神剑山庄资源网 Design By www.hcban.com
题目:
计算斐波那契数列。具体什么是斐波那契数列,那就是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 : Cecil Charlie import sys import copy sys.setrecursionlimit(1000) # 用来调整解释器默认最大递归深度 class Fibonacci(object): def __init__(self): pass def fibonacci1(self, n): ''' 原始的方法,时间复杂度为 o(2**n),因此代价较大 :param n: 数列的第n个索引 :return: 索引n对应的值 ''' if n < 1: return 0 if n == 1 or n == 2: return 1 return self.fibonacci1(n-1) + self.fibonacci1(n-2) @staticmethod def fibonacci2(n): """ 用循环替代递归,空间复杂度急剧降低,时间复杂度为o(n) """ if n < 1: return 0 if n == 1 or n == 2: return 1 res = 1 tmp1 = 0 tmp2 = 1 for _ in xrange(1, n): res = tmp1 + tmp2 tmp1 = tmp2 tmp2 = res return res def fibonacci3(self, n): """ 进一步减少迭代次数,采用矩阵求幂的方法,时间复杂度为o(log n),当然了,这种方法需要额外计算矩阵,计算矩阵的时间开销没有算在内.其中还运用到了位运算。 """ base = [[1, 1], [1, 0]] if n < 1: return 0 if n == 1 or n == 2: return 1 res = self.__matrix_power(base, n-2) return res[0][0] + res[1][0] def __matrix_power(self, mat, n): """ 求一个方阵的幂 """ if len(mat) != len(mat[0]): raise ValueError("The length of m and n is different.") if n < 0 or str(type(n)) != "<type 'int'>": raise ValueError("The power is unsuitable.") product, tmp = [], [] for _ in xrange(len(mat)): tmp.append(0) for _ in xrange(len(mat)): product.append(copy.deepcopy(tmp)) for _ in xrange(len(mat)): product[_][_] = 1 tmp = mat while n > 0: if (n & 1) != 0: # 按位与的操作,在幂数的二进制位为1时,乘到最终结果上,否则自乘 product = self.__multiply_matrix(product, tmp) tmp = self.__multiply_matrix(tmp, tmp) n = 1 return product @staticmethod def __multiply_matrix(mat1, mat2): """ 矩阵计算乘积 :param m: 矩阵1,二维列表 :param n: 矩阵2 :return: 乘积 """ if len(mat1[0]) != len(mat2): raise ValueError("Can not compute the product of mat1 and mat2.") product, tmp = [], [] for _ in xrange(len(mat2[0])): tmp.append(0) for _ in xrange(len(mat1)): product.append(copy.deepcopy(tmp)) for i in xrange(0, len(mat1)): for j in xrange(0, len(mat2[0])): for k in xrange(0, len(mat1[0])): if mat1[i][k] != 0 and mat2[k][j] != 0: product[i][j] += mat1[i][k] * mat2[k][j] return product f = Fibonacci() print f.fibonacci1(23) print f.fibonacci2(23) mat1 = [[2,4,5],[1,0,2],[4,6,9]] mat2 = [[2,9],[1,0],[5,7]] print f.fibonacci3(23)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
标签:
python,斐波那契数列
神剑山庄资源网 Design By www.hcban.com
神剑山庄资源网
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
神剑山庄资源网 Design By www.hcban.com
暂无python斐波那契数列的计算方法的评论...
更新日志
2024年10月02日
2024年10月02日
- 孙悦.1996-伙伴【正大国际】【WAV+CUE】
- 纪钧瀚《钢琴阅读时光 雨中书店聆听轻音乐》[FLAC/分轨][399.62MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[320K/MP3][87.4MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[FLAC/分轨][184.94MB]
- 陈慧娴.2018-Priscilla-Ism演唱会3CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 郑秀文.1999-我应该得到(国)【华纳】【WAV+CUE】
- 陈家慧.2011-钢琴酒吧2CD【龙吟唱片】【WAV+CUE】
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[320K/MP3][45.01MB]
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[FLAC/分轨][109.13MB]
- 赞多《序章》[320K/MP3][45.54MB]
- 许巍.2004-每一刻都是崭新的【步升大风】【WAV+CUE】
- 群星.2024-四方馆影视原声带【韶愔音乐】【FLAC分轨】
- 陈雷.1997-安锁咧【金圆唱片】【WAV+CUE】
- 关淑怡.2013-MY.FAVORITE.SK.3CD【环球】【WAV+CUE】
- Sweety.2006-花言乔语【丰华】【WAV+CUE】