Python中的记忆斐波那契算法

一尘不染

Python中的记忆斐波那契算法

algorithm

我有这种记忆技术，可以减少获得斐波那契序列号的呼叫数量：

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)
        return memo[n]


def fib1(n):
    memo = {0:1, 1:1}
    return fastFib(n, memo)


numCalls = 0
n = 6
res = fib1(n)
print 'fib of', n,'=', res, 'numCalls = ', numCalls

但是我被困在这里：memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)这里memo = {0:1, 1:1}。每次我想获取数字fib时，如何准确减少通话次数？

阅读 370

2020-07-28

共1个答案

一尘不染

您应该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）越大，该差异就越大。

2020-07-28