斯特林公式(Stirling's Formula):我一个阶乘表达式,怎么就和圆扯上关系了呢?
By Long Luo
在科研和工程领域中,阶乘( \(\textit{Factorial}\) )有着广泛的应用。在概率论中,阶乘是计算排列( \(\textit{Permutation}\) )和组合( \(\textit{Combination}\) )时不可或缺的;在物理中,计算粒子系统的状态数以及大型系统的统计分布都要用到阶乘;在计算机中,阶乘则用于图论和组合优化问题。
大家都知道“指数爆炸”这个值,因为指数增长是非常迅猛的。其实阶乘增长要远远快于指数增长,如下图 1 所示为不同算法复杂度增长情况。随着 \(n\) 的增大,阶乘的计算复杂度迅速上升,当处理大 \(n\) 时,计算 \(n!\) 会变得极其复杂且耗时。例如 \(5! = 120\) ,而 \(50! \approx 3.04 \times 10^{64}\) ,这已经是一个非常庞大的数字!如果直接使用递归方法去求解 \(n!\) 的时间复杂度是 \(O(2^n)\) ,使用动态规划也只能降低到 \(O(n)\) 。在实际应用中,往往需要计算大数的阶乘,即使目前最先进的计算机去处理极大数的阶乘时,也会面临需要巨大的计算及存储资源消耗问题。
人们迫切需要找到一种可以快速计算阶乘的方法,在 18 世纪初期,苏格兰数学家詹姆斯·斯特林( \(\textit{James Stirling}\) )提出了斯特林公式 。斯特林公式( \(\textit{Stirling's Approximation}\) )提供了一种近似计算阶乘的方法,特别适用于大 \(n\) 的情况,其标准形式为:
\[ n! \approx {\sqrt {2\pi n}} \,\left( {\frac {n}{e}} \right )^n \tag{1.1} \label{1.1} \]
其对数形式为:
\[ \ln (n!) \approx n \ln n - n \]
这个公式最早是亚伯拉罕·棣莫弗( \(\textit{Abraham de Moivre}\) )在研究二项分布时,为了解决大数阶乘问题时发现的,其形式为:
\[ n! \approx C n^{n + \frac {1}{2}}e^{-n} \tag{1.2} \label{1.2} \]
其中 \(C\) 为某个常量值,斯特林证明了公式中 \(C = \sqrt {2 \pi}\) ,于是冠名权就给了斯特林。
斯特林公式可以大大简化阶乘的计算,特别是当 \(n\) 很大时,它提供了一个非常精确的近似值。斯特林公式使得复杂的阶乘计算可以通过较为简单的幂函数、指数函数和根号运算来完成。相比于直接计算阶乘,它极大地减少了计算量,是大数问题中不可或缺的工具。
斯特林公式中集合了圆周率 \(\pi\) 和自然常数 \(e\) ,这 \(2\) 个数学中最重要的常数,十分独特且具有美感。因为 \(e\) 意味着连续增长,而阶乘就是连续自然数的相乘。而出现 \(\pi\) 的时候,就要问自己 “Where is the circle?”,那么阶乘是如何和几何中的圆扯上关系了呢?
关于斯特拉公式的证明,常见的证明是对数形式的证明或者利用伽马函数( \(\textit{Gamma Function}\) )来证明,这里将介绍一种从零开始更易理解的推导方式。