O(n^n / n!)的渐近复杂度阶是什么？如何证明其增长速率？

要确定$n^n/n!$的增长速率，核心工具是斯特林近似——这是分析阶乘渐近行为的标准方法。

斯特林公式给出了$n!$的渐近等价形式：
$$n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$$
其中$\sim$表示当$n \to \infty$时，两边的比值趋近于1。

将这个近似代入比值$n^n/n!$中：
$$\frac{n^n}{n!} \sim \frac{n^n}{\sqrt{2\pi n} \left(\frac{n}{e}\right)^n} = \frac{e^n}{\sqrt{2\pi n}}$$

从这个结果可以直接看出：

• 主导项是$e^n$，这是指数级增长的核心部分；
• 分母的$\sqrt{2\pi n}$是多项式级别的增长（远慢于指数级），不会改变整体的指数增长趋势。

严格来说，我们可以用斯特林公式的上下界验证：
对于所有$n \geq 1$，有：
$$\sqrt{2\pi n} \left(\frac{n}{e}\right)^n \leq n! \leq \sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{\frac{1}{12n}}$$

代入比值后可得：
$$\frac{e^n}{\sqrt{2\pi n} e^{\frac{1}{12n}}} \leq \frac{n^n}{n!} \leq \frac{e^n}{\sqrt{2\pi n}}$$

由于$e^{\frac{1}{12n}} \leq e^{\frac{1}{12}}$（当$n \geq 1$），且$\sqrt{n}$的增长远慢于$e^n$，因此存在常数$C_1, C_2 > 0$，使得当$n$足够大时：
$$C_1 e^n \leq \frac{n^n}{n!} \leq C_2 e^n$$

这说明$\frac{n^{n}{n!}$的增长速率是$\Theta(e}n)$，确实是指数级的，和你的直观判断一致。

内容的提问来源于stack exchange，提问作者rafaelcosman