为什么这两种算法中的一种能够更有效地找到第n个斐波那契数？

Question

在计算第64个Fibonacci数时，第一个算法需要几个小时，第二个算法需要不到一秒钟。

为什么第二个算法的效率比第一个算法的效率高得多？

它们看起来很相似。

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]

Answer 1

第二个实现是使用“memoizing”来记住先前计算的Fibonacci值。

考虑一下你正在尝试计算fib(5)：你首先要计算fib(4)和fib(3)。 fib(4)本身也要求你计算fib(3)。实际上，对于每个Fibonacci数，您可以计算一次前面的每个Fibonacci数并存储它们（这是memoization方法）。或者，在性能更差的情况下，您可以重新计算所需的每个斐波纳契数，即使您之前已经计算过它。很明显，如果没有记忆，你需要做更多的工作，而对于高斐波那契数字，这确实有所不同，正如你所观察到的那样。

Answer 2

第一算法的复杂度为O（2 ^ n）。

第二个将结果缓存在prev中，因此它不会为给定数字多次计算fib_linear_recursion。它的复杂性是线性的，O（n）。

有关详细信息，请参阅this answer。

Answer 3

第一种算法仅使用递归，而第二种算法使用动态编程，即带有记忆的递归。

如果您为第一个算法绘制树，您将看到重复的节点。但是使用第二算法，它存储已经计算的节点，因此程序不必一次又一次地计算