n log n是O（n）吗？

Question

我正在尝试解决这种复发情况

T（n）= 3 T（n / 2）+ n lg n ..

由于n lg n为O（n ^ 2），所以我得出了属于主定理情况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)小于多项式。

换句话说： 通用标签

其中k > 1

在您的示例中： 通用标签

由于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）。}