費氏數列(Fibonacci numbers)

還記得達文西密碼裡面，羅浮宮館長死前留下的密碼嗎？

其中關鍵的線索就是費氏數列！

費氏數列，又稱斐波那契數列。意思是有一列數字，最後一個數字是其前面兩個數字的相加。

我們給一個n，請您回傳費氏數列最後的數字。

Example

fib(10) -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
answer = 55 

fib(6) -> [0, 1, 1, 2, 3, 5, 8]
answer = 8 

這邊我們用費氏數列來說明：

一道題目，用不同演算法所造成不同的時間複雜度。

JavaScript 解法

先看 js 的迴圈與遞迴解

js 迴圈解

首先我們用迴圈解：

function fib(n) {
  const result = [0, 1];

  for (let index = 2; index <= n; index++) {
    // 倒數第一個數
    const a = result[index - 1]; // or result[result.length -1]

    // 倒數第二個數
    const b = result[index - 2];

    result.push(a + b);
  }
  console.log('full array: ' + result)
  console.log('last number: ' + result[result.length -1])
  return result[result.length -1];
}

用迴圈解，n 增加會多跑一次迴圈，因此時間複雜度是線性的(Linear Run Time)。

js 遞迴解(Recursion)

如下：

function fib(n) {
  if (n < 2) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

用遞迴解做了以下事情(ex: fib(5))

fib(5) 會去做 fib(4)與 fib(3)

fib(4) -> fib(3) -> fib(2) -> fib(1), fib(0) -> 1
       -> fib(1) -> 1
       
       -> fib(2) -> fib(1), fib(0) -> 1

fib(3) -> fib(2) -> fib(1), fib(0) -> 1
       -> fib(1) -> 1

所以只是fib(5)，共呼叫了 15 次 fib(x) ，因此在費氏數列的問題上，遞迴是時間複雜度比較差的。

因為他接近指數時間(Exponential Time)。

Java 解法

Java 迴圈解

private static int fib1(int n) {
        int theLastTwo = 0, theLastNum = 1, temp; 
        
        if (n == 0) 
            return theLastTwo; 
        
        for (int index = 2; index <= n; index++) { 
            temp = theLastTwo + theLastNum; 
            theLastTwo = theLastNum; 
            theLastNum = temp; 
        } 
        
        System.out.println("the Last Two " + theLastTwo);
        System.out.println("the Last Number " + theLastNum);
        return theLastNum; 
    }

Java 遞迴解

public class FibonacciEx1 {

    static private int fib(int n) {
        if (n <= 1)
            return n;
        
        return fib(n - 1) + fib(n - 2);
    }


    public static void main(String[] args) {
        System.out.println(fib(5));
    }

}

此文同時發佈於鐵人賽。