python - 为什么这两种寻找第 n 个斐波那契数的算法中的一种更有效？

Question

在计算第 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]

标签： pythonalgorithmfibonacci

Answer 1

第二种实现是使用“记忆”来记住以前计算的斐波那契值。

考虑到您正在尝试计算fib(5)：您首先必须计算fib(4)和fib(3)。fib(4)本身也需要你去计算fib(3)。事实上，对于每个斐波那契数，您可以计算每个前面的斐波那契数一次并存储它们（这是记忆方法）。或者，在性能更差的情况下，您可以重新计算您需要的每个斐波那契数，即使您之前已经计算过了。显然，如果没有记忆，您将需要做更多的工作，并且对于高斐波那契数，这确实会产生影响，正如您所观察到的。