是 log(n!) = O((log(n))^2) 吗？
Is log(n!) = O((log(n))^2)?
我正在练习渐近分析的问题，但我被这个问题卡住了。
是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 )
我无法继续进行。关于如何进一步进行的任何提示或直觉？谢谢
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
我想我得到了我自己问题的答案。我们将证明以下事实：
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))（这里我用little-o表示n*log(n)的增长率严格大于log(n)^2
的增长率
所以结论是 log(n!) = big-omega(log(n^2))
如有错误请指正
我正在练习渐近分析的问题，但我被这个问题卡住了。
是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 )
我无法继续进行。关于如何进一步进行的任何提示或直觉？谢谢
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
我想我得到了我自己问题的答案。我们将证明以下事实：
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))（这里我用little-o表示n*log(n)的增长率严格大于log(n)^2
所以结论是 log(n!) = big-omega(log(n^2))
如有错误请指正