斯特林公式 ——Stirling公式（取N阶乘近似值）

朱雀 2022-05-15 04:22 466阅读 0赞

转载：[点我][Link 1]

斯特灵公式是一条用来取n[阶乘][Link 2][近似值][Link 3]的[数学][Link 4][公式][Link 5]。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特灵公式十分好用。从图中可以看出，即使在n很小的时候，斯特灵公式的取值已经十分准确。

![SouthEast][]

公式为：   ![n! \\approx \\sqrt\{2\\pi n\}\\, \\left(\\frac\{n\}\{e\}\\right)^\{n\}.][n_ _approx _sqrt_2_pi n_ _left_frac_n_e_right_n_.]

从图中看出，对于足够大的整数n，这两个数互为近似值。更加精确地：

![\\lim\_\{n \\rightarrow \\infty\} \{\\frac\{e^n\\, n!\}\{n^n \\sqrt\{n\}\}\} = \\sqrt\{2 \\pi\}.][lim_n _rightarrow _infty_ _frac_e_n_ n_n_n _sqrt_n_ _ _sqrt_2 _pi_.]       或者        ![\\lim\_\{n \\rightarrow \\infty\} \{\\frac\{n!\}\{\\sqrt\{2\\pi n\}\\, \\left(\\frac\{n\}\{e\}\\right)^\{n\}\}\} = 1][lim_n _rightarrow _infty_ _frac_n_sqrt_2_pi n_ _left_frac_n_e_right_n_ _ 1]

这个公式，以及误差的估计，可以推导如下。我们不直接估计n!，而是考虑它的[自然对数][Link 6]：

![\\ln(n!) = \\ln 1 + \\ln 2 + \\cdots + \\ln n.][ln_n_ _ _ln 1 _ _ln 2 _ _cdots _ _ln n.]

按一般方法计算N的阶乘，其时间复杂度为O（N）：    N！=  
1 \* 2 \* 3 \* 4 \* 5 \* ………… \* N；

如果要计算N后得到的数字为几位数，则我们可以知道其位数等于lgN！+1；  
  
则:  ![\\ln(n!) = \\ln 1 + \\ln 2 + \\cdots + \\ln n.][ln_n_ _ _ln 1 _ _ln 2 _ _cdots _ _ln n.]  
  
但是当N很大的时候，我们可以通过斯特林公式进行优化：（即Stirling公式）  
  
![n! \\approx \\sqrt\{2\\pi n\}\\, \\left(\\frac\{n\}\{e\}\\right)^\{n\}.][n_ _approx _sqrt_2_pi n_ _left_frac_n_e_right_n_.]（e  
= 2.718）  
  
斯特林公式可以用来估算某数的大小，结合lg可以估算某数的位数，或者可以估算某数的阶乘是另一个数的倍数。

例题：    [http://acm.hdu.edu.cn/showproblem.php?pid=1018][http_acm.hdu.edu.cn_showproblem.php_pid_1018]

题目给出的N的范围是: 1<= N <= 10 7

用普通方法肯定算不出N的阶乘后的出的数字位数，但运用斯特林公式则很好解决.

**Stirling 公式**

![Center][]

即：

![e656c0c9a9bd7e763310012120a00317.png][]

Stirling公式的意义在于：当n足够大时，n!计算起来十分困难，虽然有很多关于n!的等式，但并不能很好地对阶乘结果进行估计，尤其是n很大之后，误差将会非常大。但利用Stirling公式可以将阶乘转化成幂函数，使得阶乘的结果得以更好的估计。而且n越大，估计得越准确。

利用Stirling公式求解n!的位数：易知整数n的位数为\[lgn\]+1。利用Stirling公式计算n!结果的位数时，可以两边取对数，得:

![Center 1][]

故n!的位数为：

![Center 2][]

[Link 1]: https://blog.csdn.net/liangzhaoyang1/article/details/51145807
[Link 2]: http://zh.wikipedia.org/wiki/%E9%9A%8E%E4%B9%98
[Link 3]: http://zh.wikipedia.org/wiki/%E8%BF%91%E4%BC%BC%E5%80%BC
[Link 4]: http://zh.wikipedia.org/wiki/%E6%95%B8%E5%AD%B8
[Link 5]: http://zh.wikipedia.org/wiki/%E5%85%AC%E5%BC%8F
[SouthEast]: /images/20220515/c105d45ea8684104b5683437ccf52356.png
[n_ _approx _sqrt_2_pi n_ _left_frac_n_e_right_n_.]: /images/20220515/7d18244359844f6186badf7a1cb50793.png
[lim_n _rightarrow _infty_ _frac_e_n_ n_n_n _sqrt_n_ _ _sqrt_2 _pi_.]: http://upload.wikimedia.org/math/6/c/f/6cf8c6b4a0e3df9fde5bd5d2524064ac.png
[lim_n _rightarrow _infty_ _frac_n_sqrt_2_pi n_ _left_frac_n_e_right_n_ _ 1]: /images/20220515/93abf05dbcbd46a1bc7951b2e22eb099.png
[Link 6]: http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E5%AF%B9%E6%95%B0
[ln_n_ _ _ln 1 _ _ln 2 _ _cdots _ _ln n.]: /images/20220515/a687a9447bb448d59884eb681a1a9d9b.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1018]: http://acm.hdu.edu.cn/showproblem.php?pid=1018
[Center]: /images/20220515/97826ed86eab42238ddd9494ec587805.png
[e656c0c9a9bd7e763310012120a00317.png]: https://upload.wikimedia.org/math/e/6/5/e656c0c9a9bd7e763310012120a00317.png
[Center 1]: /images/20220515/d07fa11d74004f85bfb91a6b7a19d022.png
[Center 2]: /images/20220515/5537d99f2d8c400ea18173bdfa4c36ea.png