什么是O(log(n!))，O(n!)和Stirling近似公式？

Question

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

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

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

- Jiew Meng

---

n! 就是它本身。虽然表示法有些奇怪... - leppie

@leppie "就是它本来的样子"。啊哈哈..太有趣了。 - Det

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))，它们属于等效的大O类。

- Paul

---

哇，对数的力量。 - sarnold

谢谢，我不是很理解最后一部分的内容 log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2))。floor(n/2)*log(floor(n/2)) 与 O(log(n!)) 或 O(n log(n)) 有什么关系呢？ - Jiew Meng

@kazuoua 你不能像那样简单地将“log”应用于方程的两边。如果这样做，您还可以认为O(n²) = O(n)，因为O(log(n²)) = O(2log(n)) = O(log(n))。 - Paul

它们不是相等的类。O(n!)是O(n^n)的严格子集。那个所谓的“证明”毫无意义。当n趋近于无穷大时，n/n^n的极限也是0；同样地，1/n^n的极限也是0。你的推理会证明O(1) = O(n^n)。 - Paul

@NickAceves 也很容易通过反证法证明 O(n^n) 不在 O(n!) 中，使用大O符号的定义。 - Paul

Answer 2

根据斯特林逼近，

log(n!) = n log(n) - n + O(log(n))

针对较大的n，右侧项被n log(n)主导。这意味着O(log(n!)) = O(n log(n))。

更正式地说，"大O记号"的一个定义是，当且仅当f(x) = O(g(x))时，

lim sup|f(x)/g(x)| < ∞ as x → ∞

使用斯特林逼近公式，很容易证明log(n!) ∈ O(n log(n))。类似的论证也适用于n!。通过对斯特林逼近公式两边取指数，我们发现，对于大的n，n!在渐近上的行为类似于n^(n+1) / exp(n)。由于当n → ∞时n / exp(n) → 0，因此我们可以得出结论，n! ∈ O(n^n)，但O(n!)不等同于O(n^n)。在O(n^n)中有一些函数不属于O(n!)（如n^n本身）。

- Ted Hopp