algorithm - 算法复杂度，log^kn vs n log n

Question

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

我不确定，而 O(log^3 n)，甚至 O(log^2 n)，被认为与 O(n log n) 一样复杂/多/少/同样复杂。

如果我要立即遵守规则，我会说 O(n log n) 是更复杂的规则，但我仍然不知道为什么或如何。

我做了一些研究，但我无法找到这个问题的答案。

非常感谢你。

Answer 1

因此 (n log n) 比 ((log n) ³ )“大”。这可以很容易地通过归纳推广到 ((log n) ^k )。

Answer 2

如果将这两个函数绘制在一起，您可以看到n log( n ) 的增长速度比 log ³ n快。

为了证明这一点，您需要证明n log n > log ³ n对于所有大于某个任意数字c的n值。找到这样的c，你就有了证据。

事实上，对于正x ， n log( n ) 的增长速度比任何 log ^x n都快。