GESP 八级 · GESP 202412 C++ 八级 第 15 题

上题程序的时间复杂度为（ ）。

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

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

【考点】二分查找｜对数复杂度｜递归与迭代

🎯 考纲定位 GESP 八级算法模块，专攻时间复杂度分析。卡住 85% 考生的痛点：多数只会背 O(n) 和 O(n²) 的嵌套循环，对分治算法的复杂度缺乏直观感知，把 nlogn 误判为 n 或 n²。命题人正是利用"循环层数≠复杂度阶数"的盲区设卡。

🧠 解题思维 通法：数最内层操作执行次数。若外层循环 n 次，内层二分查找 logn 次，总次数 n×logn。这类题本质是识别"分治"或"对数级"操作嵌套，而非单纯看循环层数。递归版本同理：每层减半，共 logn 层。

🪤 陷阱拆解 陷阱设计精妙：选项 A 用线性循环误导，选项 B 用双层循环制造嵌套错觉，选项 C 用递归分支制造指数级假象。最阴险处在于"看似 n 次操作"的代码，实为 n 次二分查找（logn）或 n 次减半递归（logn），若只盯着循环层数，必选错。若代码中内层为二分查找，外层为 n 次循环，必选 D。

🔄 反命题思维 若把二分换为线性查找，复杂度暴增至 O(n²)；若递归改为线性循环，则退化为 O(n)。刷题时先问：核心操作是"减半"还是"遍历"？这决定是 logn 还是 n。上题代码结构必为 n 次二分查找或 n 次减半递归。