Python中的记忆斐波那契算法

Python中的记忆斐波那契算法

您应该

memo[n]

始终返回，不仅要进行不安全的查找（的最后一行

fastFib()

）：

def fastFib(n, memo):    global numCalls    numCalls += 1    print 'fib1 called with', n    if not n in memo:        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)    #this should be outside of the if clause:    return memo[n] #<<<<<< THIS

这样可以减少调用次数，因为对于

n

您的每个值，实际上最多只能计算和递归一次，从而将递归调用的次数限制为

O(n)

（

2n

调用上限），而不必一次又一次地有效地重新计算相同的值进行指数递归调用。

fib（5）的一个小例子，其中每一行都是递归调用：

天真的方法：

f(5) = f(4) + f(3) = f(3) + f(2) + f(3) =f(2) + f(1) + f(2) + f(3) =f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 1 + f(0) + f(1) + f(2) + f(3) = 2 + f(1) + f(2) + f(3) =3 + f(2) + f(3) = 3 + f(1) + f(0) + f(3) = 3 + 1 + f(0) + f(3) = 5 + f(3) = 5 + f(2) + f(1)  =5 + f(1) + f(0) + f(1) =5 + 1 + f(0) + f(1) =5 + 2 + f(1) =8

现在，如果您使用备忘录，则无需重新计算很多事情（例如

f(2)

，它被计算了3次），您将获得：

f(5) = f(4) + f(3) = f(3) + f(2) + f(3) =f(2) + f(1) + f(2) + f(3) =f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 1 + f(0) + f(1) + f(2) + f(3) = 2 + f(1) + f(2) + f(3) =3 + f(2) + f(3) =  {f(2) is already known}3 + 2 + f(3) = {f(3) is already known}5 + 3  = 8

如您所见，第二个比第一个短，并且数字（

n

）越大，该差异就越大。