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 吗？
最佳答案
不，n log n ≠ θ(n)。要看到这一点，请注意
limn → ∞ ((n log n) / n) = limn → ∞ log n = ∞
由于这个极限趋于无穷大，我们看到 n log n 不是 θ(n)。您是否找到了相反说法的来源？
希望这有帮助!
关于runtime - nlog(n) 是大 Theta(n) 吗？主定理，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26434510/