渐进记号的相关证明（使用极限的方式）

⎧⎩⎨⎪⎪⎪⎪⎪⎪ limf(n)g(n)>0⇔f(n)=Θ(g(n))limf(n)g(n)=0⇔f(n)=o(g(n)) $$/left/{/begin{split}//lim/frac{f(n)}{g(n)}>0/quad /Leftrightarrow /quad f(n)=/Theta(g(n))///lim/frac{f(n)}{g(n)}=0/quad /Leftrightarrow /quad f(n)=o(g(n))/end{split}/right.$$

1. 证明 nlogn=o(n1+ϵ)$n/log n=o(n^{1+/epsilon})$

nlognn1+ϵ=lognnϵ⇒lnxxϵ⇒1ϵxϵ⇒0 $$/frac{n/log n}{n^{1+/epsilon}}=/frac{/log n}{n^/epsilon}⇒ /frac{/ln x}{x^/epsilon} ⇒ /frac1{/epsilon x^/epsilon} ⇒ 0$$