python斐波那契数列递归算法的时间复杂度推导_Fibonacci 斐波那契数列的几种写法、时间复杂度对比... 拼搏现实的明天。 2022-10-28 00:51 30阅读 0赞 作者:刘志军,6年+Python使用经验, 高级开发工程师,目前在互联网医疗行业从事Web系统构架工作 个人公众号:Python之禅(微信ID:vttalk) ![122646193\_2\_20180122102907565][122646193_2_20180122102907565] 单身汪节早已被商家重新定义,除了买买买还可以做点什么?我看在家修炼编程技术是不错的选择,「用Python实现斐波那契数列」是我们在知识星球中每周给大家安排的一道题,你也可以先思考一下有哪些实现方法,说不定哪天面试就能派上用场,终有一日当上CTO赢取白富美从此走上人生巅峰。 斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为: 数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34。 用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,还会问你时间复杂度怎样,空间复杂度怎样,有没有可改进的地方。 递归法 所谓递归就是指函数的定义中使用了函数自身的方法 def fib\_recur(n): assert n >= 0 if n in (0, 1): return n return fib\_recur(n - 1) + fib\_recur(n - 2) for i in range(20): print(fib\_recur(i), end=' ') >>>0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 递归是一种写法最简洁的方法,但它是效率非常低,因为会出现大量的重复计算,时间复杂度是:O(1.618 ^ n),1.618 是黄金分割点。同时受限于 Python 中递归的最大深度是 1000,所以用递归来求解并不是一种可取的办法。 递推法 递推法就是从0和1开始,前两项相加逐个求出第3、第4个数,直到求出第n个数的值 def fib\_loop(n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a for i in range(20): print(fib\_loop(i), end=' ') >>>0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 这种算法的时间复杂是O(n),呈线性增长,如果数据量巨大,速度越到后面会越慢。 上面两种方式都是使用分而治之的思想,把一个大的问题化小,然后利用小问题的求解得到目标问题的答案。 矩阵法 《线性代数》是大学计算机专业的一门课程,教的就是矩阵,那时候觉得这东西学起来很枯燥,没什么用处,工作后你才发现搞机器学习、数据分析、数据建模时大有用处,书到用时方恨少。其实矩阵的本质就是线性方程式。 斐波那契数列中两个相邻的项分别为:F(n) 和 F(n - 1),如果把这两个数当作一个2行1列的矩阵可表示为: 因为 F(n) = F(n-1)+F(n-2),所以就有: 通过反推,其实它是由两个矩阵的乘积得来的 ![122646193\_6\_20180122102907909][122646193_6_20180122102907909] 依此类推: ![122646193\_7\_2018012210290865][122646193_7_2018012210290865] 最后可推出: ![122646193\_8\_20180122102908159][122646193_8_20180122102908159] 因此想要求出F(n)的值,只要能求出右边矩阵的n-1次方的值,最后求得两矩阵乘积,取新矩阵的第一行的第一列的值即可,比如n=3时, ![122646193\_9\_20180122102908221][122646193_9_20180122102908221] 可以得知F(3)的值2,F(2)的值为1,因为幂运算可以使用二分加速,所以矩阵法的时间复杂度为 O(log n) 我们可以用科学计算包 numpy 来实现矩阵法: import numpy def fib\_matr(n): return (numpy.matrix(\[\[1, 1\], \[1, 0\]\]) \*\* (n - 1) \* numpy.matrix(\[\[1\], \[0\]\]))\[0, 0\] for i in range(20): print(int(fib\_matr(i)), end=' ') >>>0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 3中不同的算法效率对比: ![122646193\_10\_20180122102908362][122646193_10_20180122102908362] 从上面图可以看出递归法效率惊人的低,矩阵法在数据量比较大的时候才突显出它的优势,递推法随着数据的变大,所花的时间也越来越大。 ![122646193\_11\_20180122102908581][122646193_11_20180122102908581] Python爱好者社区历史文章大合集: [122646193_2_20180122102907565]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_2_20180122102907565 [122646193_6_20180122102907909]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_6_20180122102907909 [122646193_7_2018012210290865]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_7_2018012210290865 [122646193_8_20180122102908159]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_8_20180122102908159 [122646193_9_20180122102908221]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_9_20180122102908221 [122646193_10_20180122102908362]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_10_20180122102908362 [122646193_11_20180122102908581]: http://image109.360doc.com/DownloadImg/2018/01/2222/122646193_11_20180122102908581
还没有评论,来说两句吧...