假設我們有一個排序好的array int[] A如下：

[-3, -1, 2, 4, 4, 8, 9, 11]

我們希望知道A存不存在兩個index i, j 使得A[i] = A[j]。

假若我們用以下的方法來實作：

for(int i = 0; i < A.length; i++){
    for(int j = i + 1; j < A.length; j++){
        if(A[i] == A[j]){
            return true;
        }
    }
}
return false;

也就是把每一個pair都抓出來比較有沒有一樣的，當找到一樣的就return true，反之return false。

請問該如何表達這個演算法的效能如何？

最直觀的做法就是拿個碼表，然後執行看看，記錄執行了多久。可是這個做法會有電腦效能的差異，我們也很難確保這次量測時跟下次量測其他演算法時，電腦硬體上造成的變因沒有任何改變。那如果去計算電腦要去執行的動作有哪些以及幾次呢？

這時我們就要捲起衣袖，把每個電腦要操作的動作都列下來；假設這個A.length = 10000，並且計算各個動作會進行幾次，如下表：

只要把要比較的演算法都做出這個表，並假設都一樣要跑A.length=10000，就可以比較出哪個演算法要執行比較少動作，也就一定是效能比較好的演算法。

但其實我們也可以把這個10000改成用一個N來表示，讓表示式變得更general：

這時候我們可以知道，當N是一個很大很大的數值時，其實真正影響效能的只會是N ^ 2，因為在N非常大的時候，N ^ 2增長的速度(order of growth)會遠大於其他不管是N或是1/2的影響。

Asymptotic翻成中文是”漸進的”，而這個詞用在演算法上可以理解成我們要去找出當演算法跑一個很大很大的N資料量時，結果會趨近於什麼，就像是我們先從x=1丟進演算法，得出某個y值的執行時間，然後x=2, x=3, ……, 不斷漸進，漸進到當x = 超大的N 時會如何表示。

若我們把演算法用f(N)來代表，而asymptotic探討的就是該如何找到以下的關係：

k1 * Θ(N) < f(N) < k2 * Θ(N)

而如上面的範例所知，這邊的Θ(N)就等於N ^ 2。

那我們常常聽到的Big O是什麼呢？其實big O就是指 只考慮上界而不關心下界，在演算法上白話文就是只關注最壞的情況N的表示式是什麼，描述這種情形我們就稱為O(N)，反之關注最佳情形的下界表示式稱為Ω(N)。

值得注意的是，Big O有個邏輯上的陷阱，由於O(N)這個符號只要符合以下就成立：

f(N) < Big O

所以以下狀況的Big O都是對的：

理應有效力的探討Big O的話，會是O(N ^ 4)，但是其他order of growth更大的Big O表示式你也不能說他錯哦～

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License