python斐波那契数列的计算方法
题目：
计算斐波那契数列。具体什么是斐波那契数列，那就是0，1，1，2，3，5，8，13，21，34，55，89，144，233。
要求：
时间复杂度尽可能少
分析：
给出了三种方法：
方法1：递归的方法，在这里空间复杂度非常大。如果递归层数非常多的话，在python里需要调整解释器默认的递归深度。默认的递归深度是1000。我调整了半天代码也没有调整对，因为递归到1000已经让我的电脑的内存有些撑不住了。
方法2：将递归换成迭代，这样时间复杂度也在代码中标注出来了。
方法3：这种方法利用了求幂的简便性，采用了位运算。但是代价在于需要建立矩阵，进行矩阵运算。所以，当所求的数列的个数较小时，该方法还没有第二种简便。但是当取的索引值n超级大时，这种方法就非常方便了。时间复杂度在代码中标注出来了。
代码：
#!usr/bin/python2.7
#-*-coding=utf8-*-
#@Time:18-1-3下午2:53
#@Author:CecilCharlie
importsys
importcopy
sys.setrecursionlimit(1000)#用来调整解释器默认最大递归深度
classFibonacci(object):
def__init__(self):
pass
deffibonacci1(self,n):
'''
原始的方法，时间复杂度为o(2**n)，因此代价较大
:paramn:数列的第n个索引
:return:索引n对应的值
'''
ifn<1:
return0
ifn==1orn==2:
return1
returnself.fibonacci1(n-1)+self.fibonacci1(n-2)
@staticmethod
deffibonacci2(n):
"""
用循环替代递归，空间复杂度急剧降低，时间复杂度为o(n)
"""
ifn<1:
return0
ifn==1orn==2:
return1
res=1
tmp1=0
tmp2=1
for_inxrange(1,n):
res=tmp1+tmp2
tmp1=tmp2
tmp2=res
returnres
deffibonacci3(self,n):
"""
进一步减少迭代次数，采用矩阵求幂的方法，时间复杂度为o(logn)，当然了，这种方法需要额外计算矩阵，计算矩阵的时间开销没有算在内.其中还运用到了位运算。
"""
base=[[1,1],[1,0]]
ifn<1:
return0
ifn==1orn==2:
return1
res=self.__matrix_power(base,n-2)
returnres[0][0]+res[1][0]
def__matrix_power(self,mat,n):
"""
求一个方阵的幂
"""
iflen(mat)!=len(mat[0]):
raiseValueError("Thelengthofmandnisdifferent.")
ifn<0orstr(type(n))!="":
raiseValueError("Thepowerisunsuitable.")
product,tmp=[],[]
for_inxrange(len(mat)):
tmp.append(0)
for_inxrange(len(mat)):
product.append(copy.deepcopy(tmp))
for_inxrange(len(mat)):
product[_][_]=1
tmp=mat
whilen>0:
if(n&1)!=0:#按位与的操作，在幂数的二进制位为1时，乘到最终结果上，否则自乘
product=self.__multiply_matrix(product,tmp)
tmp=self.__multiply_matrix(tmp,tmp)
n>>=1
returnproduct
@staticmethod
def__multiply_matrix(mat1,mat2):
"""
矩阵计算乘积
:paramm:矩阵1，二维列表
:paramn:矩阵2
:return:乘积
"""
iflen(mat1[0])!=len(mat2):
raiseValueError("Cannotcomputetheproductofmat1andmat2.")
product,tmp=[],[]
for_inxrange(len(mat2[0])):
tmp.append(0)
for_inxrange(len(mat1)):
product.append(copy.deepcopy(tmp))
foriinxrange(0,len(mat1)):
forjinxrange(0,len(mat2[0])):
forkinxrange(0,len(mat1[0])):
ifmat1[i][k]!=0andmat2[k][j]!=0:
product[i][j]+=mat1[i][k]*mat2[k][j]
returnproduct
f=Fibonacci()
printf.fibonacci1(23)
printf.fibonacci2(23)
mat1=[[2,4,5],[1,0,2],[4,6,9]]
mat2=[[2,9],[1,0],[5,7]]
printf.fibonacci3(23)
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。