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

给出了一个提示,我应该用nn表示上界,用(n/2)(n/2)表示下界。这对我来说不是那么直观。为什么会这样呢?我可以清楚地看到如何将nn转换为n·log(n)(即方程两边都取对数),但这有点倒过来了。

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


当前回答

这可能会有帮助:

eln(x) = x

and

(lm)n = lm*n

其他回答

这可能会有帮助:

eln(x) = x

and

(lm)n = lm*n

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

谢谢,我发现你的答案令人信服,但在我的情况下,我必须使用Θ属性:

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

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

这是非常严格的界限!

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