是的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 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) [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屋！