算法复杂度，log^k n vs n log n

Question

我正在开发一些算法，占用O（log^3 n）。 （注：以O作为Big Theta，尽管Big O也可以）

我不确定，而O（log^3 n），甚至O（log^2 n）被认为是更多/更少/ equaly复杂为O（n log n）。

如果我要严格遵守规则，我会说O（n log n）是更复杂的规则，但是我仍然没有任何线索知道为什么或如何。

我已经做了一些研究，但我一直未能找到这个问题的答案。

非常感谢。

Answer 1

因此（N log n）的比（（log n）的） “更大”。这可以通过归纳容易地推广到（（log n）^k）。

Answer 2

如果graph the two functions together你可以看到，ñ日志（ñ）增长高于登录 ñ更快。

为了证明这一点，你需要证明ň日志ň>登录 ñ为比一些任意数量Çň更大的所有值。找到这样一个c，你有你的证据。

实际上，n log(n) grows faster than any log^xn为正数x。