log(n!) = Θ(n·log(n))? [英] Is log(n!) = Θ(n·log(n))?

问题描述

我要证明 log(n!) = Θ(n·log(n)).

I am to show that log(n!) = Θ(n·log(n)).

提示我应该用 nⁿ 显示上限并显示下限(n/2)^(n/2).这对我来说似乎并不那么直观.为什么会是这样?我绝对可以看到如何将 nⁿ 转换为 n·log(n)(即记录方程的两边)，但这有点倒退.

A hint was given that I should show the upper bound with nⁿ and show the lower bound with (n/2)^(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nⁿ to n·log(n) (i.e. log both sides of an equation), but that's kind of working backwards.

解决这个问题的正确方法是什么?我应该画递归树吗?对此没有任何递归性，因此这似乎不是一种可能的方法..

What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn't seem like a likely approach..

推荐答案

记住

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)

而且你可以在扔掉前半部分之后做类似的事情来得到下界:

And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:

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))?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！