n log n是O(n)吗？

Question

我正在尝试解决这个递归问题：

T(n) = 3 T(n/2) + n lg n ..

我得出的结论是它属于主定理第二种情况，因为n lg n是O(n^2)

但是在参考解决方案后，我注意到他们有以下解决方案：

解决方案表明n lg n = O ( n ^(lg 3 - e))，其中e介于0和0.58之间

所以这意味着n lg n 是O(n) .. 这正确吗？我有什么遗漏吗？

nlgn不是O(n^2)吗？

- Wael Awada

Answer 1

这将更好地解释事情

- Sreenath Nannat

---

谢谢您的努力。那么我猜 n lg n > O(n)，这本书错了吗？ - Wael Awada

@WaelAwada 这本书的答案并不与 O(n log n) > O(n) 相矛盾。 - Ilian

@WaelAwada 这本书的摘录看起来像是一种书面形式（如果不幸地交换了第一和第二项），用于说明简单支配函数的两个术语：n lg n 和 _n^logb a_。由于 n lg n 被 n 的任何大于一的幂次 支配，因此它被 n^lg 3 支配。 - greybeard

你从这里获取那张图表吗？http://bigocheatsheet.com 你应该注明出处！ - Lukas Eder

那个图表中O(nlogn)的紫色线是错误的。看看x轴上的100。它应该映射到100log(100) = 1002 = 200。但实际上在图表中它映射到了大约650。也许他们加入了一个常数乘数，但是他们没有为其他线这样做。很奇怪。 - Anssssss

这是Log2(100)约等于7。 - cognacc

Answer 2

n*log(n)不是O(n^2)。它被称为准线性，增长速度比O(n^2)慢得多。实际上，n*log(n)比多项式更小。

换句话说：

O(n*log(n)) < O(n^k)

当 k > 1 时：

以你的例子为例：

3*T(2n) -> O(n^1.585)

由于 O(n^1.585) 是多项式且支配 O(n*log(n))，因此后者的项会被忽略，因此最终的复杂度只是 O(n^1.585)。

- Mysticial

---

我认为后面的项只有在加法时才会被忽略..所以O(n + lg n) = O(n)。 - Wael Awada

这种情况下也会出现掉落。但需要一个全面的示例/分析来说明原因。 - Mysticial

Answer 3

n^lg3不是O(n)。它的时间复杂度比O(n)更高...实际上，任何大于1的n指数都会导致时间复杂度渐进更长。由于lg(3)约为1.58，只要从指数中减去小于0.58的值，它就会渐进地高于O(n)。

- user684934

---

所以如果我理解正确，你和我一样认为解答手册错误地说 n lg n = O(n)。 - Wael Awada

不！n log n更大，增长更快，并且不受n的限制。情况恰恰相反。 - user684934

如果对于所有的n > n0，f(n) < c.g(n)，则f(n) = O(g(n))。那么如果n lg n = O(n)，c和n0将是多少？ - Wael Awada

让c = 1和n0为5，你会发现这是不正确的。反过来则是正确的。 - user684934

所以如果反过来的话，那么 n = O(n lg n)，我理解了，但是书上说 n lgn = O(n)。 - Wael Awada