我要证明 log（ n ！）=Θ（ n ·log（ n ））。
提示我应该用 n n 表示上限，而用 （ n / 2）（ n / 2）表示下限。在我看来，这似乎并不那么直观。为什么会这样呢？我绝对可以看到如何将 n n 转换为 n ·log（ n ）（即，记录方程的两边），但这有点倒退。
解决这个问题的正确方法是什么？我应该画递归树吗？对此没有任何递归，因此这似乎不是一种可行的方法。
请记住
log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)
您可以通过以下方式获得上限
log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n) = n*log(n)
在丢弃总和的前一半之后，您可以通过执行类似的操作来获得下界：
log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n) >= log(n/2) + ... + log(n/2) = n/2 * log(n/2)
