我认为它起作用的一种方式是，我们可以这样说，∑_i^{n (log i)} < ∑_i^{n (log n)}然后尝试证明它是O（n log n），但是从这里去哪里呢？有什么建议么？
如果只需要显示总和为O（n log n），则可以显示
Σlog i≤Σlog n = n log n
因此，您的函数为O（n log n）。如果您想更正式一点，可以使用常数c = 1和n 0 = 1。
更有趣的问题是通过证明Ω（n log n）的下界来表明总和为Θ（n log n）。为此，请注意，总和大于或等于求和中最后n / 2个项的总和。这些总和中的每一项至少为log（n / 2）。这给出（n / 2）log（n / 2）=（n / 2）（log n-log 2）的下限，即Ω（n log n）。因此，您的总和为O（n log n）和Ω（n log n），因此为Θ（n log n）。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句