time-complexity - 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？

标签： time-complexitybig-ocomplexity-theory

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