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)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。