是log(n!)=Θ(n·log(n))？
Mar*_*ark 202 algorithm math recursion complexity-theory big-o
我要显示log(n!)=Θ(n ·log(n)).
给出了一个提示,我应该用n n显示上限,并用(n/2)(n/2)显示下限.这对我来说似乎并不那么直观.那为什么会这样？我绝对可以看到如何将n n转换为n ·log(n)(即记录等式的两边),但这种情况是向后的.
解决这个问题的正确方法是什么？我应该绘制递归树吗？这没有任何递归,所以这似乎不是一个可能的方法..
Mic*_*ick 277
记住这一点
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)
- 你不需要Sterling逼近下界.log(n!)= log(1)+ ... + log(n)> = log(n/2)+ ... + log(n)> = n/2*log(n/2)= Omega (n log n). (28认同)
- @j_random_hacker:`log(n/2)+ log(n/2 + 1)+ ... + log(n - 1)+ log(n)`(`log(n!)的大一半项).实际上,我只是阅读了这个问题,并看到了问题中的线索.基本上,`(n/2)^(n/2)<= n!<= n ^ n` =>`log((n/2)^(n/2))<= log(n!)<= log(n ^ n)`=>`Θ(n/2*log( N/2))<= LOG(N!)<=Θ(的n*log(n))的` (5认同)
- 这是上限的一个非常好的证据:log(n!)= log(1)+ ... + log(n)<= n log(n)=> log(n!)= O(n log n ).然而,为了证明下限(以及因此大的tetha),你可能需要斯特林的近似. (4认同)
- 这个解释类似于接受的答案,但有更多细节:http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm (4认同)
- @Keith:我还没有得到它.您(或某人)可以在"log(n/2)+ ... + log(n)"的"..."部分为我扩展一些条款吗？谢谢! (2认同)
Nem*_*emo 38
我意识到这是一个非常古老的问题并且已经接受了答案,但这些答案实际上都没有使用提示建议的方法.
这是一个非常简单的论点:
n!(= 1*2*3*...*n)是n每个小于或等于的数字的乘积n.因此它小于n数字的乘积都等于n; 即,n^n.
产品中有一半的数字 - 即n/2它们 - n!大于或等于n/2.因此他们的产品大于n/2数字的乘积都等于n/2; 即(n/2)^(n/2).
记录整个日志以确定结果.
- 这实际上与接受的答案中的日志版本相同,但取代之前取对数.(虽然它更清楚地使用了提示) (7认同)
对不起,我不知道如何在stackoverflow上使用LaTeX语法..
- 这是一个很好的解释！我可以按照这个直到步骤 7，但随后我无法解码步骤 7 和步骤 8 之间发生的数学......:-( (3认同)
- @Z3d4s 步骤 7 中的论点基本上是，右侧的第一项是主导项，因此 log(n!) 可以近似为 n*log(n) 或者它的阶数为 n*log( n) 由大 O 表示法 O(n*log(n)) 表示。 (3认同)
- @rsonx 两者都是 - 例如，请参阅已接受的答案。关于{一些正但非支配项} - 实际上乘法的所有元素都 < 1，因此乘积也 < 1。`log` 将其变为负值，因此这里的渐近结果实际上是 `O(nlogn) - {something}`。与“nlogn”相比，该东西是否渐近微不足道还有待证明 - 而这个答案没有提供这一点。它不会影响大O，但会影响欧米茄。无论如何，这太复杂了，请参阅其他答案 (3认同)
- @Z3d4s 基本上对于 n -> Infini ， (1/n) -> 0。因此 (1 - (k/n)) -> 1。因此乘积项的对数将趋向于 0 (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)
- 之所以需要这种扩展推导，是因为“某物”> = n / 2 * lg（n / 2）不等于在先前评论之一中提到的omega（n lg n）。 (2认同)
进一步帮助您，Mick Sharpe 离开您的地方：
它的推导非常简单：参见http://en.wikipedia.org/wiki/Logarithm -> Group Theory
log(n!) = log(n * (n-1) * (n-2) * ... * 2 * 1) = log(n) + log(n-1) + ... + log(2) ) + 日志(1)
将 n 视为无限大。什么是无穷减一？还是减二？等等。
log(inf) + log(inf) + log(inf) + ... = inf * log(inf)
然后将inf视为 n。
| 归档时间： |
|
| 查看次数： |
175182 次 |
| 最近记录： |