为什么 lg(n!)=O(nlg(n)) 的可能解释
可能的重复：
log(n!) = θ(n·log(n)) 吗？
我的“证明”为什么 lg(n!) 是 O(nlg(n)) 是因为 n 在多项式上大于 lg(n!)，因此 nlg(n) 在多项式上总是大于 lg(n!)。这是一个可以接受的理由吗？或者你必须在数学上证明它（在这种情况下我不知道如何处理阶乘）
Possible Duplicate:
Is log(n!) = Θ(n·log(n))?
My "proof" for why lg(n!) is O(nlg(n)) is because n is polynomially larger than lg(n!), so therefore nlg(n) would always be polynomially larger than lg(n!). Is that an acceptable reason? or do you have to mathematically prove it (in which case I would not know how to deal with the factorial)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我见过的通常证明是，对于足够大的n，n！ < nn。两边取对数可得 log(n!) log(n!) log(n!) log(n!) 日志（nn）。由于 log(ba) = a log(b)，我们得到 log(n!) log(n!) log(ba) = a log(b) n log(n)。
The usual proof I've seen is that for sufficiently large n, n! < nn. Take the logarithm of both sides to get log(n!) < log(nn). Since log(ba) = a log(b), we get log(n!) < n log(n).
您可能确实需要一些数学上更严格的东西，但这并不太困难。因为
您可能会考虑
y = lg x图下的面积，并用 http://en.wikipedia.org/wiki/Rectangle_method。你会得到类似 http://en.wikipedia.org/wiki/Stirling's_approximation 的内容。因为它很小，所以你的矩形需要在上面和下面绑定。
You probably do need something a bit more mathematically strict, but it's not too difficult. Since
you might consider the area under the graph of
y = lg xand approximate it with the http://en.wikipedia.org/wiki/Rectangle_method . You'll get something like http://en.wikipedia.org/wiki/Stirling's_approximation .Because it's 'little o' your rectangles need to bound above and below.
使用斯特林近似：http://en.wikipedia.org/wiki/Stirling%27s_approximation
Use stirling's approximation: http://en.wikipedia.org/wiki/Stirling%27s_approximation
回想一下 ln(a⋅b) = ln(a) + ln(b)。因此，ln(n!) = ln(n⋅(n−1)⋅…⋅2⋅1) = ln(n) + ln(n−1) + … ln(2) + ln(1)；通过检查得出 n⋅ln(n) ≤ ln(n!) 。
Recall that ln(a⋅b) = ln(a) + ln(b). Therefore, ln(n!) = ln(n⋅(n−1)⋅…⋅2⋅1) = ln(n) + ln(n−1) + … ln(2) + ln(1); this yields n⋅ln(n) ≤ ln(n!) by inspection.