2

谁能解释为什么这条线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)
4

2 回答 2

4

没错，有一种称为动态编程（又名记忆化）的技术，您可以通过这种技术存储和重用计算结果。这使得查找和计算在以后变得更快。

当您删除时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)等。这会浪费大量时间。因此，为了节省时间（因为我们是程序员，我们非常在意时间），我们交换空间（即内存）来缓存以前的计算，从而……通过在缓存上查找来节省时间。

在 Python 字典上执行查找的时间复杂度是（平均）O(1)，这需要恒定的时间，并且是程序员在算法中可能希望的最好的事情。fib(n)将其与从头计算 a 的笨重时间复杂度进行比较。（请注意，正如@brunodesthuilliers 所评论的那样，您的函数当前通过遍历dict.keys()对象来执行查找，这将导致（更糟糕的）O(n)查找时间复杂度。简单地更改if n in fibValue.keys()为if n in fibValue可能会导致更快的计算。）

正如@PatrickArtner所建议的那样，如果您只找到一个斐波那契值，您可以通过仅存储两个值（即最新的斐波那契值）而不是缓存每个结果来使您的斐波那契计算器在时间和空间方面更有效.

于 2018-12-19T13:49:53.043 回答
0

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

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

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

于 2018-12-19T13:57:33.473 回答