NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 12 题

基于比较的排序时间复杂度的下限是（ ），其中 $n$ 表示待排序的元素个数。

这题考的是基于比较排序的时间复杂度的理论下限。拿到题先想：排序本质是分辨n!种排列，每次比较最多把可能性劈半，所以比较次数至少是log₂(n!)，再结合斯特林公式就能得出答案。

很多同学看到排序就下意识想冒泡或快排，觉得n²或n log n就是答案，却忽略了题目问的是所有基于比较的算法的‘下限’。还有人容易把非比较排序（如计数排序O(n)）混进来，或者把Θ(n log n)和O(n log n)搞混——注意这里问的是下界，必须用Θ。

考点与概念

这道题考查的是基于比较的排序算法的时间复杂度下限，核心知识点是决策树模型和斯特林公式。

所谓“基于比较的排序”，指的是像冒泡、插入、选择、快速、归并、堆排序这类，只通过元素两两比较大小来决定移动顺序的算法。这类算法无论怎么优化，都有一个理论上的最低比较次数。

命题人怎么挖坑

命题人最喜欢在这里设两个坑： 1. 概念混淆：把“非比较排序”（如计数排序、基数排序）的O(n)当成答案。注意，题目明确限定“基于比较”，所以计数排序这种靠下标直接定位的算法不算在内，它确实能突破n log n，但不符合题意。 2. 符号混淆：把Θ(n log n)写成O(n log n)。O只表示上界，而题目问的是下界，必须用Θ（紧确界）。