是的log(n!)=Θ(N·的log(n))? [英] Is log(n!) = Θ(n·log(n))?
问题描述
这是一个家庭作业的问题。我不期待一个答案,只是一些指导,可能:)我要表明的日志( N 的!)=Θ( N 的·日志( N 的))
This is a homework question. I'm not expecting an answer, just some guidance, possibly :) I am to show that log(n!) = Θ(n·log(n)).
一个提示是因为我应该表现出的上限是的 N 的的 N 的 并显示下界是( N 的/ 2)( N 的/ 2) 。这似乎不是所有的直觉给我。为什么会出现这种情况?我肯定可以看到如何转换的的 N 的的 N 的 为的 N 的?日志( N 的) [登录等式的两边],但是那是种工作倒退。什么是解决这个问题的正确方法呢?我应该画递归树?没有什么递归这一点,因此,它似乎并不像一个可能的方法。
A hint was given that I should show the upper bound with nn 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 nn to n·log(n) [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)
= n/2 * log(n/2)
这篇关于是的log(n!)=Θ(N·的log(n))?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!