C++：“求解阶乘之和 1! + 2! + 3! + ... + n!” 算法、实现与性能优化

青旅半醒 2022-05-22 06:35 206阅读 0赞

题目描述：输入正整数n，编写代码实现由1至n的阶乘之和的求算。

分析题目，我们只要实现一个函数用于返回指定值的阶乘，通过for循环调用该函数并不断累加即可。

对于求i的阶乘，只需一个for循环从1遍历到i，不断累乘即可。

完整代码如下：

#include <iostream>
    using namespace std;
    long long factorial(int n);
    int main() {
    	int n = 0;
    	cin >> n;
            //定义为long long
    	long long sum = 0;
    	for(int i = 1; i <= n; i++)
                    //对每个i调用factorial函数求其阶乘
    		sum += factorial(i);
    	cout << sum ;
    	return 0;
    }
    long long factorial(int i) {
            //这里的result一定要初始化为1
    	long long result = 1;
    	for(int j = 1; j <= i; j++)
    		result*= j;
    	return result;
    }

可以在主函数中for循环内部添加输出语句，

从而最终在终端上打印出类似“1!+2!+3!=9”的形式。

我们可以看到，我们刚刚的代码存在很大的问题！

在输入规模为n的情况下，运算量达到1+2+3+...+n，这是一个很高的时间复杂度：O(n^2)。

一个优秀的编程人员不应以实现功能为导向，而应以高效实现功能为导向。

那么，我们有没有什么方法可以高效实现求阶乘之和呢？

我们将每一项展开：

1!=1

2!=1x2

3!=1x2x3

4!=1x2x3x4

5!=1x2x3x4x5

6!=1x2x3x4x5x6

7!=1x2x3x4x5x6x7

8!=1x2x3x4x5x6x7x8

发现规律了吗？我们可以得到下面的关系式：

n!=n(n-1)!

由此分析，为什么说我们最开始的代码性能差？因为我们做了太多重复计算！

我们在求n-1的阶乘时，从1乘到n-1，得到结果然后返回；

之后我们要求n的阶乘，从1乘到n，得到结果然后返回。

我们可以看到，如果已经求出了i的阶乘，那么在求i+1的阶乘时，只需要在i的阶乘的基础上乘i+1即可！

因此我们可以直接用一个变量，先让它为1的阶乘，再乘以2变为2的阶乘，再乘以3变为3的阶乘，以此类推直到它为n的阶乘；

那么这个变量的值每变一次，我们便把它累加到sum中，从而以O(n)的时间复杂度实现阶乘之和。

完整代码如下：

#include <iostream>
    using namespace std;
    int main() {
        int n;
        cin>>n;
        //sum为阶乘之和，factorial为i的阶乘
        long long sum=0, factorial=1;
        for(int i=1; i<=n; i++) {
            factorial*=i;
            sum+=factorial;
        }
        cout<<sum;
        return 0;
    }

最后说一下我自己的一点心得：

有一句说法叫“程序员的时间远比机器的时间宝贵”，将性能提升的希望寄托在机器升级换代上，于是提出“性能优化无用论”，我觉得这是非常片面的。

首先，同样面对“求阶乘之和”这样一个需求，你想到O(n^2)的算法，别人想到O(n)的算法，我不觉得你会比别人更快完成（比一比上面两个代码的行数）。

然后，以计算机每秒运算100万次为例，别人的程序1s运行出来了（100万次运算），你的程序怕是要100万秒（100万x100万次运算）。

致力于循环展开、减少函数调用这些不痛不痒的优化，才是无用的。