算法导论笔记：渐近大于和多项式大于

转自：http://stackess.leanote.com/post/5131774ba20f

$f(n)$渐近大于 $g(n)$，记作 $f(n)=ω(g(n))$

$f(n)$ is polynomially bigger than $g(n)$when $f(n)$ asymptotically dominates $g(n)$ even after we multiply $g(n)$ by a very small order polynomial (e.g., $n^{0.00001}$).参考

$f(n)$多项式大于$g(n)$

1. $nlog2n$只渐近大于$n$，因为虽然$\lim_{n \rightarrow \infty} \frac{n\log_2n}{n} = \infty$，但对任意常数 $ϵ>0$,$\lim_{n \rightarrow \infty} \frac{n\log_2n}{n^{1+\epsilon}} = 0$
2. $2n$非渐近大于$n$，因为 $\lim_{n \rightarrow \infty} \frac{2n}{n} = 2$，即实际上$2n=O(n)$$n$是渐近紧确的界。
3. $n\log_2nn$多项式大于 $n^{\log_4 3}$，因为存在常数$ϵ=0.2$$\log_4 3+\epsilon = 0.99$，则$\lim_{n \rightarrow \infty} \frac{n\log_2n}{n^{\log_4 3+\epsilon}} = \infty$
4. $n^2$多项式大于$n\log_2 n$，因为存在常数$ϵ=0.9$，则$\lim_{n \rightarrow \infty} \frac{n^2}{n^{1+\epsilon} \log_2 n} = \infty$

$f(n)$渐近小于$g(n)$，也记作$f(n)=o(g(n))$

$f(n)$多项式小于$g(n)$