证明∑ i至n(logi)的总和为O(nlogn)

本文介绍了证明∑ i至n(logi)的总和为O(nlogn)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我认为它起作用的一种方式是，我们可以说∑_i^{n (log i)} < ∑_i^{n (log n)}，然后尝试说它是O(n log n)，但是从这里去哪里呢?有什么建议吗?

One way I thought it works is that we can say that ∑_i^{n (log i)} < ∑_i^{n (log n)} and then try to argue that it's O(n log n), but where to go from here? Any suggestions?

推荐答案

如果只需要显示总和为O(n log n)，则可以显示

If you just need to show that the sum is O(n log n), you can show that

Σ记录我Σ log n = n log n

Σ log i ≤ Σ log n = n log n

因此，您的函数为O(n log n).如果要更加正式，可以使用常量c = 1和n 0 = 1.

Therefore, your function is O(n log n). If you want to be even more formal, you can use the constants c = 1 and n0 = 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).

The more interesting question is to show that the sum is Θ(n log n) by proving an Ω(n log n) lower bound. To do this, note that the sum is greater than or equal to the sum of the last n / 2 terms in the summation. Each of those terms in the summation is at least log (n / 2). This gives a lower bound of (n / 2) log(n / 2) = (n / 2) (log n - log 2), which is Ω(n log n). Therefore, your summation is O(n log n) and Ω(n log n), so it's Θ(n log n).

希望这会有所帮助！