用python写出斐波那契数列,编程求斐波那契数列前20项python
0.问题描述
在数学上，用斐波那契数来表示。
)，称为斐波那契数列。这个数列中的每一个数都等于排在它前面的两个数之和。从系列0和1开始：
,
序列中第n个(n1)的编号如下
根据上面的公式，计算得到的斐波那契数列如下。
随着n的增加，斐波那契数列的增长比逐渐接近黄金分割比。
本文尝试用递归方法：时间复杂度，三种不同时间复杂度的算法，来求解数列的第n个数。
循环：时间的复杂性
矩阵乘法：时间复杂度
(?有讨论的余地)
1.递归解
根据斐波那契数列的计算公式：
在中选择所需的族。自然，这个问题适合用递归方法来解决。下面是直接的python代码。
effib _ recurve(n):
If=1: # basecase递归终止条件
返回
向下返回Fib _ recurve(n-1)Fib _ recurve(n-2)#递归
时间复杂性分析
细心的读者应该能观察到，递归求解的过程就像构建二叉树一样。例如，解开
依赖关系
和
我们现在
作为树的根节点，
和
继续向下递归，以左节点为左右叶节点。
继续分解成
和
，右节点
继续分解成
和
在中选择所需的族。如下图所示。
因此，算法的时间复杂度。
性能优化
指数复杂度太高
长响应时间是不可接受的，但是有优化的空间。从上面的二叉树可以看出，有很多重复的节点。优化方法是将计算结果存储在字典中，每次都调查字典中是否已经存在相同的节点。如果存在，则直接返回，否则将新节点存储在字典中。优化的步骤如下。
Dic={} #字典
def fib _ recurve _ with _ DIC(n):
全局dic #使用外部变量，这些变量必须首先声明。
If=1: # basecase递归终止条件
返回
在dic中查找n:# dictionary
返回到DIC [n]
否则未找到：#
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直接返回
返回
Fib=[0] * (n 1) #初始化数组
fibs[1]=1
for range(2，n 1): #从下标为2的数字开始
fibs[i]=fibs[i-1] fibs[i-2]
Return fibs[n] #返回第n个数
时间复杂性分析
单一周期，时间复杂性
在中选择所需的族。它与最优化的递归解具有相同的复杂性。
性能优化
时间复杂度没有优化的余地，但是可以用两个。
临时变量被替换为长度
列表，这样空间复杂度就从
减少到。代码如下：
def fib_loop_nolist(n):
如果=1: # 0，1直接返回
返回
a，b=0，1
对于范围(2，n-1)中的I:#从2开始
a，b=b，a b
返回b
3.矩阵连续乘法
根据斐波那契数列本身的性质，我们可以构造如下等式关系：
用矩阵来表达上述方程关系，即
因此
依次向下乘，得到一般形式。
我们寻求解决方案。
是矢量。
的第一部分。代码如下：
将numpy作为np导入
def fib_matrix(n):
如果=1: # 0，1直接返回
返回
result=np.mat([[1，1]，[1，0]]，dtype= float 64 )* *(n-1)* NP . mat([1，0])。T
return int(结果[0，0])
时间复杂性分析
从程序的角度来看，result结果几乎都是由一条语句返回的，所以时间复杂度为。但是语句涉及到幂运算，也就是N个矩阵相乘，时间复杂度好像是。这个结论值得商榷。
性能优化
矩阵对角化后，乘法运算可以大大提高运算效率。对角化的方法是
，其中
是要对角化的矩阵，
经过
由特征向量组成的矩阵，
经过
由的特征值组成的对角矩阵。
，python代码如下：
将numpy作为np导入
定义纤维矩阵诊断(n):
如果=1: # 0，1直接返回
返回
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(结果[0，0])
问题
NumPy在处理矩阵乘法时会做很多浮点运算，在
当为时，结果的准确性会丢失。
4总结经过实际运行测试，无字典递归算法在
几乎慢到无法使用。
使用字典优化的递归算法与循环算法具有相同的性能，使用
测试的运行时间约为十分之一秒。
矩阵乘法算法虽然看似简单，但运行效率不如循环算法，运行时间约为千分之一秒，矩阵并没有给求解运算带来明显的性能提升。
运营效率最终排序为：循环法。
递归(带字典)
矩阵连续乘法
递归(无字典)。
涉及
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。