python求解斐波那契数列的两个方法

Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个。
这次在,python中也不例外,最基本的那种递归(如下fib1)效率太低了,只要n数字大了运算时间就会很长;而通过将计算的指保存到一个dict中,后面计算时直接拿来使用,这种方式成为备忘(memo),如下面的fib2函数所示,则会发现效率大大提高。
在n=10以内时,fib1和fab2运行时间都很短看不出差异,但当n=40时,就太明显了,fib1运行花了35秒,fab2运行只花费了0.000082秒。
n=40时,输出如下:

这两个计算Fibonacci数列的函数,如下:https://github.com/smilejay/python/blob/master/py2014/fibonacci.py

master

Stay hungry, stay foolish.

2 Comments

  1. 要说省一半有点道理, 什么原因差异这么大, 说不通啊!

    • 试试就知道了 说得通啊 减少了太多的递归调用了

发表评论

电子邮件地址不会被公开。 必填项已用*标注