最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
求解斐波那契数列 python 的两个方法比较
时间:2015-03-08 编辑:简简单单 来源:一聚教程网
Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个。
这次在,python中也不例外,最基本的那种递归(如下fib1)效率太低了,只要n数字大了运算时间就会很长;而通过将计算的指保存到一个dict中,后面计算时直接拿来使用,这种方式成为备忘(memo),如下面的fib2函数所示,则会发现效率大大提高。
在n=10以内时,fib1和fab2运行时间都很短看不出差异,但当n=40时,就太明显了,fib1运行花了35秒,fab2运行只花费了0.00001秒。
n=40时,输出如下:
代码如下 | 复制代码 |
jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py 2014-10-16 16:28:35.176396 fib1(40)=102334155 2014-10-16 16:29:10.479953 fib2(40)=102334155 2014-10-16 16:29:10.480035 |
这两个计算Fibonacci数列的函数,如下:https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
代码如下 | 复制代码 |
import datetime def fib1(n): if n == 0: return 0 elif n == 1: return 1 else: return fib1(n - 1) + fib1(n - 2) known = {0: 0, 1: 1} def fib2(n): if n in known: return known[n] res = fib2(n - 1) + fib2(n - 2) known[n] = res return res if __name__ == '__main__': n = 40 print(datetime.datetime.now()) print('fib1(%d)=%d' % (n, fib1(n))) print(datetime.datetime.now()) print('fib2(%d)=%d' % (n, fib2(n))) print(datetime.datetime.now()) |