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

下面代码的时间复杂度是（　　）。

int countPairs(int a[], int n) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] + a[j] == 100) {
cnt++;
}
}
}
return cnt;
}

A. B. C. D.

看到嵌套循环先数内层执行次数。外层 i 从 0 跑 n 次，内层 j 从 i+1 跑 n−i−1 次，总迭代数 = Σ(i=0..n−1)(n−i−1) = n(n−1)/2，即 O(n²)。通法：对多重循环，把内层循环次数写成关于外层变量的表达式，再求和；若内层次数与外层变量无关，直接乘；若内层次数随外层线性变化，求和得二次方。

A 选项 O(1) 是绝对化陷阱，循环次数随 n 增长，不可能常数。C 选项 O(n) 误把内层当成 O(1) 或只数外层。B 选项 O(n³) 是常见思维惯性——看到三层就以为 n³，但本题只有两层，且内层次数随 i 递减，不是固定 n。D 选项 O(n²) 才是正确结论。

看到嵌套循环先数内层执行次数。外层 i 从 0 跑 n 次，内层 j 从 i+1 跑 n−i−1 次，总迭代数 = Σ(i=0..n−1)(n−i−1) = n(n−1)/2，即 O(n²)。通法：对多重循环，把内层循环次数写成关于外层变量的表达式，再求和；若内层次数与外层变量无关，直接乘；若内层次数随外层线性变化，求和得二次方。

A 选项 O(1) 是绝对化陷阱，循环次数随 n 增长，不可能常数。C 选项 O(n) 误把内层当成 O(1) 或只数外层。B 选项 O(n³) 是常见思维惯性——看到三层就以为 n³，但本题只有两层，且内层次数随 i 递减，不是固定 n。D 选项 O(n²) 才是正确结论。

1. 考纲定位

本题考查《GESP 考试大纲》四级"时间复杂度"模块。命题人专门放这道题，就是卡住考生"看到嵌套循环就机械乘 n"的惯性思维——四级学生最容易把内层循环次数想成固定 n，从而误选 O(n³)。