algorithm - 是 log (n!) 的下限，也是 nlogn

Question

我在这里看到了同样的问题。他们已经证明了这样的下限

    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)？

Answer 1

这是用来证明

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))。它很容易获得，属于我们感兴趣的 Θ。找到更严格的下界会更困难，而且没有必要。

这个问题的完整证明：

是 log(n!) = Θ(n·log(n)) 吗？