跳至主要內容

阶乘的位数估算--数学在计算机算法研究中的作用

数据结构与算法算法数学约 1207 字大约 4 分钟

题目引入

算法与数据结构实验题 1.10 单身狗进化 这一天晚上，弯通又做梦了，并且梦到了一个帅气的男孩纸！这个男孩给了弯通一个数字 n。男孩离开前告诉弯通，n!（n 的阶乘）的位数就是距离弯通脱单的天数。矜（ji）持（ke）的弯通想知道自己还有多久能脱单，快写个程序帮助他！
输入:
输入第一行为一个正整数 n（1<=n<=25000）。
输出:
n阶乘的位数

题目分析

这道题看上去还挺有意思的很符合大学生的心理状态, 实际上就是要求阶乘的位数倒也没有拐弯抹角.
但是我们都知道, 要是用递归或者循环写阶乘, 这将是一件极为恐怖的事情.
在数据存储(空间复杂度)&计算用时(时间复杂度)上的开销, 将成为任何一台机器的噩梦, 更不可能过测试了.
举个栗子:

    int n;
    long long ans = 1;
    std::cin >> n;
    for (int i = 1; i < MAX; i++)
        ans *= i;
    std::cout << ans;

大家可以简单跑一下这个程序, 然后就会发现, 在n = 27的时候, 就已经溢出了, 完全无法满足题目要求.
这就是第一种错误的可能, 忘记了估计数据规模, 随便算算就存爆了.

还有一种可能, 就是采用高精度的算法, 将阶乘结果用表存储, 每个内存存有限位数据, 在乘法时做类似竖式乘法的高精度运算.

这种方式能不能过这个题我没有试过因为我懒, 但是一般来说高精度阶乘的时间复杂度是O(n2)O(n^{2})

程序代码的复杂度和 n = 25000 所要存储的数据规模, 也会是比较大的开销.

下文将介绍一种用数学方法巧妙估算阶乘结果规模的方式.

斯特林公式

n!≈2πn (ne)n n!\approx {\sqrt {2\pi n}}\,\left({\frac {n}{e}}\right)^{n}

这个公式以詹姆斯·斯特林的名字命名，虽然亚伯拉罕·棣美弗早于斯特林提出了一个类似的公式，但结果较不精确.
当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而且，即使在n很小的时候，斯特林公式的取值已经十分准确.

可以通过计算对比来估计一下斯特林公式算出结果, 和阶乘计算结果的误差程度.

Stirling Approximation Relative Error vs n

我们可以看到, 随着n的增大, 斯特林公式估算的误差已经降到了十万分之一以下, 这对估算阶乘的规模来说是完全可以接受的误差.

通过斯特林公式我们可以简单估算阶乘的位数, 我们知道对于一个n进制数x, 都可以对其取$ [\log_{n}x] + 1 $来得到这个n进制数的位数, 我们将进一步推导用斯特林公式估算阶乘位数N的公式.

N=[log10[2πn (ne)n]]+1 N = [log_{10}[{\sqrt {2\pi n}}\,\left({\frac {n}{e}}\right)^{n}]] + 1

其中内层中括号标记运算顺序, 外层中括号意为高斯取整(即向下取整).

N=[12log10(2πn)+nlog10(ne)]+1 N = [\frac{1}{2}log_{10}(2\pi n) + nlog_{10}(\frac{n}{e})] + 1

通过代入n, 即可轻松求得n!n!的位数, 时间复杂度是梦寐以求的O(1), 即常数时间复杂度.

代码实现

代码实现没什么好说的, 套公式罢了, 由于我之前已经测试过最大数据规模, 所以ans也是为了省事儿用的int偷懒是可耻的

  #include <stdio.h>
  #include <math.h>

  #define PI 3.141592654
  #define E 2.71828182846

  int pos(int n)
  {
      int s = 1;
      if(n > 3)
          s = log10(2*PI*n) / 2 + n * log10(n/E) + 1;
      return s;
  }

  int main()
  {
      int num, ans;
      scanf("%d", &num);
      ans = pos(num);
      printf("%d", ans);
  }

总结

数即一切

上次编辑于: