complexity-theory - 大O对小omega

Question

为什么 ω(n) 小于 O(n)？

我知道什么是小 omega(例如，n = ω(log n))，但我不明白为什么 ω(n) 小于 O(n)。

Answer 1

Big Oh 'O' 是上限，而 little omega 'ω' 是 Tight 下限。

O(g(n)) = { f(n):存在正常数 c 和 n0，使得 0 ≤ f(n) ≤ cg(n) 对于所有 n ≥ n0}

ω(g(n)) = { f(n):对于所有常数 c > 0，存在常数 n0 使得对于所有 n ≥ n0，0 ≤ cg(n) < f(n)}。另外:无穷大 = lim f(n)/g(n)

n ∈ O(n) 且 n ∉ ω(n)。或者:n ∈ ω(log(n)) 且 n ∉ O(log(n))