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

Question

我要证明log（n！）=Θ（n ·log（n））。提示我应该用n n表示上限，而用（n / 2）（n / 2）表示下限。在我看来，这似乎并不那么直观。为什么会这样呢？我绝对可以看到如何将n 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)

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

Answer 2

我意识到这是一个非常老的问题，答案是可以接受的，但是这些答案实际上都没有使用提示所建议的方法。

这是一个非常简单的参数：

n!（= 1 * 2 * 3 * ... * n）是n每个均小于或等于的数字的乘积n。因此它小于n全部等于的数字的乘积n; 即n^n。

产品中一半的数字（即n/2其中的数字）n!大于或等于n/2。因此他们的乘积大于n/2全部等于的数字的乘积n/2; 即(n/2)^(n/2)。

全面记录日志以确定结果。

Answer 3

对于下限，

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1

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

       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2

       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2

       = n/2 lg n - 1/2

lg（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）