GESP 七级 · GESP 202412 C++ 七级 第 14 题

下面 init_sieve 函数的时间复杂度为（ ）。

int sieve[MAX_N];
void init_sieve(int n) {
    for (int i = 1; i <= n; i++)
        sieve[i] = i;
    for (int i = 2; i <= n; i++)
        for (int j = i; j <= n; j += i)
            sieve[j]--;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】时间复杂度分析｜嵌套循环迭代计数｜调和级数

🎯 考纲定位

GESP 7级 算法复杂度分析模块。命题人把这道题扔进来，就是要卡住那些只会背"三层循环就是O(n³)"的考生——他们看到两层循环就慌慌地选C，完全没管内层循环的步长随i增大而变大，迭代次数会越来越少。