runtime - nlog(n) 是大 Theta(n) 吗？主定理

Question

n⋅log(n) 在 Θ(n) 中吗？
我问这个是因为我正在使用主定理解决重复问题。

方程为 T(n) = 2T(n/2) + n log n

该解决方案表示它满足案例 2，即 T(n) = Θ(n log(n))。

我不明白 n log(n) 怎么可能是 O(n)，当 n > 10 时 n log(n) 不应该大于 n 吗？

Answer 1

不，n log n ≠ Θ(n)。要看到这一点，请注意

lim _{n → ∞} ((n log n) / n) = lim _{n → ∞} log n = ∞

由于这个限制趋向于无穷大，我们看到 n log n 不是 Θ(n)。您是否找到了相反的消息来源？

希望这可以帮助！

Answer 2

Θ(n⋅log(n)) 不是 O(n)，而是 O(n⋅log(n))，这是正确的解。