基础算法——阶乘和

2020-06-28 | Share to Twitter

如题，今天记录一下计算阶乘和的程序（O(n^2)）和改进版（O(n)）。

O(n2) 的暴力程序

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n = 20,sum,fact;
    for (int i = n; i >= 1; i--)
    {
        fact = 1;
        for (int j = i; j >= 1; j--)
            fact *= j;
        sum += fact;
    }
    cout << sum;
    return 0;
}

这个其实没什么好说的，两层for所以是O(n2)。

O(n)的优化解

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n = 20, prod = 1, sum = 0;
    for (int i = 1; i <= n; i++)
    {
        prod *= i;
        sum += prod;
    }
    cout << sum;
    return 0;
}

我们不难可以发现阶乘之和实际上是前面一个阶乘乘上这个数加一（怎么感觉说的比代码还麻烦啊（所以可以用一个变量prod（product）来储存这个乘积，这样就可以达到O(n)了。

当然，数据过大（毕竟阶乘），会出现不可预料的bug，即使long long也存在，不做记载了，题目也不会这么变态的（