asymptotics - O((n^2)*log(n)) 是否大于 O(n^(2.5))？

Question

我知道 $O(n^2\times\log(n))$ 大于 $O (n^2)$，但 $O(n^2\times\log(n))$ 大于 $O(n^{2.5})$?

Answer 1

为了比较 2 个复杂性，只需计算它们的比率限制，如下所示:

$\displaystyle\begin{align*}\lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}} &=\lim_{n\to\infty}\frac{log(n)}{\sqrt{n}} =\lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}} =\lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}}\\ &\下置{\左| k =\sqrt{n}\right|}{=} \\\lim_{k\to\infty}\frac{2log{(k)}}{k} = 2\lim_{k\to\infty}\frac{log{(k)}}{k}\\ &\leq 2\lim_{k\to\infty}\frac{ln{(k)}}{k}\\ &\overset{\ast}{=} 2\lim_{k\to\infty}\frac{(ln{(k))'}}{k'} = 2\lim_{k\to\infty}\frac{\frac{1}{k}}{1} = 2\lim_{k\to\infty}\frac{1}{k}\\ &=0\end{对齐*}$

我们使用L'Hôpital's rule简化计算 * 处 $\frac{\ln(k)}{k}$ 的限制。

如您所见，$O(n^2\times\log(n))$ 低于另一个。