漸近符號的比較

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 文件 StackOverflow 文件 StackOverflow 文件

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

連結

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