你应该始终返回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)
return memo[n]
通过这种方式,调用的数量被减少了,因为对于每个值 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
)越大,这种差异就越显着。
memo = {0:0, 1:1}
而不是memo = {0:1, 1:1}
。 - oba2311