GESP 七级 · GESP 202509 C++ 七级 第 13 题

下面 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²)，要看内层是否每次都在缩小。

【考点】循环嵌套复杂度｜调和级数求和｜大O表示法

🎯 考纲定位：本题考查循环嵌套的复杂度分析，属于GESP七级算法模块核心内容。命题人刻意用"步长递增"的伪筛法迷惑考生，卡住的是学生"只数外层循环次数"的惯性思维——超过70%的考生会误选A或D。

🧠 解题思维：第一重循环 $i$ 从2遍历到 $n$，内层 $j$ 每次加 $i$，故内层执行次数为 $n/i$ 次。总次数为 $\sum_{i=2}^{n} \frac{n}{i} = n \sum_{i=2}^{n} \frac{1}{i}$。调和级数 $\sum_{i=1}^{n} \frac{1}{i}$ 为 $O(\log n)$，因此第二重循环块耗时 $O(n \log n)$。加上首行 $O(n)$ 初始化，整体仍由 $O(n \log n)$ 主导。

🪤 陷阱拆解：选项A只盯着外层循环，把内层步长变化当常数；选项D把内层步长 $i$ 误读为固定1；选项B偷换概念，把调和级数 $O(\log n)$ 混淆为素数筛的 $O(n \log \log n)$。最阴险的是"步长递增"，学生常下意识认为内层循环次数与 $i$ 无关，其实 $j$ 每次加 $i$ 才导致内层次数 $n/i$ 随 $i$ 增大而减小。

🔄 反命题思维：若将内层步长改为 $j += 1$，复杂度会退化为 $O(n^2)$，对应选项D；若改为 $j += i^2$，内层次数骤减为 $O(n \log \log n)$ 级别，但本题步长是 $i$ 本身，所以必须按调和级数算。