我要证明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!) = Θ(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
这可能会有帮助:
eln(x) = x
and
(lm)n = lm*n
如果你重新构造这个问题，你可以用微积分来解决它!这个方法最初是通过Arthur Breitman https://twitter.com/ArthurB/status/1436023017725964290向我展示的。
首先，求log(x)从1到n的积分得到n*log(n) -n +1。这证明了一个严格的上界，因为log是单调的，对于每一个点n，从n到n+1对log(n) >log (n) * 1积分。你也可以用log(x-1)来设定下限，对于每一个点n, 1*log(n) >从x=n-1到n对log(x)积分。log(x)从0到n-1的积分是(n-1)*(log(n-1) -1)或者n log(n-1) -n -log(n-1)+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)
对于下界，
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)
