n log n是O(n)？

Question

我试图解决这种情况

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

我已经得出它属于主要定理案例2的解决方案,因为n lg n是O(n ^ 2)

但在参考解决方案手册后,我注意到他们有这个解决方案

解决方案说,对于0到0.58之间的e,n lg n = O(n ^(lg 3 - 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)

哪里 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,只要从指数中减去小于.58,它就渐近地大于O(n).