algorithm - 动态规划斐波那契算法

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].

谢谢你的帮助。

Answer 1

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

Answer 2

是的。最大的收获是每个循环都有恒定数量的操作，并且循环的大小与 n 的大小成线性关系。

但是，存在一种更节省空间的解决方案，因为除了最后两个之外，您并不特别关心任何数字。下次试试！

Answer 3

找到第 n 个斐波那契的迭代解决方案在 n 的值方面采用 O(n)，在 n 的大小方面采用 O(2^length(n))（长度（n）== 表示 n 的位数） . 这种运行时间称为伪多项式。但是，如果使用递归方法来找到 n 的 fib，那么就值而言，它将花费指数时间 (O(2^n))。但这可以通过使用动态规划方法来解决 n 的 fib 来减少。