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

Question

4

我正在开发一些算法，它的时间复杂度为O(log^3 n)。(注：虽然大写O也可以，但请将O解释为Big Theta)

我不确定O(log^3 n)，甚至是O(log^2 n)，与O(n log n)相比哪个更/少/相等地复杂。

如果我直接按照规则进行，我会说O(n log n)更为复杂，但是我仍然不知道为什么或如何得出这个结论。

我已经做了一些研究，但是我还没有找到这个问题的答案。

非常感谢。

- user1320847

4

log^3(100000) 与 1000000*log(1000000) 哪个更大？ - mbeckish

nlogn比log^2n更复杂，例如如果我们有N等于1024，那么我们有102410>1010（以2为底的对数）。 - Iłya Bursov

1

@JohnKugelman，你应该把这个作为答案发布。 - Ridcully

@JohnKugelman 绝对正确。请将其发布为答案。 O(n log n) 作为贪心算法是否可接受？ - user1320847

2个回答

9

如果您将两个函数绘制在一起，您会发现n log(n)增长速度比log³ n快。

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

- John Kugelman

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kennytm · Accepted Answer

因此，（n log n）比（（log n）³）“更大”。这可以通过归纳法轻松地推广到（（log n）^k）。