前言

今天將從複雜度開始講解，並舉出費波那契級數的例子來幫助我們更加理解演算法影響效能的重要性。

如何評判一個演算法的好壞？

當我們想要評估一個算法的好壞時，其實有很多方法，比方說我們可以比較不同的算法對同一組輸入的執行處理時間，稱作「事後統計法」，但這樣的方法明顯會根據硬體設備不同及運行時不確定的環境而產生時間上的不同，因此我們常用另一種方法「時間複雜度」來進行指令執行次數的估算。

我們首先舉一個例子，假設今天我們想要求出1+2+3+...+n，那我們可以用下列算法：

（一）迭代算法

int sum = 0; // 計算一次
for(int i = 1; i <= n ;i++){
    sum += i; // 共計算了n次
}

當然我們也可以使用我們之前學過的數學公式來算：

（二）數學公式

(1 + n) * n / 2; // 計算一次

這兩個算法求得的答案是一樣的，但是在效能上（二）卻遠高過（一），原因是（一）要經過n次以上的計算才能求得答案，（二）卻只要計算一次就能得到答案。

BigO

我們一般用大O表示法來描述複雜度，它表示的是數據規模n對應的複雜度，它有以下的特點：

常忽略常數、係數，因為當n大到一定的程度時，我們可以不用管它
- 9 表示為 O(1)
- 2n+3 表示為O(n)
- n^2 + 2n + 6 表示為O(n^2) 因為當n非常大時，2n是影響不大的

以下舉幾個例子計算BigO

(1)

public static void test1(int n) {
    // 1次計算
    if (n > 10) { 
        System.out.println("n > 10");
    } else if (n > 5) { // 2
        System.out.println("n > 5");
    } else {
        System.out.println("n <= 5"); 
    }
    // 4次計算
    for (int i = 0; i < 4; i++) {
        System.out.println("test");
    }

    // 共5次計算 => Ｏ(1)

}

(2)

public static void test2(int n) {
    for (int i = 0; i < n; i++) { // n次
        for (int j = 0; j < 15; j++) { // 常數次
            System.out.println("test");
        }
    }
    // O(n*常數) => O(n)
}

(3) 指數

public static void test3(int n) {
    for (int i = 1; i < n; i = i * 2) {
        // i = 1, 2,4,8,16 = 2^k
        //  2^k > n
        // k > log2(n)
        // 因此時間複雜度為O(logn);
        System.out.println("test");
    }
}

從上面的例子可以大略知道如何計算演算法的Big O 階級，但目前這樣看感覺還沒有什麼太大的時間差異，都是電腦一下子就能跑完，因此我們舉出費波那契級數來看複雜度對於演算法的影響。

費波那契級數（Fibonacci)

費波那契級數是一個義大利人費波那契在描述兔子生長的數目：

第一個月有一對兔子誕生
過了一個月後，他們會變成成年的兔子，可以進行生育
之後的每月，每一對都可生育一對兔子
兔子不會死亡

因此可以看下面這張圖，每一列是新的一個月，而當月份的總兔子數量則是列上的兔子數量，因此請問一個月後，會有多少對兔子？

fibonacci: 1, 1, 2, 3, 5, 8....

以簡單的數學推倒我們可以很快找到它的規律，第一個月以n = 0表示

fib(0) = 1 // 第一個月只有一對兔子
fib(1) = 1 // 第二個月也只有一對兔子
fib(2) = 2 
fib(3) = 3 = fib(1) + fib(2)
fib(4) = 5 = fib(3) + fib(2)
   .
   .
   .
fib(n) = fib(n-1) + fib(n-2)

則我們很直觀地可以使用演算法來解這一道題目：

（ㄧ）使用遞迴的方式

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

（二）使用迭代的方式

迭代的方式是使用兩個變數f,s分別紀錄fib(n-1)與fib(n-2)，初始化為1，當每計算一次級數後，這兩個指標就會個字向右移一格。

private int fib2(int n){
    if(n <= 1){
        return n;
    }
    int first = 1;
    int second = 1;
    int sum = 0;
    for(int i = 0; i < n-1; i++){
        sum = first + second; // sum為前兩個數字相加
        first = second; // 運算完sum之後，first移到second的位置
        second = sum; // second移到first的位置
    }
    return sum;
}