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

我将显示Log (n!) = Θ(n·Log (n))。

提示我应该用< em > n < / em > <一口> < em > n < / em > < /一口>显示上界，用(< em > n < / em > / 2) <一口> (< em > n < / em > / 2) < /一口>显示下界。这对我来说不是那么直观。为什么会这样呢?我可以肯定地看到如何将< em > n < / em > <一口> < em > n < / em > < /一口>转换为< em > n < / em >·log (n < em > < / em >)(即对方程两边都取对数)，但这有点向后工作。

解决这个问题的正确方法是什么?我要画递归树吗?没有什么递归的，所以这似乎不是一个可能的方法。

274765 次浏览
小开
最佳答案

记住,

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)
小开

这可能会有帮助:

eln(x) = x

而且

(lm)n = lm*n
小开

看到斯特林近似:

ln(n!) = n*ln(n) - n + O(ln(n))

后两项的重要性小于前一项。

小开

更进一步，米克·夏普留给你的

它的推导很简单: 参见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 ?等。

Log (inf) + Log (inf) + Log (inf) +…= inf * log(inf)

然后把正看成n。

小开

http://en.wikipedia.org/wiki/Stirling%27s_approximation 斯特林近似可能对你有帮助。它对于处理与10^10及以上数量级的大数相关的阶乘问题非常有帮助

enter image description here

小开

我知道这是一个有公认答案的老问题，但这些答案实际上都没有使用暗示所建议的方法。

这是一个非常简单的论证:

n!(= 1*2*3*…*n)是小于或等于n的n数的乘积。因此，它小于所有等于n的n数的乘积;例如,n^n。

n!积中一半的数字——即它们的n/2——大于或等于n/2。因此，它们的乘积大于所有等于n/2的n/2数的乘积;即(n/2)^(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

小开

对于下界，

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) (nlgn - 1)

结合两个边界:

1/2 (nlgn - 1) <= lg(n!) <= nlgn

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

因此lg(n!) = (nlgn)

小开

enter image description here

对不起，我不知道如何在stackoverflow上使用LaTeX语法。

小开

如果你重新构造这个问题，你可以用微积分来解决它!这个方法最初是通过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) >log(x)从x=n-1到n的积分。log(x)从n1到n2的积分是n3，或n4。

这是非常严格的界限!


提交答案