0 .问题说明
在数学中，由斐波那契数字(Fibonacci number )表示
)组成的数组，称为斐波那契数列(Fibonacci sequence )。 这个数字序列中的每个数字都等于前面排列的两个数字之和。 数列从0和1开始：
，
数列中第n个(n1 )的数字如下
根据上述公式，通过计算得到的斐波那契数列如下。
随着n的增大，斐波那契数列的增长比例逐渐接近黄金分割比例。
本论文尝试使用递归法：时间复杂度这3种时间复杂度不同的算法来求解该序列的第n个数字
循环法：时间的复杂性
矩阵乘法：时间复杂性
(？ 有讨论的余地)
1 .递归解法
根据斐波那契数列的计算公式：
中选择所需的族。 自然认为这个问题适合用递归法求解。 以下是直接的python代码。
effib_recur(n ) :
if n=1: # base case递归终止条件
return n
returnfib_recur(n-1 ) fib _ recur (n-2 ) #向下递归
时间复杂度分析
细心的读者应该可以观察到递归求解的过程就像建立二叉树一样。 例如，解开
依赖关系
和
我们现在
作为树的根节点，
和
继续向下递归、左节点作为左右2个叶节点
继续分解为
和
，右节点
继续分解为
和
中选择所需的族。 如下图所示。
因此，该算法的时间复杂度。
性能优化
指数复杂度太高了
响应时间长的话不能接受，好在有优化的空间。 从上面的二叉树可以看出，存在大量重复的节点。 优化的方法是将计算结果存入词典，每次计算时调查词典中是否已经存在同一节点，如果存在，则直接返回，否则将新节点存入词典。 优化后的步骤如下。
dic={} #词典
deffib_recur_with_DIC(n ) :
global dic #使用外部变量，必须先声明
if n=1: # base case递归终止条件
return n
查阅if n in dic: #词典
返回DIC [ n ]
未找到else: #
result=fib_recur_with_DIC(n-1 ) fib_recur_with_DIC (n-2 ) fib _ recur _ with _ DIC ) ) ) )。
DIC [ n ]=结果#存储结果
返回结果
优化后的程序相当于对前面的递归树进行剪枝的操作，因为同一个节点只执行了一次，所以减少了时间的复杂性。
2 .循环解法
假设前面的递归解法是自上而下地将大问题分解为小问题来求解，则循环解的规律是逆向思维，自下而上，首先求出小问题的解，然后进一步求出最终问题的解。
求解过程如下
单击，将每个步骤的结果保存到列表中与下标对应的位置。 代码如下所示。
effib_loop(n ) :
IFN=1: # 0，1直接返回
return n
fibs=[0] * (n 1 ) #初始化数组
fibs[1]=1
forIinrange(2，n 1 ) : #从下标为2的数字开始
fibs[i]=fibs[i-1] fibs[i-2]
return fibs[n] #返回第n个数字
时间复杂度分析
单层循环，时间的复杂性
中选择所需的族。 与优化的递归解法具有相同的复杂性。
性能优化
时间复杂度没有优化的空间，但可以使用两个
临时变量替换掉长度为的列表，使空间复杂度从
降为
。代码如下：
def fib_loop_nolist(n):
if n <= 1: # 0,1 直接返回
return n
a, b = 0, 1
for i in range(2, n+1): # 从2开始
a, b = b, a + b
return b
3. 矩阵连乘法
根据斐波那契数列自身的性质，我们可以构造如下方等式关系：
使用矩阵表示上述等式关系，即
那么
依次乘下去，可得一般形式
我们要求解的
即为向量
的第一个分量。代码如下：
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几乎是一条语句返回的，这样看时间复杂度为
。但语句涉及到乘方运算，即n个矩阵相乘，时间复杂度似乎又是
。这一结论有待商榷。
性能优化
将矩阵对角化后，再进行连乘操作，可大大提升运算效率。对角化方法为
，其中
是要被对角化的矩阵，
为由
的特征向量组成的矩阵，
为由
的特征值构成的对角矩阵。
，python代码如下：
import numpy as np
def fib_matrix_diag(n):
if n <= 1: # 0,1 直接返回
return n
A = np.array([[1,1],[1,0]])
E = np.linalg.eig(A) # E中保存了A的特征值和特征向量
D = np.diag(E[0]) # 特征值对角矩阵
S = E[1] # 特征向量矩阵
result = np.mat(S) * np.mat(D)**(n-1) * np.mat(np.linalg.inv(S)) * np.mat([1,0]).T
return int(result[0,0])
问题
NumPy在处理矩阵乘法时会进行大量的浮点运算，在
时，结果的精度有损失。
4 小结经实际运行测试，不使用字典的递归算法在
时几乎慢到不可用的程度。
使用字典优化后的递归算法与循环算法性能相当，使用
测试运行时长大概在万分之一秒。
矩阵连乘算法虽看似简单，但运行效率不如循环算法，运行时长大概在千分之一秒，且矩阵对解化操作并没有带来明显的性能提升。
最终的运行效率排序为：循环法
递归(带字典)
矩阵连乘
递归(不带字典)。
参考