GESP 四级 · GESP 202309 C++ 四级 第 17 题

对 $N$ 个元素的数组执行插入排序算法，通常的时间复杂度是 $O(N^2)$。

这道题考算法复杂度记忆。拿到题先别慌，脑子里过一遍常见排序的渐进复杂度表，插入排序最坏和平均都是平方级，最好才是线性的，题干问‘通常’，直接锁定平均情况，选A。

很多学生把‘通常’理解成‘最好情况’，或者下意识联想到快速排序的O(N log N)，结果误选B。其实‘通常’在算法题里就是指平均情况，插入排序平均就是O(N^2)。

这道题考查的是基础排序算法的时间复杂度记忆，属于GESP四级算法模块的必考内容。命题人挖坑的点在于题干中的‘通常’二字，以及考生容易混淆‘最好情况’与‘平均情况’。很多学生看到排序就想到快速排序或归并排序的O(N log N)，或者把插入排序的最好情况O(N)误当成‘通常’情况，从而错误地选择了B。其实‘通常’在算法分析语境下就是指平均情况，而插入排序的平均时间复杂度正是O(N^2)，与最坏情况一致。因此正确答案是A。拿到这种概念题，解题心法很简单：先回忆常见排序的复杂度表——冒泡、插入、选择都是O(N^2)（平均/最坏），快速、归并、堆排是O(N log N)，计数、桶、基数排是O(N)。然后看题干限定词，‘通常’对应平均，‘最好’对应最优，‘最坏’对应最劣。本题直接匹配即可，无需复杂推导。避坑的关键是别被‘插入排序’的名字误导，名字里带‘插’不代表它快，它本质是双重循环，数据量大时确实慢。考频方面，‘排序基础’在题库中共考过249题，覆盖9个考试级别，逐年分布从2008年的2题一路攀升，到2026年已达50题，其中GESP四级考了39题，占比约15%，说明这类基础概念题在四级考试中非常高频，几乎年年必现。趋势上，近五年（2022-2026）排序题年均50题左右，且难度集中在识别算法特性与复杂度匹配，不太会出超纲变种。因此预测未来GESP四级仍会持续高频考查排序算法的复杂度判断，尤其是插入、冒泡、选择这三类O(N^2)排序与快速、归并这两类O(N log N)排序的区分；命题人可能会继续用‘通常’‘平均’‘最坏’等限定词来制造陷阱，也可能偶尔把复杂度与数据规模结合（如‘当N=1000时插入排序大约需要多少次比较’）来增加计算量，但核心还是考记忆与概念辨析。总之，这类题属于‘背了就能拿分’的类型，但一定要把‘通常=平均’这个对应关系刻进脑子里，否则很容易掉进命题人设的坑里。