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

我要证明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)

2010-01-19 17:23:52

其他回答

这可能会有帮助:

e^ln(x) = x

and

(l^m)ⁿ = l^m*n

2010-01-19 17:33:06

记住,

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)

2010-01-19 17:23:52

参见斯特林近似:

-不，不，不。

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

2010-01-19 17:51:25

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

2017-01-09 18:25:17

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

2011-11-03 03:53:31

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

推荐文章

最新文章

标签