3月 06, 2010

【演算】複雜度分析 - 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),若且唯若存在一正整數 n0 與 c > 0,使得所有整數 n ≥ n0 都滿足 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),若且唯若存在一正整數 n0 與 c > 0,使得所有整數 n ≥ n0 都滿足 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),若且唯若存在一正整數 n0, c1與 c2 > 0,使得所有整數 n ≥ n0 都滿足 c1g(n) ≤ f(n) ≤ c2g(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),若且唯若存在一正整數 n0 與 c > 0,使得所有整數 n ≥ n0 都滿足 0 ≤ f(n) < cg(n),則 f(n) ∈ ο(g(n))。

  對於兩個非負函數 f(n) 與 g(n),若且唯若存在一正整數 n0 與 c > 0,使得所有整數 n ≥ n0 都滿足 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. 對於演算法所使用的記憶體空間,通常也是如此。

3 回覆:

匿名 提到...

非常感謝您的文章
很高興能來到你的blog^_^
祝您有個愉快的一天&聖誕快樂^_^

Unknown 提到...

您好,我的文章能對您有所助益是我的榮幸

也祝您聖誕佳節愉快 :)

hi 提到...

it's good man!

張貼留言