IT博客汇 | python求解斐波那契数列的两个方法

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

master发表于 2014-10-17 06:33:02

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

View Code BASH

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

View Code PYTHON

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())

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