是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)) 糾正我，如果我做了什麼錯誤