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

Question

我猜O(log(n!))渐近比O(n)慢。我说的对吗?

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!))