time-complexity - 什么是 O(log(n!))、O(n!) 和斯特林近似？

Question

什么是O(log(n!))和O(n!)？我相信它是O(n log(n))和O(n^n)？为什么？

我认为这与Stirling's approximation有关，但我不太明白这个解释。

我对 O(log(n!) = O(n log(n)) 的理解有误吗？如何用更简单的术语来解释数学？实际上我只是想知道这是如何工作的。

Answer 1

O(n!) 不等于 O(n^n)。它渐近小于 O(n^n)。

O(log(n!)) 等于 O(n log(n))。这是证明这一点的一种方法:

请注意，通过使用对数规则log(mn) = log(m) + log(n)我们可以看到:

log(n!) = log(n*(n-1)*...2*1) = log(n) + log(n-1) + ... log(2) + log(1)

证明O(log(n!)) ⊆ O(n log(n)):

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

小于:

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

因此 O(log(n!)) 是 O(n log(n))


的子集

证明O(n log(n)) ⊆ O(log(n!)):

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

哪个大于(该表达式的左半部分，所有 (n-x) 替换为 n/2:

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ∈ O(n log(n))

因此，O(n log(n)) 是 O(log(n!)) 的子集。

由于 O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n))，它们是等价的 big-Oh 类。