GESP 五级 · GESP202609 C++ 五级 第 20 题

下面程序的时间复杂度为 $O(n)$。

for (int i = 1; i <= n; i *= 2) {
cout << i << endl;
}

看到这题先想循环变量 i 每次乘 2，属于指数增长，循环次数是 log₂n。代入 n=1024 验算：i 依次为 1,2,4,8,16,32,64,128,256,512,1024，共 11 次，即 log₂1024+1=11，确为 O(log n)。通法：凡变量每次乘常数（或除常数）的循环，复杂度必为对数级。

选项 A 把"循环次数"偷换成"循环变量上限"，诱导考生误判为 O(n)；选项 B 才是正确判断。最阴险的细节是"i 从 1 开始"而非 0，导致迭代次数比 log₂n 多 1，但量级不变。

考纲定位 本题考查 GESP 五级《算法复杂度》模块，命题人卡住的是"看到循环就默认 O(n)"的惯性思维。五级要求掌握常见复杂度识别，此题就是专门挑出对数级循环来筛掉只会背公式的考生。

解题思维 看到 i *= 2 立刻想到指数增长，循环次数是 log₂n。代入 n=1024 验算：i 依次为 1,2,4,8,16,32,64,128,256,512,1024，共 11 次，即 log₂1024+1=11，确为 O(log n)。通法：凡变量每次乘常数（或除常数）的循环，复杂度必为对数级。

陷阱拆解 选项 A 把"循环次数"偷换成"循环变量上限"，诱导考生误判为 O(n)；选项 B 才是正确判断。最阴险的细节是"i 从 1 开始"而非 0，导致迭代次数比 log₂n 多 1，但量级不变。

反命题思维 若把 i *= 2 改成 i++，复杂度立刻变 O(n)；若改成 i *= 3，仍是 O(log n) 但常数因子变大。