f(n)=O(g(n))、f(n)=Ω(g(n))、f(n)=Θ(g(n))等的含义

f(n) = O(g(n)) 表示存在正常数 c 和 n0，使得当 n ≥ n0 时，f(n) 的值不超过 g(n) 的值的 c 倍。也就是说，f(n) 的增长率不会比 g(n) 的增长率快。

f(n) = Ω(g(n)) 表示存在正常数 c 和 n0，使得当 n ≥ n0 时，f(n) 的值至少为 g(n) 的值的 c 倍。也就是说，f(n) 的增长率不会比 g(n) 的增长率慢。

f(n) = Θ(g(n)) 表示存在正常数 c1，c2 和 n0，使得当 n ≥ n0 时，f(n) 的值在 c1 倍 g(n) 的值和 c2 倍 g(n) 的值之间。也就是说，f(n) 的增长率和 g(n) 的增长率是相等的，它们的渐进增长率相同。