我要证明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)
