为什么我的备忘录没有提高效率？

Question

我正在做Python中的Think练习，使用Memo计算Fibonacci序列比不使用Memo要高效得多。但是当实现它并测试所消耗的时间时，我发现运行时间并没有减少。我知道我的程序肯定有问题，有人能告诉我哪里出了问题吗。非常感谢

import time

known = {0:0,1:1}
def fibonacci_memo(n):
    """return the nth number of fibonacci sequence
    using memo to raise efficiency"""
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

def fibonacci(n):
    """return the nth number of fibonacci sequence
    without using memo"""
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

if __name__ == '__main__':
    start = time.clock()
    print fibonacci_memo(32)
    elaspsed = time.clock() - start
    print 'using memo time used: ' + str(elaspsed)

    start = time.clock()
    print fibonacci(32)
    elaspsed = time.clock() - start
    print 'without using memo time used: ' + str(elaspsed)

输出类似于：

2178309
using memo time used: 1.83040345779
2178309
without using memo time used: 1.792043347

Answer 1

记忆函数的递归调用的是另一个函数。尝试用以下内容替换斐波那契备忘录：

def fibonacci_memo(n):
    """return the nth number of fibonacci sequence
    using memo to raise efficiency"""
    if n in known:
        return known[n]

    res = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    known[n] = res
    return res