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

Question

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想要改善这个问题吗？更新问题，以便将其作为 on-topic用于堆栈溢出。

7年前关闭。



Improve this question




我认为它起作用的一种方式是，我们可以说 ∑_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和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)。

希望这可以帮助!

关于math - 证明∑ i至n(logi)的总和为O(nlogn)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21152609/

上一篇：r - 在 R 中有效地填充平均值旁边的值

下一篇：SQL 查询给我最后一列，其中有一个值

相关文章：

math - 添加导致 `MethodError: no method matching +(::Array{Int64, 0},::Int64)`

angularjs - Angular js - 四舍五入

java - Java 中素数算法的时间复杂度

java - Java 中 Arrays.deepEquals() 的时间复杂度

给定两个函数的Javascript找到交集

algorithm - 可被 N 整除的最小正数

algorithm - 找到任意两个函数的交集 - 求解联立方程

algorithm - 在哪种情况下，复杂度为 2^n 的算法会用于 n^5？

recursion - 行列式递归算法的复杂度计算

algorithm - Big-Theta 算法分析

Answer 1

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

Σ log i ≤ Σ log n = n log n

因此，您的函数为O(n log n)。如果要更加正式，可以使用常量c = 1和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)。

希望这可以帮助!