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

下面两层循环的时间复杂度是 $O(n^2)$。

for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j *= 2) {
cout << i + j;
}
}

外层循环 i 从 0 到 n-1 执行 n 次，内层循环 j 从 1 开始每次乘以 2 直到≥n，这是典型的对数级循环，执行次数为 log₂n。总操作数 = n × log₂n = O(n log n)。

学生容易把内层循环误判为线性增长，套用"两层循环就是 O(n²)"的机械记忆，或者忽略 j*=2 的指数特性。

1. 考纲定位

本题考查《GESP 四级算法模块》中的时间复杂度分析与对数级循环识别。命题人专门放这道题，就是要卡住那些只会背"两层循环=O(n²)"公式、缺乏真正推导能力的考生——这是四级算法题最典型的"套路陷阱"。

2. 解题思维

看到题先想循环次数：外层 i 从 0 到 n-1，执行 n 次；内层 j 从 1 开始，每次乘以 2，直到 j ≥ n。内层循环次数 = ⌊log₂(n-1)⌋ + 1，即 O(log n)。总复杂度 = n × log n = O(n log n)。