爲什麼我的備忘錄根本沒有提高效率？

Question

我在Python中進行思考練習，用Memo來計算Fibonacci序列比不使用一個更有效。但是當實施它並測試所消耗的時間時，我發現運行時間根本沒有減少。我知道我的程序肯定有問題，有人可以告訴我我哪裏出了錯。非常感謝。

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

你fibonacci_memo功能是不是自稱遞歸，它調用的原始（非memoized）斐波那契數函數。

Answer 2

您的memoized函數的遞歸調用一個不同的函數。嘗試用此替換fibonacci_memo：

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