渐近符号的比较

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