首页 > 编程知识 正文

数论斯特林公式 Stirling公式取N阶乘近似值,斯特林公式n的阶乘近似

时间:2023-05-06 11:50:01 阅读:186543 作者:490

斯特林公式是取n次幂近似值的数学公式。 一般来说,当n较大时,n阶幂的计算量足够大,因此斯特林公式足够容易使用。 从图中可以看出,即使n很小,斯特林公式的值也足够准确。

公式如下。

如可以看到的,对于足够大的整数n,这两个数相互近似。 更准确地说:

或者

该公式和误差的估计可以推导如下。 我们不直接估算n! 考虑自然对数:

用一般方法计算n的阶乘,其时间复杂度为o(n ):n!=1*2*3*4*5*.*n;

如果计算n得到的数字是几位数的话,就知道该位数等于lgN! 1;

:

但是,当n很大时,可以根据斯特林公式进行优化。 ((即Stirling公式) )。

(e=2.718 ) )。

斯特林公式可以用来估算某个数的大小,与lg结合可以估算某个数的位数,或者可以估算某个数的阶乘为另一个数的倍数。

例题: http://ACM.hdu.edu.cn/show problem.PHP? pid=1018

主题给出的n的范围为: 1=N=107

用普通的方法绝对算不出n的阶乘后的数字位数,但用斯特林公式可以很好地解决。

Stirling 公式

也就是说:

Stirling公式的意思是,当n足够大时,n! 计算非常困难。 关于n有很多! 的等式,但无法很好地估计阶乘结果。 特别是n大的话,误差会变得非常大。 然而,可以利用Stirling公式将阶乘转化为幂函数,从而更好地估计阶乘的结果。 而且n越大,估计越准确。

用Stirling公式求解n! 的位数:容易知道的整数n的位数为[lgn] 1。 使用Stirling公式计算n! 的位数时,可以两边取对数,为:

所以n! 的位数如下。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。