Hegwin.Me

寓形宇内复几时?曷不委心任去留?胡为乎遑遑欲何之?

Stirling公式的证明

The Proof of Stirling's approximation

在描述算法的时间复杂度时,我们常用大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})$。

Logarithmic-time-complexity-blog-1.md.jpg

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} $$$

< Back