动态规划斐波那契算法

Question

我正在研究一个计算斐波那契数的算法，并得到了相应的伪代码，但我无法确定它运行所需的时间。我认为它的时间复杂度为O(n)，但不是很确定。 以下是代码：

Algorithm Fast-Fibonacci(n)
Let fib[0] and fib[1] be 1.
for each i from 2 to n, do:
    Let fib[i] be fib[i - 2] + fib[i - 1].
end of loop
return fib[n].

感谢任何帮助。

- MNM

Answer 1

您是正确的，这需要O(n)的时间复杂度，因为您只是从2到n按顺序计数来填充数组。如果您对i-1和i-2数字中的每个数字进行某种查找，那么可能会增加复杂性，但是按照您编写的方式，您正在为这些值调用直接地址。

- Mike Clark

Answer 2

没错。重要的线索是，你在每个循环中都有恒定数量的操作，并且你的循环大小与n的大小成线性关系。

然而，存在一种更节省空间的解决方案，因为你并不特别关心除了最后两个数字以外的任何数字。接下来试试这个方法吧！

- argentage

---

不！循环是针对 $n$ 线性的，而不是针对 $n$ 的 大小，其大小为 $log n$。 - Greg82

Answer 3

迭代解法找到第n个斐波那契数的时间复杂度与n的值成正比，为O(n)，与n的大小成指数关系，为O(2^length(n))（length(n)表示表示n所需位数）。这种运行时间被称为伪多项式。然而，如果使用递归方法来找到n的斐波那契数，则其时间复杂度将呈指数级增长（O(2^n)）。但是，可以通过使用动态规划方法来解决n的斐波那契数，从而将时间复杂度降低。

- beri4lord