algorithm - n log n 是 O(n)？

Question

我正在尝试解决这种重复

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

我已经得出它属于大师定理案例 2 的解决方案，因为 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) 吗？

Answer 1

这将更好地解释事情

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).

Answer 3

n ^lg3不是 O(n)。它超过了 O(n)...事实上，n 上大于 1 的任何指数都会导致比 O(n) 渐近更长的时间。由于 lg(3) 约为 1.58，只要从指数中减去小于 0.58，它就会逐渐大于 O(n)。