关于阶乘问题

碰到了一个题，使用vector超时了，使用一般的低级数组，没有超时。

一般数组：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n)
    {
        if(n == 0 || n == 1)
        {
            cout << 1 << endl;
        }
        else
        {
            int a[100000] = {0}, i, j, sum, t, k, q;
            a[0] = 1; // 初始化数组，存储阶乘的结果
            k = 1;    // 数组的有效位数，初始为1
            for(i = 2; i <= n; i++)
            {
                sum = 0; // 进位
                for(j = 0; j < k; j++)
                {
                    t = a[j] * i + sum; // 计算当前位乘积加上进位
                    a[j] = t % 10; // 当前位更新为结果的个位
                    sum = t / 10;  // 计算新的进位
                }
                while(sum)
                {
                    a[k++] = sum % 10; // 处理剩余的进位
                    sum /= 10;
                }
            }
            for(q = k - 1; q >= 0; q--)
                cout << a[q]; // 倒序输出数组内容，即大数的各个位
            cout << endl;
        }
    }
    return 0;
}

容器vector

#include<iostream>
#include<vector>
using namespace std;

//不建表，只在需要的时候计算阶乘，并且避免存储所有的阶乘结果
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i ++)
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}
vector<int> factor(int n)
{
    vector<int> res(1,1);
    for(int i = 1; i <= n; i ++)
        res = mul(res,i);

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n)
    {
        vector<int> C = factor(n);
        for(int i = C.size() - 1; i >= 0; i --)
            cout << C[i];
        cout << endl;
    }

    return 0;
}

两个代码的思路相同，分析起来代码复杂度也相同，但是代码1在每次调用mul()函数的时候都会创建一个新的向量vector<int>C，这涉及到频繁的内存分配和释放操作，效率较低。向量操作比代码2中的数组操作略微复杂。

代码2使用一个固定大小的数组，不会频繁进行内存分配操作，因此运行效率较高；普通数组数组操作更加低级且高效