动态规划斐波那契算法

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 数字进行某种查找，这可能会增加复杂性，但按照您编写的方式，您正在为每个值调用直接地址。