algorithm - 是 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

根据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