NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 17 题

（ ）的平均时间复杂度为 $O(n \log n)$，其中 $n$ 是待排序的元素个数。

看到平均O(n log n)先别急着套公式，直接想：快排平均是O(n log n)最坏会退化到O(n²)，归并排序稳如泰山，插入和冒泡都是O(n²)。题目问平均，所以快排和归并都入选。

很多学生看到快排就只记得最坏O(n²)或者只记得平均O(n log n)却忘了它属于随机化算法，容易漏选A；还有人会把堆排序（O(n log n)）误当成本题选项，其实堆排不在题干给出的四个里；更常见的是把插入排序或冒泡排序的O(n²)记混成O(n log n)，导致多选C或B。

考点与概念

本题考的是经典排序算法的平均时间复杂度。核心概念在于：平均复杂度是算法在随机输入下的期望表现，而最坏复杂度则是极端情况下的上限。

命题人视角

命题人喜欢出这种“陷阱型”选择题：快排的平均复杂度确实是O(n log n)，但最坏情况是O(n²)，很多学生只记结论不记来源，看到O(n²)就下意识排除，结果漏选A。归并排序则没有这种陷阱，它稳定地保持O(n log n)。插入排序和冒泡排序在平均和最坏情况下都是O(n²)，属于典型的“平方级”算法，用来对比O(n log n)的算法。