漫談算法（番外篇）：算法複雜度符號體系完全指南（O、Ω、Θ、o、ω）

作者：劉子韜

漸近符號核心定義

本文不區分 log 和 lg，均指以 2 為底對數。所有符號描述函數增長階而非具體值。

1. 大 O 符號（上界）

定義：O(g(n)) = { f(n) : ∃ 正常數 c, n₀, ∀ n > n₀, 0 ≤ f(n) ≤ c·g(n) }

含義：g(n) 是 f(n) 的漸近上界。f(n) = O(g(n)) 實際表示 f(n) ∈ O(g(n))。

2. 大 Ω 符號（下界）

定義：Ω(g(n)) = { f(n) : ∃ 正常數 c, n₀, ∀ n > n₀, 0 ≤ c·g(n) ≤ f(n) }

含義：g(n) 是 f(n) 的漸近下界。

3. 大 Θ 符號（緊確界）

定義：Θ(g(n)) = { f(n) : ∃ 正常數 c₁, c₂, n₀, ∀ n > n₀, c₁·g(n) ≤ f(n) ≤ c₂·g(n) }

含義：f(n) 同階於 g(n)，上下界同階。

4. 小 o 符號（非緊確上界）

定義：o(g(n)) = { f(n) : ∀ 正常數 c, ∃ n₀, ∀ n > n₀, 0 ≤ f(n) < c·g(n) }

關鍵差異：大 O 要求「存在某個 c」，小 o 要求「對任意 c 都成立」。即 f(n) 增長嚴格慢於 g(n)。

極限視角：lim_n→∞ f(n)/g(n) = 0 ⇔ f(n) = o(g(n))

5. 小 ω 符號（非緊確下界）

定義：ω(g(n)) = { f(n) : ∀ 正常數 c, ∃ n₀, ∀ n > n₀, 0 ≤ c·g(n) < f(n) }

極限視角：lim_n→∞ f(n)/g(n) = ∞ ⇔ f(n) = ω(g(n))

直觀理解：增長率視角

• f = O(g) ：f 增長不超過 g（≤）
• f = Ω(g) ：f 增長不低於 g（≥）
• f = Θ(g) ：f 與 g 同階（=）
• f = o(g) ：f 增長嚴格慢於 g（<）
• f = ω(g) ：f 增長嚴格快於 g（>）

常用數學公式速查表

1. 等比級數：Σ_i=0ⁿ rⁱ = (rⁿ⁺¹-1)/(r-1) (r≠1)
2. 調和級數：H_n = Σ_i=1ⁿ 1/i = ln n + γ + o(1)
3. 對數恆等式：log_ab = log_cb / log_ca
4. Stirling 公式：n! = √(2πn) (n/e)ⁿ (1 + Θ(1/n))
5. 二項係數上界：C(n,k) ≤ (en/k)ᵏ
6. 主定理通用形式：T(n) = aT(n/b) + f(n)

實戰應用提示

• 分析算法複雜度時，先確定遞歸式或迴圈結構
• 用遞歸樹或主定理求解遞歸式
• 證明下界常用決策樹或對手論證
• 小 o/ω 用於精確表達「嚴格快於/慢於」關係
• 面試/考試中，大 O/Θ 最常用，小 o/ω 體現深度理解

總結

漸近符號是算法分析的語言。大 O/Ω/Θ 刻畫上下緊確界，小 o/ω 刻畫非緊確界。極限定義提供直觀判斷工具。熟練掌握定義、圖形含義、極限關係與常用公式，是算法分析基本功。