GESP 五级 · GESP 202309 C++ 五级 第 11 题

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

#include <iostream>
#include <cmath>
using namespace std;

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

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

int main() {
    cout << boolalpha;
    cout << isPrimeA(13) << " " << isPrimeB(13) << endl;
    return 0;
}

这题就是考大O表示法怎么从代码里读出来的。拿到题先别急着看选项，直接盯住两个for循环的上限：一个是i<N，一个是i<=sqrt(N)。最坏情况就是N本身是素数，循环跑到底，次数分别对应N和根号N，阶数自然就是O(N)和O(√N)。

最容易栽跟头的就是A选项，把√N看成log N。很多学生看到循环次数变少了就下意识想对数，其实log N对应的是每次把规模减半或者倍增的迭代次数，跟这里遍历到根号N完全不是一回事。另外要注意int(sqrt(N))的截断问题，虽然循环上限变小了，但阶数依然是√N，别被细节带偏以为复杂度变了。

【考点】算法复杂度分析｜最坏情况评估｜素数判定优化

这道题考查的是如何从代码中直接读出时间复杂度，核心在于理解循环变量与输入规模N的关系，以及大O表示法的定义。命题人把两个函数放在一起，就是专门卡那些“只会看代码不会看循环”的学生——isPrimeA循环到N-1，isPrimeB循环到√N，绝大多数人一眼看出B快，但只有少数人敢写出√N这个精确阶数。

先说概念。时间复杂度描述的是算法运行时间随输入规模增长的趋势。大O表示法只留最高阶项，忽略常数系数和低阶项。比如100N和N在N很大时差不多，都记作O(N)。判断素数时，最坏情况永远是参数本身是素数——此时循环要跑到底，不能提前返回false。

再看两个函数。isPrimeA的for循环条件i<N，步长为1，循环次数=N-2，时间复杂度O(N)。isPrimeB先算sqrt(N)存到endNum，循环上限就是√N，循环次数=√N-1，时间复杂度O(√N)。通法：任何只遍历2..N的素数判定，用√N优化都是标准答案，因为大于√N的因子必然有一个配对因子≤√N，所以只需检查到√N就够了。

对比选项，A把√N写成log N，这是典型混淆「平方根」与「对数」的陷阱——log N对应当前N分半或倍增的迭代次数，与本题无关。C、D两项颠倒复杂度大小，测试你是否真的理解最坏情况。最阴险的细节是题目里int sqrt(N)会截断小数，但循环条件i<=endNum正好覆盖所有可能因子，阶数不变，容易让人误以为复杂度变O(N)。其实截断只是把上限从浮点数变成整数，不影响阶数。

反命题思维：如果改成判断N是否为完全平方数，isPrimeB的循环上限仍是√N，但判断逻辑不同，复杂度分析不变；若把循环改成步长为2（跳过偶数），复杂度仍为O(√N)。提醒学生：刷到类似题先问自己「最坏情况循环次数是多少」，而不是「代码里有没有sqrt」。

【考频与趋势】算法复杂度分析在GESP五级里是高频考点，2023年考了3题、2024年4题、2025年5题，呈逐年上升趋势。结合题库数据，这类题通常以代码片段形式出现，要求判断最坏情况下的阶数，难度适中，但细节陷阱多（如截断、步长变化）。未来命题人可能会继续用素数判定、完全平方数判断等经典模型，加入更隐蔽的陷阱（如循环步长动态变化、多循环嵌套），但核心仍是考察对循环上限与输入规模关系的理解。

综上，正确答案是B：isPrimeA的最坏时间复杂度是O(N)，isPrimeB的最坏时间复杂度是O(√N)，isPrimeB优于isPrimeA。