#1 BIG O - 有關程式執行的快慢

如果前面的文章所提，在十多年前時我還沒有電腦科學的基礎知識，在當時很難辦別自己寫的程式是不是好的，後來念書了之後才知道原來在課本裡有一些理論的方法來讓你做評估，而這篇文章的主題就是要來談這項評估.  評估的方法不只一種，而且還有一些數學推論，不過我將會儘量跳過數學推論的部份，而且只談論業界中最流行的一種評估方法，它叫做 O (我們將它念成 big O).

O 的數學基礎是你的程式所需執行的時間會因為輸入參數的不同而有所變化，比如你有一個程式要算1+2+3+4+5的答案，若你懂基本的程式，你就知道輸入參數是5，然後寫一個 loop 來做 5 次的加法就可以得到最後的答案. 一旦你的輸入參數是 10，那麼你寫的那個 loop 的內容就會執行十次.

int answer=0;
for (int i = 1; i <= n ; i++ ) {
     answer += i;
}

所以以上的程式就可以用一個數學的多項式來表達所需要執行的步驟. 以此例子來說是 f(n) = n ，所以 n = 5 時，程式要做 5 次加法, n=10 時，程式要做 10次加法. 如果以 n為x軸，以加法次數為y軸時，你就可以為這程式畫出一條線. O 的方法就是找一個比你的程式 f(n) 還要高一點的g(n)，所謂高一點就是從 x,y軸的位置來看，所以我們稱g(n)為f(n)的上限，講白話一點就是不會超過g(n)，所以g(n)可以視為程式在執行時最費時的情況，不會再比它更慘了，所以才叫做上限. 然後當輸入參數漸漸變大，就會發現g(n)和f(n)會越來越接近.

因此，O就是找出上述的 g(n).

所以，我們在評估程式時很難去用執行時間來評估，因為不同的電腦架構和程式語言都會影響，我們也不會用程式寫了幾行來評估，而是用上述的方法來評估.

在課本上，我們稱它為時間複雜度 (Time Complexity)，在業界中最常用 O 來表達，所以當你使用一些業界的 SDK 時，有時你會看到某個 API 是多少的 O，比如O(n), O(n²)等等.

以上是比較偏向用數學的角度來解釋，接下來我們用更簡單的方法來說明找出一個程式的 O.

int FindSum2(int n) {
    int answer = 0;
    int n = n + 1;
    for( int i = 1; i <= n ; i++) {
        answer = answer + i;
    }
    return answer;
}

上面這一個 FindSum2() 跟上面的程式幾乎一樣，只是有一個小小的變化，在 for 之前多了一個 n = n +1; 所以你可以看到當你輸入 n = 0 時，會執行一次的加法, n=1時，會執行二次加法，以此類推，當 n 越來越大時，加法執行的次數就是 n+1. 所以這個程式就是 O(n+1)，通常我們會忽略掉一些舉無輕重的執行次數，因為當你的 n 變的很大很大的時候，後面那一個 +1 似乎就變的相當不起眼，因此我們會直接說 O(n).

寫程式有趣的地方就是在這裡，因為當程式的輸入參數很小時，程式都能表現的很好，但程式寫的好不好就看它在輸入參數很大時的表現了. 相信大家在業界工作時，在許多項目都會有這樣的感覺，就像網路上只有十台電腦時，網路速度還蠻快的，但變成一百台電腦時，事情就不一樣了.

另外，我們再來看一個例子

int FindSum3(int n) {
    int answer = 0;
    for( int i = 0 ; i < 10 ; i++ ) {
        answer = answer + 2;
    }
    for( int i = 1; i <= n ; i++) {
        answer = answer + i;
    }
    return answer;
}

上面的 FindSum3() 和 FindSum2() 相差了一個 for loop. 我們可以用上述的觀念做找出 FindSum3() 的 O. 你認為是多少呢?

是的，他們兩個是一樣的! 也許你會說這兩個明明是不一樣的，執行的加法次數也不一樣，沒錯，他們執行的加法次數的確不一樣，誠如之前所說，一旦 n 變的很大時，其實也可以說是一樣的，比如執行十億次的加法和執行十億又十次的加法所需的時間，你覺得你會在乎那十次嗎? 我想你比較在乎十億次才對. 所以，到這裡你就可以知道 O 所要表達的並不是一個精確數字的情況，它所要表達的是一個趨勢.

我們再來看看另外一個例子.

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = 0 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

FindSum4() 輸入參數是一個陣列 ary 和一個數字 target，要來找出陣列裡是否有兩個元素的和等於 target. 猜猜，FindSum4() 的 O 是多少? 記得，在 FindSum4() 中，那一個參數會影響它的執行時間? 沒錯，就是陣列，陣列如果很短，程式執行時間也短，陣列如果很長，執行時間也較長，你看到有兩個 for loop, 而 loop 裡面的內容要執行幾次完全是由陣列的長度所決定 (ary.length)，所以你可以把陣列的長度來做當 n，而 FindSum4() 的 O 是 n². 答對了嗎 ? 所以，如果你可以想到另一種程式寫法只要 O(n)，那麼你的程式在時間複雜度上就打敗了我寫的 FindSum4()，也因為如此，我們才能說你想到的那個程式執行的比我的 FindSum4() 還要快.

以上是我們用加法執行的次數為例子來說明 O，簡單的運算用來表達執行次數是很單純的，所以千萬別以為所有的程式都可以這樣分析，因為你還要確定你所呼叫的每個 API 是不是都像加法那樣單純. 因為現在許多高階的程式語言，像java, C#等，都包裝的很好，有時你並不會看到內部的運作機制，比如 string.Contains() 不像加法那麼單純，其實 Contains() 裡面很可能就會有一個 loop，而且這個 loop 執行的次數會取決於 string 的長短.

希望透過以上這些簡單的例子能讓你了解怎麼以時間複雜度的角度來看程式執行的好壞，同時也了解基本的 O，以及推論出 O 的函數值.