我要证明log(n!) = Θ(n·log(n))
给出了一个提示，我应该用nn表示上界，用(n/2)(n/2)表示下界。这对我来说不是那么直观。为什么会这样呢?我可以清楚地看到如何将nn转换为n·log(n)(即方程两边都取对数)，但这有点倒过来了。
解决这个问题的正确方法是什么?我要画递归树吗?没有什么递归的，所以这似乎不是一个可能的方法。
当前回答
对于下界，
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 (nlgn - 1) <= lg(n!) <= nlgn
通过选择大于(1/2)的下界常数，我们可以补偿括号内的-1。
因此lk(n!) = (nlgn)
其他回答
参见斯特林近似:
-不，不，不。
后两项的重要性小于前一项。
对于下界，
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 (nlgn - 1) <= lg(n!) <= nlgn
通过选择大于(1/2)的下界常数，我们可以补偿括号内的-1。
因此lk(n!) = (nlgn)
我知道这是一个有公认答案的老问题，但这些答案实际上都没有使用暗示所建议的方法。
这是一个非常简单的论证:
n !(= 1*2*3*…*n)是n个小于或等于n的数的乘积，因此它小于n个都等于n的数的乘积;也就是说,n ^ n。
一半的数字，即n/2个，在n!乘积大于或等于n/2。因此它们的乘积大于n/2个数的乘积都等于n/2;例如(n / 2) ^ (n / 2)。
全程记录日志以建立结果。
这可能会有帮助:
eln(x) = x
and
(lm)n = lm*n
http://en.wikipedia.org/wiki/Stirling%27s_approximation 斯特林近似可能对你有帮助。它在处理与10^10及以上数量级的巨大数字相关的阶乘问题时非常有用。
