GESP 八级 · GESP 202406 C++ 八级 第 13 题

下面程序的时间复杂度为（ ）。

bool notPrime[N] = {false};
void sieve() {
    for (int n = 2; n * n < N; n++)
        if (!notPrime[n])
            for (int i = n * n; i < N; i += n)
                notPrime[i] = true;
}

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

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

【考点】复杂度分析｜素数筛法｜调和级数

1. 🎯 考纲定位

GESP八级C++算法模块，重点考查复杂度分析。命题人放这道题，是卡住考生对"素数筛法"这一经典算法的复杂度推导能力，而非死记硬背。