对lg(n!)=O(nlg(n))的可能解释

Question

可能重复：

Is log(n!) = Θ(n·log(n))?

我的“证据”为什么lg(n!)是O( nlg(n) )是因为n是多项式大于lg(n!)，因此n(N)总是多项式大于lg(n!)。这是一个可以接受的理由吗？或者你必须从数学上证明它(在这种情况下，我不知道如何处理阶乘)

Answer 1

你可能确实需要一些数学上更严格的东西，但这并不太难。因为

 lg(n!) = lg 1 + lg 2 + lg 3 + ..... + lg n

您可以考虑y = lg x图下的区域，并用http://en.wikipedia.org/wiki/Rectangle_method近似它。你会得到一些类似于http://en.wikipedia.org/wiki/Stirling's_approximation的东西。

因为它是“小O”，你的长方形需要上下绑定。

Answer 2

使用stirling近似：http://en.wikipedia.org/wiki/Stirling%27s_approximation

ln n! = n\ln n - n +O(ln(n)) 

Answer 3

回想一下，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!)通过检查。