《算法导论》-- 渐进符号

1. Ο符号,表示一个上界

f(n)=Ο(g(n)) means there are consts c>0,n0>0,such that 0 <= f(n) <= c g(n) for all n>=n0, ex : 2n² = O(n³)
Other Ex:

• f(n) = n³+O(n²) means an error term

• n²+Ο(n)=O(n²) means for any f(n)∈Ο(n)
  here is an h(n)∈O(n²) such that n²+f(n)=h(n)

2. Ω符号 表示一个下界

f(n)=Ω(g(n)):
there exist consts c>0,n0>0,such that 0<=cg(n)<f(n)
for all n>= n0
Ex: n½ = Ω(㏒n)

3. Θ符号 表示一个集合

f(n)=Θ(g(n)):
means there are consts c1,c2>0,such that
c1g(n)<=f(n)<=c2g(n) for all n>0

4. ο符号

f(n)=ο(g(n)) means: lim(n->∞) f(n)/g(n) = 0;

5. ω符号

f(n)=ω(g(n)) means: lim(n->∞) f(n)/g(n) = ∞;