【演算】複雜度分析 - Complexity Analysis

　　在演算法簡介中，我們提到了「找電話」問題的兩個演算法：分別為「依序找」跟「按筆劃找」。我們可以知道，對於相同的問題，可能會同時存在許多不同的解法。然而在這種擁有多種可能解法的情況下，我們理應對這些演算法進行評估，並從中選擇一種最有效的方式。



　　從比較執行時間的層面來看，或許你會想到：直接利用計時器來比較不同演算法實現程式的執行時間。但是，這種方式的變因太多。實作演算法的程式語言、記憶體大小、不同的編譯（直譯）器、甚至是電腦中運行的程式，可能都會影響計時所得的結果。相對的，這種方式也就顯得不太準確。

　　除了實際去計時之外，我們也可以假設演算法中「每一步」的執行時間都相同。於是，我們也可以直接拿演算法所有「步驟」的執行次數總和來進行比較。



　　讓我們同樣以「依序找電話」演算法為例。

　　先考慮在最差情況（worst case）下（也就是欲尋找的電話號碼不在電話簿中，因為你必須搜遍整本電話簿），「依序找電話」虛擬碼每行敘述的執行次數如下（方便起見，我們以變數 n 代表電話簿的大小 phoneBook.size）：

Input name                                          // 1
While True do                                       // n
    If index > phoneBook.size then                  // n
        Output "phone number not found"             // 1
        Break loop                                  // 1

    If phoneBook.record[index].name = name then     // n
        Output phoneBook.record[index].phone        // 0
        Break loop                                  // 0

    index = index + 1                               // n

　　因此在最差情況下，每行敘述的執行次數總和：W(n) = 1 + n + n + 1 + 1 + n + 0 + 0 + n = 4n + 3。

　　由此可以發現，一個演算法的執行時間通常會隨著輸入資料的大小 n 的成長而成長（註1）。而這個與資料大小 n 相關的時間（或空間）函數，則稱為這個演算法的複雜度（complexity）。



　　不過，我們還可以用更簡明、更具數學意義的方式來表達它。

　　首先，我們可以知道當 n 是一個相當大的數字時，4n 是遠大於 3 的。換句話說，就是我們只需要保留函數的最高項，也就是這個例子中的 4n。而若是只想考慮其函數的成長趨勢，我們甚至可以連其係數一併省略，只注意 n 這個部份，代表這個演算法是一個線性時間（linear time）的演算法，記作 O(n)。



　　Ο（big-omicron，或是稱作 big-O）是一個漸進符號（asymptotic notation），代表了函數的漸進上限（asymptotic upper bound）。其定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ f(n) ≤ cg(n)，則 f(n) ∈ Ο(g(n))。

　　簡單來說，若是我們說一個演算法的複雜度函數 f(n) ∈ Ο(g(n))，就代表函數 f(n) 的成長趨勢與 g(n) 相似或是更慢的。



　　除了 big-omicron 之外，我們還可以使用 Ω（big-omega）、Θ（big-theta）、ο（little-omicron）與 ω（little-omega）來表達一個演算法的複雜度。

　　big-omega 代表了函數的漸進下限（asymptotic lower bound）。簡單來說，若是我們說一個演算法的複雜度函數 f(n) ∈ Ω(g(n))，就代表 f(n) 函數圖形的成長趨勢與 g(n) 相似或是更快的。其正式的定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ cg(n) ≤ f(n)，則 f(n) ∈ Ω(g(n))。

　　那麼 big-theta 呢？其實，big-theta 也就相等於 big-omicron 與 big-omega 的交集，也就是 Θ(g(n)) = Ο(g(n)) ∩ Ω(g(n))，代表 f(n) 函數圖形的成長趨勢與 g(n) 是相似的。其正式的定義如下：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀, c₁與 c₂ > 0，使得所有整數 n ≥ n₀ 都滿足 c₁g(n) ≤ f(n) ≤ c₂g(n)，則 f(n) ∈ Θ(g(n))。

　　而 little-omicron 與 little-omega 則分別為 big-omicron 與 big-omega 和 big-theta 的差集，即 ο(g(n)) = Ο(g(n)) - Θ(g(n)), ω(g(n)) = Ω(g(n)) - Θ(g(n))。以下為其正式定義：

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ f(n) < cg(n)，則 f(n) ∈ ο(g(n))。

　　對於兩個非負函數 f(n) 與 g(n)，若且唯若存在一正整數 n₀ 與 c > 0，使得所有整數 n ≥ n₀ 都滿足 0 ≤ cg(n) < f(n)，則 f(n) ∈ ω(g(n))。

　　為了方便比較，我們可以將 f(n) 與 g(n) 比擬成 a 跟 b，則：

• f(n) ∈ Ο(g(n)) ≈ a ≤ b
• f(n) ∈ Ω(g(n)) ≈ a ≥ b
• f(n) ∈ Θ(g(n)) ≈ a = b
• f(n) ∈ ο(g(n)) ≈ a < b
• f(n) ∈ ω(g(n)) ≈ a > b

　　雖然存在這麼多種漸進符號以表達演算法的複雜度，但是一般來說，當我們分析一個演算法的複雜度，比較常使用 big-omicron 來表達估算後的結果。這是因為對於一個演算法，其所耗費的時間（或是記憶體）上限，通常才是我們需要關注的重點。

註1. 對於演算法所使用的記憶體空間，通常也是如此。