GESP 七级 · GESP 202606 C++ 七级 第 13 题

某算法需要枚举 $n$ 个对象；对每个对象，还需要进行一次二分查找。若二分查找的对象规模也是 $n$，则该算法的时间复杂度通常为（ ）。

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

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

【考点】时间复杂度分析｜二分查找

枚举n个对象，每个对象执行一次二分查找。二分查找在规模为n的数组中完成一次需要O(log n)时间，而枚举n个对象意味着n次这样的操作，因此总时间复杂度为n × log n = O(n log n)。这里关键是理解"复合操作"的乘法关系——不是相加而是相乘，这是无数学生因混淆运算逻辑而丢分的核心原因。

陷阱方面，选项A的O(n)常见于只关注枚举步骤而忽略后续查找；选项C的O(n²)则误将二分查找当作O(n)线性查找；选项D的O(log n)更是只盯着二分查找本身，完全忘记枚举的n次循环。命题人利用的正是学生对"总复杂度=单步复杂度×执行次数"这一基本模型的陌生，以及将二分查找与线性查找混为一谈的惯性思维。

反命题角度，若将二分查找改为线性扫描，答案会直接变为O(n²)；若枚举次数改为√n，则总复杂度为O(√n log n)。刷到类似题时，先问自己"这次是乘还是加？操作了几次？"，这是破题的关键。