GESP 五级 · GESP 202406 C++ 五级 第 8 题

上题代码的时间复杂度是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

1. 🎯 考纲定位

GESP 五级《算法基础》模块核心考点，命题人专盯“能数出循环次数却分不清操作量级”的学生。五级不考复杂 DP/贪心，偏偏考复杂度，就是要卡住那些只会背结论、不会看代码的学生。在《GESP 考试大纲》中，时间复杂度属于第 5 级“算法基础”中的“复杂度分析”子项，命题人放这道题，就是测试学生是否真正理解 O(n) 的含义，而不是死记硬背。

2. 🧠 解题思维

看到题先想代码结构：单层 for 循环，迭代次数 n 次，每次循环内只做常数操作（如一次赋值、一次比较、一次加法）。总操作量 = n×1 = n，即 O(n)。通法：数循环嵌套层数（层数=对数因子），每层判断是常数还是变量（变量=乘数），乘起来就是复杂度。线性复杂度代码的特征是只有一个循环，且循环体中没有嵌套循环或递归，每次操作都是常数时间。