log(n!) 等价于 nlogn 吗？（大 O 符号）

Question

在我的书中有一个选择题：

以下函数的大 O 表示法是什么：n^log(2) +log(n^n) + nlog(n!)

我知道 log(n!) 属于 O(nlogn)，但我在网上读到它们是等价的。log(n!) 和 nlogn 有什么相同之处？怎么样：log(n!) = logn + log(n-1) + ... + log2 + log1 等价于 nlogn？

Answer 1

我们n/2是整数除法的商n通过2。我们有：

log(n!) =  log(n) + log(n-1) + ... + log(n/2) + log(n/2 - 1) + ... + log(2) + log(1)
        >= log(n/2) + log(n/2) + ... + log(n/2) + log(n/2 - 1) + ... + log(2)
        >= (n/2)log(n/2) + (n/2)log(2)
        >= (n/2)(log(n) -log(2) + log(2))
        =  (n/2)log(n)

然后

n log(n) <= 2log(n!) = O(log(n!))

和n log(n) = O(log(n!))。反过来，

log(n!) <= log(n^n) = n log(n)

和log(n!) = O(n log(n))。