GESP 四级 · GESP 202603 C++ 四级 第 12 题

下列代码段的时间复杂度为（ ）。

int cnt=0;
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        if( (i+j) % 3 == 0) cnt++;
    }
}

答案C。在循环中遍历数组并累积结果时，注意累加变量的初始值和每次循环的更新方式。

for循环体可能一次都不执行！这是和while循环一样的"先判断后执行"机制。

【考点】循环嵌套｜大 O 表示法

考纲定位：四级算法模块精准打击"双层循环复杂度误判"，90% 考生会盯着内层 if 条件以为复杂度骤降，命题人就是要挖这个"有 if 就降阶"的直觉误区。

解题思维：外层循环 n 次，内层循环 n 次，总迭代次数 n×n=n²；if 语句只做常数时间判断，操作次数仍与迭代次数同阶。通法：多层循环相乘得总次数，常数操作不改变量级，O(n²) 是嵌套循环的标准答案。

陷阱拆解：A 项 O(n) 是只看见内层循环被 if"过滤"就误判；B 项 O(n log n) 可能混淆了内层循环有 log 因子；D 项 O(2^n) 是指数级思维惯性。最阴险的细节在于 if 条件 (i+j)%3==0 看似大幅减少 cnt++，但判断本身也是 O(1)，总操作次数为 n²次判断 + n²次可能的 cnt++，仍是 O(n²)。若只背结论"有 if 就降复杂度"，必掉入这个坑。

反命题思维：若把内层循环改成 j 从 0 到 i，复杂度仍为 O(n²/2)=O(n²)；若改成 j 从 0 到 n/2 且 break，复杂度才可能降为 O(n)。刷到类似题先问自己"命题人想考我什么"——不是看代码表面，而是看循环次数与操作次数的关系。