動態規劃斐波那契算法

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的大小成線性關係。

但是，由於您並不特別在乎最後兩個數字以外的任何數字，因此存在更具空間效率的解決方案。接下來嘗試！