表明总和Σi到n(logi)是O(nlogn)

Question

我认为它有效的一种方式是我们可以说, ?_i^{n (log i)} < ?_i^{n (log n)}然后试着争辩它是O(n log n),但是从哪里开始？有什么建议？

Answer 1

如果您只需要显示总和为O(n log n),则可以显示该值

Σlogi≤Σlogn = n log n

因此,您的函数是O(n log n).如果你想更正式,你可以使用常数c = 1和n ₀ = 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).

希望这可以帮助!