Python快速计算Fibonacci数列中第n项的方法

from time import time from functools import lru_cache

def fibo1(n): '''递归法''' if n in (1, 2): return 1 return fibo1(n-1) + fibo1(n-2)

@lru_cache(maxsize=64) def fibo2(n): '''递归法,使用缓存修饰器加速''' if n in (1, 2): return 1 return fibo2(n-1) + fibo2(n-2)

def fibo3(n): '''序列解包''' a, b = 1, 1 for i in range(2, n+1): a, b = b, a+b return a

# 测试3个函数的执行速度 n = 40 for fibo in (fibo1, fibo2, fibo3): start = time() print(fibo.__name__, fibo(n), sep=':', end=':')

print(time()-start)

运行结果:

fibo1:267914296:67.31945824623108 fibo2:267914296:0.0 fibo3:267914296:0.0

由于第一个函数运行速度非常慢,在n变大时只测试后面2个函数的执行时间,当n=120时,运行结果为:

fibo2:5358359254990966640871840:0.0 fibo3:5358359254990966640871840:0.0

当n=220时,运行结果为:

fibo2:4244200115309993198876969489421897548446236915:0.0 fibo3:4244200115309993198876969489421897548446236915:0.0

当n=380时,第二个函数由于递归深度过大而崩溃,抛出异常

RecursionError: maximum recursion depth exceeded while calling a Python object

下面继续测试第3个函数,当n=500时,运行结果为:

fibo3:139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125:0.015594482421875

当n=1000时,运行结果为:fibo3:43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875:0.035840511322021484

当n=8000时,运行结果为:

fibo3:3561533204460626739768914905427460387141369539110154082973500638991885819498711815304829246223963373749873423083216889782034228521693267175594214186111978816819236959743284321273097535654614718808050244321699002512466203835566030351092652496815708455980825654877181538741827129421689128991879649533246136168998590044965735035810856774605383628378979290580539135791985063484992877932473487054068899476937399295193905527420792975902913836012199062687063537510151753758100626402591751183925883151617648375005313453493271681248233059858496951790113255897429539560654496639601132039360167542277472498901884679404509894269174519328918160745655327632006736189766801968534195725815421784083495026969542066047758885029695257263330719223956309043195653930347983496830801755572982419821881275569179922973415736010289561700699477021488635509784509168019589640190234350021673802856836365767446249424907273016689053388000785637444921523414602360860001530139933615215383220927084750528293779491002813557093860863839463287251443115581618266959802005566973874793475256663122039030056061200186123236430592279484254766158650545069933528061680141046574115103014532101595841822474764213889385114174543352137856680694687244097968099924183815689652779302937329729253678579649215884078334428338037327451220722810587680172255878795449524781554973097109174140632623167659027450550461045055883872225659796812847075286475208205923875668405160707778568995306926178023176315799965539425437791083258303238592641010878264249883586034912756021070468742995902773902487497010335873840408520900059054071283266816325489230566003110549946685475230821114509971542662742044237174282248020953398789607528748909125:0.09996175765991211

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2017-10-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的博客

php命名空间详解

1、命名空间概述 从广义上来说,命名空间是一种封装事物的方法。在很多地方都可以见到这种抽象概念。例如,在操作系统中目录用来将相关文件分组,对于目录中的文件来说,...

34080
来自专栏我的技术专栏

Java Thread wait、notify与notifyAll

16620
来自专栏Python攻城狮

Python-线程1.线程2.多线程-threading3.主线程会等待所有的子线程结束后才结束4.查看线程数量 5.threading注意点 6.多线程-共享全局变量 7.列表当做实参传递到线程中

thread.start_new_thread(function,args[,kwargs])

49630
来自专栏Python小屋

列表元素循环移位中Python切片的妙用

之前有个文章中介绍了列表循环移位的3中方法,原文请见:Python序列循环移位的3种方法 其中第二种方法虽然更直接地翻译了题目的要求,但是显得还是有点啰嗦,如...

35540
来自专栏JackeyGao的博客

Django小技巧08: Blank or Null

Django Model API 中提供了blank和null两个参数, 非常容易混淆。当我第一次使用 Django 的时候, 总是不能恰当的使用这两个参数。

8530
来自专栏Python小屋

回调函数原理与Python实现

回调函数的定义与普通函数并没有本质的区别,但一般不直接调用,而是作为参数传递给另一个函数,当另一个函数中触发了某个事件、满足了某个条件时就会自动调用回调函数。下...

42680
来自专栏我是攻城师

关于线程可见性一个“诡异”的问题

如果执行上面的代码,大多人可能觉得会死循环,因为这里没有任何的同步策略,比如synchronized,Lock,atomic,volatile等关键字,也就是说...

10330
来自专栏用户2442861的专栏

Java类加载器深入探索

林炳文Evankaka原创作品。转载请注明出处http://blog.csdn.net/evankaka

11010
来自专栏ccylovehs

JDK动态代理与CGLib动态代理

JDK1.3以后java提供了动态代理技术,允许开发者在运行期创建接口的代理实例,动态代理是实现AOP的绝好底层技术。

44610
来自专栏运维技术迷

Redis全局命令

redis有5种数据结构,他们是键值对中的值,对于键来说有一些通用的命令。 查看所有键 语法:keys * [root@vultr ~]# redis-cli ...

35170

扫码关注云+社区

领取腾讯云代金券