在描述算法的时间复杂度时，我们常用大O记法（Big O notation）来描述计算量随问题规模增长的情况。对于正整数的阶乘$n!$，如果使用一般的递归实现，这个时间复杂度是 $O(n)$，它代表计算量随着$n$的增长呈线性增加。当$n$较大时，计算量也相当可观，如果不需要特别精确的结果，那就可以使用Sterling公式进行近似计算，它可以将时间复杂降为 $O(\log{n})$ ，这是一个非常大的效率提升。

Sterling公式的表示

Sterling公式是用来求 $n!$ 近似值的公式，形式如下：

$$$ n! \sim \sqrt{2\pi n} \Big(\frac{n}{e}\Big)^n $$$

或者用极限的表达形式：

$$$ \lim_{n\to \infty} \frac{\sqrt{2\pi n} n^{n} e^{-n} }{n!} = 1 $$$

Sterling公式近似计算有这2个优点：

1. 当 $n$ 比较小的时候，计算值已经比较精确。比如当 $n = 5$ 时，$ n! = 120$，而利用Sterling公式计算的近似值为 $118.02$，误差为1.6%；$n = 10$时，$ n! = 3628800 $，公式计算近似值为 $3598695.6$ ，误差0.8%。
2. 它大幅降低了运算的时间复杂度，普通的计算需要从1乘到n，时间复杂是 $O(n)$，而利用此近似公式，时间复杂可以下降到 $O(\log{n})$。

Sterling公式中包含两部分的计算，开平方和计算乘方。对于 $\sqrt{n}$ 开平方的计算效率，使用牛顿迭代法，在现在的CPU下可以认为是和乘法差不多，时间复杂度为 $O(M(n))$ （这里的 $n$ 表示它有几位数字，M表示乘法的运算复杂度）；而 $n^n$ 这样的乘方计算，利用递归，可以做到只用 $O(\log{n})$ 的时间开销——所以整体的时间复杂度是 $O(\log{n})$。

Sterling 公式的证明

对 $n!$ 取自然对数：

$$$ \ln(n!) = ln(1) + ln(2) + \dots + ln(n) $$$

由于 $ln $ 在定义域 $(0, +\infty)$ 上单调递增，我们有：

$$$ \int_{n-1}^{n} ln(x) dx < ln(x) < \int_{n}^{n+1} ln(x) dx $$$

对于 $0$ 到 $n$ 的整数，应用上面这个不等式，然后累加在一起，可以得到：

$$$ \int_{0}^{n} ln(x) dx < ln(n!) < \int_{1}^{n+1} ln(x) dx $$$

不等式的左端属于反常积分，但从它的反函数 $ e^x $ 在 $ (-\infty, 0) $ 可积（即图形的面积可求出来），我们可以知道它是收敛的。根据积分表 $ \int \ln{x} = x \ln{x} - x + C$，对不等式两端求定积分：

$$$ n \ln{n} - n < ln(n!) < (n+1) \ln{(n+1)} + 1 $$$

接下来，令：

$$$ d_n = \ln{(n!)} - (n + \frac{1}{2}) \ln{(n)} + n $$$

则有：

$$$ d_{n} - d_{n+1} = (n+\frac{1}{2}) \ln{\frac{n+1}{n}} - 1 $$$

对 $\frac{n+1}{n}$ 进行代数变形：

$$$ \frac{n+1}{n} = \frac{1 + \frac{1}{2n+1} }{ 1 - \frac{1}{2n+1}} $$$

根据泰勒级数展开（$|x| \lt 1$）：

\begin{align*} \ln{(1+x)} &= +x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} + \dots \\ \ln{(1-x)} &= -x - \frac{x^2}{2} - \frac{x^3}{3} - \frac{x^4}{4} - \dots \end{align*}

所以有：

$$$ \frac{1}{2}\ln{\frac{1+x}{1-x}} = x + \frac{x^3}{3} + \frac{x^5}{5} + \dots $$$

因为 $|\frac{1}{2n+1}| \lt 1$ ，我们可以利用上式得到：

\begin{align*} d_{n} - d_{n+1} &= (2n+1)[\frac{1}{2n+1} + \frac{1}{3(2n+1)^3} + \frac{1}{(2n+1)^5} + \dots ] - 1 \\ &= \frac{1}{3}\cdot \frac{1}{(2n+1)^2} + \frac{1}{5} \cdot \frac{1}{(2n+1)^5} + \dots - 1 \\ &< \frac{1}{3} [\frac{1}{(2n+1)^2} + \frac{1}{(2n+1)^4} + \dots] \\ &= \frac{1}{3} \frac{1}{(2n+1)^2 - 1} \\ &= \frac{1}{12} (\frac{1}{n} - \frac{1}{n+1}) \end{align*}

根据上式的结果，我们可以得出：

1. $\{ d_n \}$ 是一个递减序列；

2. $\{ d_n - \frac{1}{12n} \}$ 是一个递增序列。

这意味着 $\{ d_n \}$ 可以收敛到一个常数 $C$ 且 $C \gt d_1 - \frac{1}{12} = \frac{11}{12}$

$$$ \lim_{n\to \infty} d_n = C $$$

对上式两边取指数：

$$$ \lim_{n\to \infty} n! \frac{e^n}{n^n \sqrt{n}} = e^C $$$

接下来只需要证明 $e^C = \sqrt{2\pi}$，而这里需要用到之前证明的Wallis 公式 ：

$$$ \lim_{n \to \infty} \frac{2 \cdot2 \cdot 4 \cdot 4 \cdots (2n) (2n)}{1 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdots (2n-1) (2n+1)} = \frac{\pi}{2} $$$

将Wallis公式两边做开方：

$$$ \frac{2 \cdot 4 \cdots (2n)}{1 \cdot 3 \cdot 5 \cdots (2n-1) \sqrt{2n}} \sim \sqrt{\frac{\pi}{2}} $$$

左侧分子分母同乘 $2 \cdot 4 \cdots (2n)$，我们得到：

$$$ \frac{(2^n \cdot n!)^2}{(2n)!} \cdot \frac{1}{\sqrt{2n}} \sim \sqrt{\frac{\pi}{2}} $$$

将 $n! \sim \frac{e^c n ^ n \sqrt{n}}{e^n}$ 代入上式：

$$$ \frac{(2^n\frac{e^Cn^n\sqrt{n}}{e^n})^2}{\frac{e^C(2n)^{2n}\sqrt{2n}} {e^{2n}} } \cdot \frac{1}{\sqrt{2n}} \sim \sqrt{\frac{\pi}{2}} $$$

化简后即得：

$$$ e^C \sim \sqrt{2\pi} $$$

至此，我们便完成了Sterling公式的证明。

证明过程中用到的一些数学结论

1. $\ln{(1+x)}$ 的泰勒展开

2. $\frac{1}{x^2} + \frac{1}{x^4} + \frac{1}{x^6} + \dots $ 的计算

对于第一个问题 $f(x) = \ln{(1+x)} $, 有$f'(x) = \frac{1}{1+x}$，当 $ |x| \lt 1$ 时：

$$$ \frac{1}{1+x} = \sum_0^{\infty} (-1)^nx^n $$$

左右同时积分，即得：

$$$ \ln{(1+x)} = \sum_0^{\infty} \frac{(-1)^nx^{n+1}}{n+1} = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} + \dots $$$

把 $x$ 替换成 $ -x $ 就可以得到 $\ln{(1-x)}$ 的展开。

对于第二个问题，这实际上无穷几何级数的求和：

$$$ S = a + ar + ar^2 + ar^3 + \dots $$$

对上式两边乘以 $r$:

$$$ r S = ar + ar^2 + ar^3 + ar^4 + \dots $$$

上述两式相减，即得：

$$$ (1-r)S = a $$$

也就是：

$$$ S = \frac{a}{1-r} $$$

需要注意的是，当 $|r| \lt 1$ 时上式才成立，因为此时才能保证其收敛。

在这个问题 $\frac{1}{x^2} + \frac{1}{x^4} + \frac{1}{x^6} + \dots $ 里，$a = r = \frac{1}{x^2}$，所以：

$$$ S = \frac{1}{x^2 - 1} $$$