为了账号安全,请及时绑定邮箱和手机立即绑定

log(n!)=Θ(n·log(n))吗?

log(n!)=Θ(n·log(n))吗?

我要证明log(n!)=Θ(n ·log(n))。提示我应该用n n表示上限,而用(n / 2)(n / 2)表示下限。在我看来,这似乎并不那么直观。为什么会这样呢?我绝对可以看到如何将n n转换为n ·log(n)(即,记录方程的两边),但这有点倒退。解决这个问题的正确方法是什么?我应该画递归树吗?对此没有任何递归,因此这似乎不是一种可行的方法。
查看完整描述

3 回答

?
慕村225694

TA贡献1880条经验 获得超4个赞

记住


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) 


查看完整回答
反对 回复 2019-10-05
?
紫衣仙女

TA贡献1839条经验 获得超15个赞

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

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

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

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

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


查看完整回答
反对 回复 2019-10-05
?
一只名叫tom的猫

TA贡献1906条经验 获得超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(n lg n-1)<= lg(n!)<= n lg n


通过选择大于(1/2)的下界常数,我们可以补偿括号内的-1。


因此lg(n!)= Theta(n lg n)


查看完整回答
反对 回复 2019-10-05
  • 3 回答
  • 0 关注
  • 3756 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信