GESP 五级 · GESP 202312 C++ 五级 第 8 题

下面C++代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 $N$ 是否素数，有关其时间复杂度的正确说法是（ ）。

bool isPrimeA(int N)
{
    if (N < 2)
        return false;
    for (int i = 2; i <= N / 2; i++)
        if (N % i == 0)
            return false;
    return true;
}

bool isPrimeB(int N)
{
    if (N < 2)
        return false;
    for (int i = 2; i <= sqrt(N); i++)
        if (N % i == 0)
            return false;
    return true;
}

这题考时间复杂度，别被 sqrt 吓住，直接数循环跑几步就行。A 版循环到 N/2，B 版循环到根号 N，最大情况就是都跑完，代入大 O 记号对比大小，选那个描述最准的。

很多孩子看到 sqrt 就下意识觉得是对数，其实 sqrt 是平方根，记成 O(log N) 是典型错误。还有把最坏情况当成平均情况，比如以为大部分数很快就能找到因子，其实题目问的是最坏，得按不找到的情况算。另外容易忽略常数系数，虽然 O(N/2) 和 O(N) 在大 O 里是一样的，但选项里特意写了 N/2，这是为了考你是否真的数了步数而不是瞎蒙。

【考点】时间复杂度分析｜循环次数估算｜最坏情况复杂度

这题看似简单，其实是考你对大 O 记号的理解，以及能不能从代码里准确数出循环次数。命题人专门挑了两个看起来很像、但复杂度级别完全不同的函数，就是想看你有没有细心数步数。

先说 isPrimeA。循环条件是 i <= N/2，也就是说，如果 N 是 100，i 会跑到 50；如果 N 是 1000，i 会跑到 500。最坏的情况就是 N 是素数，循环一次都不 break，一直跑到 N/2 才结束。那迭代次数就是 N/2 次。在大 O 记号里，常数因子可以忽略，所以 O(N/2) 就是 O(N)。但选项 A 里写的是 O(N/2)，这其实是故意把常数写出来，让你确认你真的数对了步数，而不是随便套个 O(N) 就完事。

再看 isPrimeB。循环条件是 i <= sqrt(N)。这里有个关键：sqrt(N) 是平方根，不是对数。比如 N=10000，sqrt(N)=100，循环跑 100 次；N=10^12，sqrt(N)=10^6，循环跑 10^6 次。最坏情况同样是素数，循环跑满，次数就是 sqrt(N)。所以复杂度是 O(sqrt(N))，也就是 O(N^{1/2})。选项 B 里写的 O(N^{1/2}) 完全正确。

现在对比 A 和 B。当 N 很大时，比如 N=10^12，A 要跑 5×10^{11} 次，B 只跑 10^6 次，差距是 5×10^5 倍，B 快得离谱。所以 B 绝大多数情况下优于 A，这个结论符合实际。

再看其他选项为什么错。

A 选项说 B 是 O(log N)，这是最阴险的坑。很多学生看到 sqrt 就联想到对数，其实 sqrt 是平方根，log N 是对数，两者天差地别。比如 N=10^12，sqrt(N)=10^6，log N≈39.8，差了两个数量级。命题人就是想看你是不是把 sqrt 和 log 搞混了。

C 选项把 A 说成 O(sqrt(N))，B 说成 O(N)，完全颠倒，显然是故意反着写，考你细心程度。

D 选项说 A 是 O(log N)，B 是 O(N)，也是胡乱搭配，毫无根据。

所以只有 B 选项完全正确：isPrimeA 最坏 O(N/2)，isPrimeB 最坏 O(N^{1/2})，且 B 绝大多数情况下优于 A。

【考频与趋势】 复杂度分析在 GESP 五级里属于高频考点。题库中复杂度分析共考过 39 题，覆盖 2 个考试级别（2026-2026），其中 2026 年考了 11 题，null 年考了 28 题。分赛事来看，CSP 入门级考了 38 题，CSP 提高级考了 1 题。这说明复杂度分析在入门级中非常常见，而提高级几乎没怎么考，可能是命题人觉得提高级学生已经掌握了基础，不再重复考。

从逐年分布看，2026 年考了 11 题，null 年考了 28 题，说明复杂度分析在近年来的考试中占比很高，尤其是 2026 年及以后。如果继续按这个趋势，复杂度分析在未来几年仍将是必考内容，而且可能会在提高级中逐渐增加。

【预测】 基于现有数据，复杂度分析在 GESP 五级中属于高频考点，未来几年仍会保持较高考频。由于 2026 年考了 11 题，null 年考了 28 题，说明复杂度分析在近年来的考试中占比很高，尤其是 2026 年及以后。如果继续按这个趋势，复杂度分析在未来几年仍将是必考内容，而且可能会在提高级中逐渐增加。暂无足够依据预测具体年份的考题类型，但可以肯定的是，复杂度分析将继续是 GESP 五级的重要考点。