複雜度(Complexity)& 漸近符號(Asymptotic Notation)


「漸近符號(asymptotic notation)」包含大 O 符號(Big O notation)、大 Ω 符號(Big Omega notation)與大 θ 符號(Big Theta notation)等,可以用來表示一演算法的時間複雜度(time complexity),進而探討該演算法的好壞。


複雜度(complexity)

表示一演算法的效能,複雜度越低,代表演算法越好。

空間複雜度(space complexity)

演算法需要的記憶體空間,一般較少探討。

時間複雜度(time complexity)

演算法完成運算需要經過的時間,但這裡的「時間」不是用計時器去算幾分幾秒,主要有下列兩個原因:

  1. 同一電腦多次完成相同運算,每次的耗時不一定相同。
  2. 不同電腦有各自的硬體條件,完成同一運算的耗時也不會相同。

因此,探討一演算法的時間複雜度,看的是「運算元數量」,運算元越多,代表需要經過越多次的計算,時間複雜度較高。

時間複雜度範例:等差級數

計算等差級數時,可用迴圈將數字一一加總,也可直接套公式。以下比較兩方法的運算元數量:

  1. 迴圈解:1+2+...+n 依序往上加,共要加總 (n–1) 次,有 (n–1) 個運算元。
  2. 公式解:[(1+n)‧n]/2,不管數字多大,都只有「+」、「x」、「/」3 個運算元。

由此可知,套公式的運算元數量明顯較少、時間複雜度較低,兩者的差別將隨 n 的值逐漸變大而越來越明顯。


漸近符號(asymptotic notation)

使用一簡單的時間函式表示「代表演算法趨勢之函式」的集合。

大 O 符號(Big O notation)

最常用來探討演算法時間複雜度的指標,關注的是「最糟情況」下的運算次數,對時間複雜度影響較小的項目都不在考量範圍,因此,評估任一演算法的「Big O」時,有下列三規則:

  1. 常數忽略不記,任一項次係數皆視為1
  2. 較低次方者忽略不記
  3. 對數底數忽略不記

以上述「等差級數」範例來說,大 O 值分別如下:

  1. 迴圈解:有 (n–1) 個運算元,但較低次方的常數項 (–1) 忽略不記,因此時間複雜度為 O(n)。
  2. 公式解:有 3 個運算元,但常數的值 3 不影響,因此時間複雜度為 O(1)。

「Big O」比較

對於任一演算法而言,若其「Big O」的值未隨 n 變大而急遽上升,代表它的時間複雜度低,是好的演算法。各類常見演算法的「Big O」有下列優劣關係:

較常見的「Big O」比較圖示如下:

常見「Big O」比較圖(修改自 devopedia


「Big O」正式定義

f(n)=O(g(n)),若且唯若存在正實數 c、正實數 n₀,對於所有的 n≥n₀,可滿足 0 ≤ f(n) ≤ c·g(n)

這定義讓人看得眼花撩亂、不知所云,我們可以改用座標圖理解。
現有兩函數 f(n)、g(n) 如下:

將 g(n) 乘上一個正實數 c,會大致變成下面這樣:

對於所有的 n≥n₀,0≤f(n)≤c·g(n),也就是只要在 n₀ 以上,f(n) 永遠比 c·g(n) 小,c·g(n) 表示 f(n) 的上界(upper bound),此時 f(n) 被定義為 O(g(n)),這個 O(g(n)) 就是「Big O」。


大 Ω 符號(Big Omega notation)

「Big Ω」跟「Big O」十分相似,但是用來表示 f(n) 的下界(lower bound),定義如下:

f(n)=Ω(g(n)),若且唯若存在正實數 c、正實數 n₀,對於所有的 n≥n₀,可滿足 0 ≤ c·g(n) ≤ f(n)

現假設有 f(n)、g(n) 如下:

將 g(n) 乘上一個正實數 c,大致變成下面這樣:

跟「Big O」不一樣的是,當 n≥n₀,f(n) 變成永遠在 c·g(n) 的「上方」,0≤c·g(n)≤f(n),f(n) 永遠比 c·g(n) 大,c·g(n) 表示 f(n) 的下界(lower bound),此時 f(n) 被定義為 Ω(g(n)),這個 Ω(g(n)) 就是「Big Ω」。


大 θ 符號(Big Theta notation)

「Big θ」是「Big O」與「Big Ω」的綜合體,同步找出 f(n) 的上界與下界,定義如下:

f(n)=θ(g(n)),若且唯若存在正實數 c₁、正實數 c₂、正實數 n₀,對於所有的 n≥n₀,可滿足 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)

現假設有 f(n)、g(n) 如下:

將 g(x) 乘上 c₁、c₂ 後,大致變成下面這樣:

當 n≥n₀,f(n) 變成永遠在 c₂·g(n) 的「下方」、c₁·g(n) 的「上方」,0≤c₁·g(n)≤f(n)≤c₂·g(n),f(n) 永遠在 c₁·g(n) 及 c₂·g(n) 之間,此時 f(n) 被定義為 θ(g(n)),這個 θ(g(n)) 就是「Big θ」。


「Big O」、「Big Ω」、「Big θ」比較

  1. 「Big O」:只看上界,即所有時間複雜度較高的情況。
  2. 「Big Ω」:只看下界,即所有時間複雜度較低的情況。
  3. 「Big θ」:同時看上界與下界。

假設 f(n)=θ(n),則三種漸近符號可同時表示如下:

在實際比較演算法的時間複雜度時,多半只會探討「所有較糟可能中的最佳情形」,也就是「上界中的最小者」,因此只會探討所有「Big O」中最小的值,否則每種演算法的「Big O」都可以取 O(nⁿ),如此便沒有比較意義。


參考資料

  1. 初學者學演算法|談什麼是演算法和時間複雜度
  2. Complexity:Asymptotic Notation(漸進符號)

*根據「國家教育研究院雙語詞彙、學術名詞暨辭書資訊網」,「asymptotic」的中文為「漸近的」,因此「asymptotic notation」翻譯應為「漸近符號」。

#資料結構 #演算法 #複雜度 #漸近符號







你可能感興趣的文章

VSCode 中使用typescript檢視output - Code Runner套件

VSCode 中使用typescript檢視output - Code Runner套件

BootStrap5 第一章 : 載入

BootStrap5 第一章 : 載入

Python設計概論

Python設計概論






留言討論