題目連結: Fibonacci Number

此題為給定數字 N，要求費氏數列第N項 F(N)，其中費氏數列定義為:
F(0)=0
F(1)=1
F(N)=F(N-1)+F(N-2) , for N>1
題目另外有補充: $0 \leq N \leq 30$。

思路1： 公式解

我們可由公式解直接計算一般項 $F(N) = \frac{1}{\sqrt{5}} \left[ \left( \frac{1 + \sqrt{5}}{2} \right)^N - \left( \frac{1 - \sqrt{5}}{2} \right)^N \right]$

• 複雜度評估
  當要求F(N)項時，因為步驟中需要自乘N次， 時間複雜度為 O(N)。
  此方法只用了常數量變數，與N無關，空間複雜度為 O(1)。

參考程式碼

func fib(N int) int {
    ans:=0
    c:=(1.0/math.Sqrt(5))
    first:=1.0
    second:=1.0
    
    for i:=0;i<N;i++{
        first*=(1+math.Sqrt(5))/2.0
        second*=(1-math.Sqrt(5))/2.0
    }
    
    ans= int (c*(first-second))
    return ans
}

思路2： 遞迴法

當 n>1 時，根據定義 F(n) = F(n-1) + F(n-2)，我們只需要不斷呼叫原函式即可。

• 複雜度評估
  因為此方法每次會呼叫原函式處理前兩個數，當要求第 N 項時，時間複雜度為 $O(2^N)$
  詳細過程可以參考此連結，附有圖解。此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func fib(N int) int {
    if N<=1{
        return N
    }
    
    return fib(N-1)+fib(N-2)
    
}

思路3 : 迭代法

我們也可以從頭開始累加，每次保留最後兩項的值，直到第 N 項。

• 複雜度評估
  當要求第N項時，我們需要處理N次，時間複雜度為 O(N)
  此方法只用了常數量變數，與N無關，空間複雜度為 O(1)。

參考程式碼

func fib(N int) int {
    if N<=1{
        return N
    }
    
    first:=0
    second:=1
    sum:=0
    
    
    for i:=2;i<=N;i++{
       sum=first+second
        first=second
        second=sum
    }
    
    return sum
}

小結

方法 1 若要求費氏數列第 N 項，則需要做 N 次浮點數的乘法以及加減法運算，再轉回整數。我們需要留意計算完的答案跟所求是否會有誤差。
方法 2 雖然程式碼簡潔，可是時間複雜度為 $O(2^N)$，需要的步驟極多。實務上一般不採用此方法。另外此方法計算過程是由費氏數列第 N 項往回呼叫到第 0 項，過程會重複計算一樣的項，也是方法 2 的缺點。
若今天題目更改為: 給定 N，輸出費式數列第 0 項 到第 N 項的值，則我們只需要將解法 3 稍做修改，在計算過程中把每項的值存起來即可。

我將解法 3 修改後的方法作為解法4 加上簡單的測試，上傳程式碼到此。