algorithm - 哪个函数在 n 和 log(n!) 之间渐近较大

Question

我猜O(log(n!))它渐近地比O(n). 我对吗 ？

标签： algorithmmathbig-o

Answer 1

不幸的是，你的猜测完全错误！尝试扩展log(n!)如下：

log(n!) = log(n * (n-1) * ... * 1) > log(n * (n-1) * ... * n/2) > 
log((n/2)^n) = n log(n/2) \in Theta(n log(n))`

所以，n \in O(log(n!))