<分区>
我在这里看到了同样的问题，他们已经证明了下界是这样的
log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)
>= log(n/2) + ... + log(n/2)
= n/2 * log(n/2)
我的疑问是为什么下限不能是 n log n 本身？或者还有其他更严格的下限吗？为什么具体是 n/2 * log(n/2)？
最佳答案
这用来证明
log(n!) = log(1) + log(2) + ... + log(n-1) + log(n) = Θ(n·log(n))
为了证明这一点，只要找到 Θ(n·log(n)) 的上限和下限就足够了
下界
n/2 * log(n/2)
已经对应于Θ(n·log(n))。它很容易获得并且属于我们感兴趣的 Θ。找到更紧的下界将更加困难并且没有必要。
本题完整证明:
关于algorithm - 是 log (n!) 的下界也是 nlogn，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25755469/