需要解释为什么这条线使我的斐波那契计算器中的一切变得更快。 (Python)

Question

谁能解释一下为什么这条线 fibValue[n] = result 让一切变得如此快？只要去掉那条线，加载超过 30 的任何东西都需要很长时间。提前致谢！

fibValue = { 0: 0, 1: 1}

def fib(n):
    if n in fibValue.keys():
        return fibValue[n]
    else:
        result = fib(n-1) + fib(n-2)
        fibValue[n] = result
        return result

result = fib(int(input("Enter number: ")))
print(result)

Answer 1

这就是一种称为 dynamic programming（又名记忆化）的技术，您可以通过这种技术存储和重用计算结果。这使得以后的查找和计算速度大大加快。

当您删除 fibValue[n] = result 时，您不会存储结果，并且由于不存储结果，您需要重新计算 该特定数字的斐波那契 n.

考虑计算 fib(6)。在第一个函数调用中，您得到

fib(6) = fib(5) + fib(4)

通过递归，得到

fib(6) =                       fib(4)               +            fib(3)        +             fib(3)       +     fib(2)

fib(6) =            fib(3)        +     fib(2)      +     fib(2)      + fib(1) +      fib(2)     + fib(1) + fib(1) + fib(0)

fib(6) =      fib(2)     + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

fib(6) = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

fib(6) =    1   +    1   +    1   +    1   +    1   +    1   +    1   +    1   +   1   +    1   +    1   +    1   +    1

fib(6) =    13

您可以看到 fib(3) 和 fib(2) 分别至少计算了 3 次。现在考虑一下您的输入是否多大（比如 1000）。您将重复计算 fib(3)、fib(100)、fib(200) 等。 这浪费了大量的时间。因此，为了节省时间（因为我们是程序员，我们非常注重时间），我们以 space（即内存）来缓存以前的计算，从而...通过在缓存上进行查找来节省时间。

在 Python 字典上执行查找的时间复杂度（平均）为 O(1)，这需要常数时间，并且是 最好的 程序员可能希望在算法中。将其与从头开始计算 fib(n) 的繁琐时间复杂度进行比较。（请注意，作为，您的函数当前通过遍历 dict.keys() 对象来执行查找，这将导致（更坏的情况）O(n) 查找的时间复杂度。只需更改if n in fibValue.keys() 到 if n in fibValue 可能会导致更快的计算。）

正如所建议的那样，如果您只找到一个单个斐波那契值，您可以使您的斐波那契计算器更高效 - space-wise 仅存储两个值（即最新的 fib 值）而不是缓存每个结果。

Answer 2

您在此处用于计算斐波那契数列的技术称为动态规划方法。

动态规划法将问题分解成子问题，求解每个子问题并保存每个子问题的结果。

这些结果用于解决其他子问题。所以它使算法更快。

需要解释为什么这条线使我的斐波那契计算器中的一切变得更快。 (Python)

Need an explanation on why this line makes everything faster in my Fibonacci calculator. (Python)

python

dynamic-programming

fibonacci