我要证明log(n!) = Θ(n·log(n))
给出了一个提示，我应该用nn表示上界，用(n/2)(n/2)表示下界。这对我来说不是那么直观。为什么会这样呢?我可以清楚地看到如何将nn转换为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)
其他回答
记住,
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)
谢谢，我发现你的答案令人信服，但在我的情况下，我必须使用Θ属性:
log(n!) = Θ(n·log n) => log(n!) = O(n log n) and log(n!) = Ω(n log n)
为了验证这个问题，我找到了这个网站，在那里你有所有的过程解释:http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm
更进一步，米克·夏普留给你的
它的推导很简单: 参见http://en.wikipedia.org/wiki/Logarithm ->群论
log(n!)=log(n*(n-1)*(n-2)*…* 2*1)=log(n)+log(n-1)+…+ log(2) + log(1)
把n看成无限大。无穷减一是多少?还是- 2 ?等。
日志（inf）+日志（inf）+日志（inf）+…= inf*log(inf)
然后把无穷看做n。
这可能会有帮助:
eln(x) = x
and
(lm)n = lm*n
参见斯特林近似:
-不，不，不。
后两项的重要性小于前一项。
