N log n是O(n)？

Question

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

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

因为n lg n是O(n^2)，所以我已经得到了它属于主定理情况2的解。

但在参考了解决方案手册后，我注意到他们有这样的解决方案

​

​

解是:当e在0和0.58之间时，n lg n=O(n^(lg3- e))

这意味着n lg n是O(n)。是这样的吗？我是不是漏掉了什么？

nlgn不是O(n^2)吗？

Answer 1

这会更好地解释事情

​

Answer 2

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

换句话说：

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

where k > 1

在您的示例中：

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

由于O(n^1.585)是多项式的，并且在O(n*log(n))中占主导地位，因此后一项下降，所以最终的复杂度就是O(n^1.585)。