渐近符号的比较

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。算法简介。