斐波那契数列公式

（上帝密码 0.618）

基础递推

$f(n) = f(n-1) + f(n-2)$

1
2
3
4
def fib(n):
  if n <= 1:
    return n
  return fib(n-1) + fib(n-2)
1
fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)

递归深度 就是 —- $n$ ( 展开 —- 递归树)

时间复杂度 —- $O(n^2)$ $f(n) = f(n-1) + f(n-2)$ 两边同时计算 类似二叉树 造成了很多重复性工作

空间复杂度 —- $O(n)$ —- 进栈出栈 ( 后进先出 )

优化递推

递推每次的计算结果放在数据结构中，如果之前计算过直接拿来用

1
2
3
4
5
6
7
fib_dict = dict()
def fib(n):
  if n <= 1:
    return n
  if n in fib_dict:
    return fib_dict[n]
  return fib(n-1) + fib(n-2)

时间复杂度 —- $O(n)$ 相当于对基础递归 ( 二叉树 ) 做了剪枝

时间复杂度没有优化空间， 对空间复杂度入手优化

基础循环

递推采用自顶向下去计算，把一个大任务拆分成N个小任务，循环相反，从小任务逐渐到大任务

1
2
3
4
5
6
7
def fib(n):
  fibs = [0] * (n + 1)
  if n <= 1:
    return n
  for i in range(2, n+1):
    fibs[i] = fibs[i-1] + fibs[i-2]
   return fibs[n]

时间复杂度 —- $O(n)$ 与优化后的递推复杂度相当

优化循环

对空间复杂度进一步优化

1
2
3
4
5
6
7
def fib(n):
	if n <= 1:
		return n
  a, b = 0, 1
  for i in range(2, n+1):
    a, b = b, a+b
  return b

空间复杂度 —- $O(1)$

矩阵乘法

$\begin{pmatrix} F_{n+2} \ F_{n+1} \end{pmatrix}=\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n+1} \ F_{n} \end{pmatrix}$

$\begin{pmatrix} F_{n+2} & F_{n+1} \ F_{n+1} & F_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^{n + 1}$

1
2
3
4
5
6
import numpy as np
def fib_matrix(n):
    if n <= 1: # 0,1 直接返回
        return n
    result = np.mat([[1,1],[1,0]],dtype='float64')**(n-1) * np.mat([1,0]).T
    return int(result[0,0])

时间复杂度分析

从程序上看，结果result几乎是一条语句返回的，这样看时间复杂度为 $O(1)$。但语句涉及到乘方运算，即n个矩阵相乘，时间复杂度似乎又是 $O(n)$。这一结论有待商榷。

最终的运行效率排序为：

循环法 > 递归(带字典) > 矩阵连乘 > 递归(不带字典)。