n log n 是 O(n)？
我正在尝试解决这个递归问题
T(n) = 3 T(n/2) + n lg n ..
我得出了它属于大师定理案例 2 的解决方案，因为 n lg n 是 O(n^2)
但在参考解决方案手册后，我注意到这个解决方案，他们有
该解决方案表示 n lg n =在^(lg 3 - e)) 对于 e 在 0 到 0.58 之间，
所以这意味着 n lg n 是 O(n) .. 这是对的吗？我在这里错过了什么吗？
nlgn 不是 O(n^2) 吗？
I am trying to solve this recurrence
T(n) = 3 T(n/2) + n lg n ..
I have come to the solution that it belongs to masters theorem case 2 since n lg n is O(n^2)
but after referring to the solution manual i noticed this solution that they have
The soluttion says that n lg n = O ( n ^(lg 3 - e)) for e between 0 and 0.58
so this means n lg n is O(n) .. is this right? Am i missing something here?
Isn't nlgn O(n^2) ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这会更好地解释事情
This will explain things better
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)。n*log(n)is notO(n^2). It's known as quasi-linear and it grows much slower thanO(n^2). In factn*log(n)is less than polynomial.In other words:
where
k > 1In your example:
Since
O(n^1.585)is polynomial and dominatesO(n*log(n)), the latter term drops off so the final complexity is justO(n^1.585).nlg3 不是 O(n)。它超出了 O(n)...事实上，任何大于 1 的 n 指数都会导致比 O(n) 渐近更长的时间。由于 lg(3) 约为 1.58，因此只要从指数中减去小于 0.58，它就会渐近大于 O(n)。
nlg3 is not O(n). It outgrows O(n)... In fact, any exponent on n that is larger than 1 results in an asymptotically longer time than O(n). Since lg(3) is about 1.58, as long as you subtract less than .58 from the exponent it is asymptotically greater than O(n).