您应该
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)越大,该差异就越大。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)