关于时间复杂度的问题

Question

这里用俩段代码，其执行的结果应该是一样的。
但是代码执行的时间却不一样
看看 为什么俩段代码时间花费差这么多。
这段代码花了 1500ms左右

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define ll long long
int cnt = 0;
bool isprime[N]{};
int prime[N]{};
int num[N]{};
int sum[N];
int dp[N]{};
int size = 0;
int not_prime[N]{};
void Solution(int n) {
    //一开始假设全是素数，然后再筛掉
    memset(isprime, true, sizeof(isprime));
    isprime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (isprime[i])prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            // 任何一个合数 = 质数 * 某一个数
            // i * prime[j]是一个合数
            isprime[i * prime[j]] = false;
            not_prime[size++] = i * prime[j];
            //如果prime[j]是i的最小质因子，那么 不管 i*x(x:表示随便一个数）的最小质因子都是 prime[j]
            // 又因为 每一个合数都要由最小质因子筛去，所以 就 不让 i乘其他数了,直接break
            if (i % prime[j] == 0)break;
        }
    }
}
int main(){
    int n;
    cin >> n;
    Solution(n);
    sort(not_prime, not_prime + size);
    size--;

    // for (int i = 0; i <= size;++i)
    //     cout << not_prime[i] << endl;

    for (int i = 0; i <= size; i++)
    {
        dp[not_prime[i]] = dp[not_prime[i] - 1] + 1;
        num[dp[not_prime[i]]]++;
    }
    // for (int i = 0; i <= size;++i){
    //     cout << dp[not_prime[i]] << endl;
    // }
    // for (int i = 1; i <= 3;++i){
    //     cout << num[i] << endl;
    // }

    for (int i = sqrt(n); i >= 1; i--)
        sum[i] += sum[i + 1] + num[i];

    int m;
    while(~scanf("%d",&m)){
        cout << sum[m] << endl;
    }
    //system("pause");
    return 0;
}

这个就花了263ms左右

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int factor[1000005];//记录最小素因子
int prime[1000005],vis[1000005];//记录素数
int dp[1000005],cnt[1000005],sum[1000005];
int p=0;
// 线性筛
void init(int n)
{
    vis[1]=1;
    int i,j;
    for(i=2;i<=n;i++){
        if(factor[i]==0){
            prime[p++]=i;
            vis[i]=1;
            factor[i]=i;
        }
        for(j=0;j<p&&prime[j]*i<=n;j++){
            factor[prime[j]*i]=prime[j];
            if(i%prime[j]==0)
                break;
        }
    }
}
int main(){
    int n,m;
    scanf("%d",&n);
    init(n);
    for(int i=1;i<=n;i++){
        //dp 记录 连续的个数
        if(!vis[i])dp[i]=dp[i-1]+1;
        // cnt[i]: i个连续合数的个数  还不包括区间大于 i 个个数的情况
        // 1234  123 123   1234  cnt[3]=4;  其实3个连续合数的个数不止4个，还要加上 区间长度为4的个数
        // 区间长度为4的 ，是因为 234 也是属于3个连续合数
        // 至于那你为什么不算区间长度为5的？5的不是包含区间长度为3的吗？
        // 其实区间长度为5的，我们已经在算3之前，我们已经细分成 很多个 长度为4的区间了
        cnt[dp[i]]++;
    }
    // 3个连续合数的个数 = cnt[3] + 4个连续合数的个数

    for (int i = (n); i >= 1; i--)
        sum[i] = sum[i + 1] + cnt[i];
    while(~scanf("%d",&m)){
        printf("%d\n",sum[m]);
    }
    return 0;

}

我觉得时间应该花的差不多呀，怎么提交结果的时候，上面的代码还时间超限了。

Answer 1

你上面代码多了一个sort函数调用啊，排序可能是O(n^2)，比较耗时