漸近符號的比較

Created: November-22, 2018

讓 f(n) 和 g(n) 是在正實數集上定義的兩個函式，c, c1, c2, n0 是正實常數。

符號	`f(n)`= O（`g(n)`）	`f(n)`=Ω（`g(n)`）	`f(n)`=Θ（`g(n)`）	`f(n)`= o（`g(n)`）	`f(n)`=ω（`g(n)`）
正式定義	`∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤` f(n) `≤ c g(n)`	`∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c` g(n) `≤ f(n)`	`∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1` g(n)`≤`f(n) `≤ c2 g(n)`	`∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤` f(n) `< c g(n)`	`∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c` g(n) `< f(n)`
`f, g` 與實數 `a, b` 的漸近比較之間的類比	`a ≤ b`	`a ≥ b`	`a = b`	`a < b`	`a > b`
例	`7n + 10 = O(n^2 + n - 9)`	`n^3 - 34 = Ω(10n^2 - 7n + 1)`	`1/2 n^2 - 7n = Θ(n^2)`	`5n^2 = o(n^3)`	`7n^2 = ω(n)`
圖解

漸近符號可以在維恩圖上表示如下： StackOverflow 文件

連結

Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein。演算法簡介。