为什么n=O(n^n)而log(n!)=Θ(log(n^n))

Question

通过考虑n!=O(n^n)的n!=n*(n-1)*...*2*1和n^n=n*n*n*n...*n，可以证明n^n=n*n*n*n...*n的存在。然而，log(n!)=Θ(nlogn)和log(n^n)=nlogn=Θ(nlogn)。我猜日志是一个增量函数，所以它不应该改变关系。这是怎么发生的？

Answer 1

我猜日志是一个增量函数

无论这意味着什么，维持相对的增长秩序是不够的。

一个简单的例子: n 2的增长速度比n快，但ln 2=2 ln的增长速度与n n相同。