log（n！）=Θ（n·log（n））吗？

Question

我要证明log（n！）=Θ（n ·log（n））。

提示我应该用n ⁿ表示上限，而用（n / 2）^{（n / 2）}表示下限。在我看来，这似乎并不那么直观。为什么会这样呢？我绝对可以看到如何将n ⁿ转换为n ·log（n）（即，记录方程的两边），但这有点倒退。

解决这个问题的正确方法是什么？我应该画递归树吗？对此没有任何递归，因此这似乎不是一种可行的方法。

Answer 1

记住log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)您可以通过以下方式获得上限log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; = n*log(n)在丢弃总和的前一半之后，您可以通过执行类似的操作来获得下界：log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;= log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;>= log(n/2) + ... + log(n/2)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; = n/2 * log(n/2)&nbsp;

Answer 2

我意识到这是一个非常老的问题，答案是可以接受的，但是这些答案实际上都没有使用提示所建议的方法。这是一个非常简单的参数：n!（= 1 * 2 * 3 * ... * n）是n每个均小于或等于的数字的乘积n。因此它小于n全部等于的数字的乘积n;&nbsp;即n^n。产品中一半的数字（即n/2其中的数字）n!大于或等于n/2。因此他们的乘积大于n/2全部等于的数字的乘积n/2;&nbsp;即(n/2)^(n/2)。全面记录日志以确定结果。

Answer 3

对于下限，lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1&nbsp; &nbsp; &nbsp; &nbsp;>= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)&nbsp; &nbsp; &nbsp; &nbsp;= n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2&nbsp; &nbsp; &nbsp; &nbsp;= n/2 lg n - (n/2)(lg 2) + n/2 - 1/2&nbsp; &nbsp; &nbsp; &nbsp;= n/2 lg n - 1/2lg（n！）> =（1/2）（n lg n-1）结合两个界限：1/2（n lg n-1）<= lg（n！）<= n lg n通过选择大于（1/2）的下界常数，我们可以补偿括号内的-1。因此lg（n！）= Theta（n lg n）