为什么这两种寻找第 n 个斐波那契数的算法中的一种更有效？
Why is one of these two algorithms for finding the n-th Fibonacci number more efficient?
计算第64个斐波那契数时，第一个算法需要几个小时，第二个不到一秒。
为什么第二种算法的效率比第一种算法高这么多？
他们看起来很像。
def fib_divide_recursion(n):
if n <= 2:
return n-1
else:
return fib_divide_recursion(n-1) + fib_divide_recursion(n-2)
def fib_linear_recursion(n, prev={}):
if n <= 2:
return n-1
try:
return prev[n]
except KeyError:
prev[n] = fib_linear_recursion(n - 1, prev) +
fib_linear_recursion(n - 2, prev)
return prev[n]
第一个算法的复杂度是O(2^n)。
第二个将结果缓存在 prev 中，因此它永远不会为给定数字计算 fib_linear_recursion 超过一次。它的复杂度是线性的，O(n)。
有关详细信息，请参阅 this answer。
第二个实现是使用 "memoizing" 来记住之前计算的斐波那契值。
假设您正在尝试计算 fib(5)：您首先必须计算 fib(4) 和 fib(3)。 fib(4)本身也需要你去计算fib(3)。事实上，对于每一个斐波那契数，你要么计算前面的每一个斐波那契数一次并存储它们（这就是记忆方法）。或者，在性能更差的情况下，您可以重新计算所需的每个斐波那契数，即使您之前已经计算过它也是如此。显然，如果没有记忆，您将需要做更多的工作，对于高斐波那契数，这确实会有所不同，正如您所观察到的那样。
第一种算法仅使用递归，而第二种算法使用动态规划，即带记忆的递归。
如果您为第一个算法画一棵树，您会看到重复的节点。但是使用第二种算法，它存储已经计算出的节点，因此程序不必一次又一次地计算
计算第64个斐波那契数时，第一个算法需要几个小时，第二个不到一秒。
为什么第二种算法的效率比第一种算法高这么多？
他们看起来很像。
def fib_divide_recursion(n):
if n <= 2:
return n-1
else:
return fib_divide_recursion(n-1) + fib_divide_recursion(n-2)
def fib_linear_recursion(n, prev={}):
if n <= 2:
return n-1
try:
return prev[n]
except KeyError:
prev[n] = fib_linear_recursion(n - 1, prev) +
fib_linear_recursion(n - 2, prev)
return prev[n]
第一个算法的复杂度是O(2^n)。
第二个将结果缓存在 prev 中，因此它永远不会为给定数字计算 fib_linear_recursion 超过一次。它的复杂度是线性的，O(n)。
有关详细信息，请参阅 this answer。
第二个实现是使用 "memoizing" 来记住之前计算的斐波那契值。
假设您正在尝试计算 fib(5)：您首先必须计算 fib(4) 和 fib(3)。 fib(4)本身也需要你去计算fib(3)。事实上，对于每一个斐波那契数，你要么计算前面的每一个斐波那契数一次并存储它们（这就是记忆方法）。或者，在性能更差的情况下，您可以重新计算所需的每个斐波那契数，即使您之前已经计算过它也是如此。显然，如果没有记忆，您将需要做更多的工作，对于高斐波那契数，这确实会有所不同，正如您所观察到的那样。
第一种算法仅使用递归，而第二种算法使用动态规划，即带记忆的递归。
如果您为第一个算法画一棵树，您会看到重复的节点。但是使用第二种算法，它存储已经计算出的节点，因此程序不必一次又一次地计算