基础算法——阶乘和

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也存在,不做记载了,题目也不会这么变态的(