Day 02 七天學會基本演算法(二)淺談演算法複雜度與費波那契數列


Day 02 七天學會基本演算法(二)淺談演算法複雜度與費波那契數列

前言

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

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

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

我們首先舉一個例子,假設今天我們想要求出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次計算 => O(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;
}

演算法的比較

上面兩個演算法在n很小的時候,都能很快計算出來,但當n = 64的時候,你會發現遞迴的演算法執行後遲遲沒有結果,但迭代的算法卻還是能很快地算出來。

這樣的原因是什麼呢? 其實就是因為遞迴的算法要進行計算的次數太多了,以下列的圖來看,光fib(5),就會呼叫15次函式,約略於2^5 - 1次,時間複雜度為O(2^n),是以指數型的速度在成長。

相對的,第二個演算法只使用for迴圈進行n次的計算,因此時間複雜度僅為O(n)級別,O(n) 與O(2^n)級別差距到底多大呢?

如果有一台1GHz的普通計算機,運算速度10^9每秒,O(n) 大約耗時6.4*(10^-8)秒,但O(2^n)卻需要584.94年,非常可觀,因此有時候算法設計的差距,會比硬體設備影響來地大上許多。

總結

今天介紹了時間複雜度和費波那契數列,希望內容對大家有幫助,明天會從排序演算法開始。






演算法是找軟體相關工作時一定會被問到的問題,也是幫助自己寫程式更增進效能與技巧的思考方式,希望透過這個系列文撰寫基本演算法的介紹,內容包含:堆疊、排序、搜尋、分治、動態規劃等內容。

留言討論