是log（n！）= O（（log（n））^ 2）？

Question

我正在练习渐近分析的问题，并且遇到了这个问题。

是log(n!) = O((log(n))^2)？

我能够证明

log(n!) = O(n*log(n)) 
(log 1 + log 2 + .. + log n <= log n + log n + ... + log n) 

和

(log(n))^2 = O(n*log(n)) 
(log n <= n => (log n)^2 <= n*logn) 

我不能进一步进行。有关如何进一步进行的任何暗示或直觉？由于

Answer 1

Accoriding到Stirling's Approximation：

log(n!) = n*log(n) - n + O(log(n))

所以很明显的上界log(n!)将是去掉了方程的上半年O(nlogn)

下界可以这样计算：

log(1) + ... + log(n/2) + ... + log(n) = log(n/2) + ... + log(n)
= log(n/2) + ... + log(n/2)
= n/2 * log(n/2)

所以下界也是nlogn。很明显的答案是NO

Answer 2

我想我得到了我自己的问题的答案。我们将证明以下事实：

1）n*log(n)是一个严密开往log(n!)

2）n*log(n)是一个上限(log(n))^2

3）n*log(n)不是一个下界(log(n))^2

有关（1）的证明，请参阅this。

证明（2）&（3）在问题本身中提供。 增长率为log n<增长率为n。 因此增长率为log(n)^2<增长率为n*log(n)。 所以log(n)^2 = o(n*log(n))（这里我用小-O表示的n*log(n)的增长速度是如此的结论是：log(n!) = big-omega(log(n^2)) 纠正我，如果我做了什么错误