可能解释为什么lg(n!)= O(nlg(n))

Question

可能重复:
log(n!)=Θ(n·log(n))？

我为什么lg(n!)是O(nlg(n))的"证据"是因为n多项式地大于lg(n!),因此nlg(n)总是多项式地大于lg(n!).这是可以接受的原因吗？或者你必须在数学上证明它(在这种情况下我不知道如何处理阶乘)

Answer 1

我见过的通常的证据是,对于足够大的n,n!<n ⁿ.取两边的对数得到log(n!)<log(n ⁿ).由于log(b ^a)= log(b),我们得到log(n!)<n log(n).