NOIP 普及 2010 第一轮 第 12 题：基于比较排序的时间复杂度下界

题目

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

选项

• A. $\Theta(n)$
• B. $\Theta (n \log n)$
• C. $\Theta (\log n)$
• D. $\Theta(n^2)$

答案

B

题解

考点定位

本题考「比较排序下界」,对应大纲 4.1.3 排序（难度【2】）。

解题过程

n 个元素有 n! 种排列，每次比较二分区分 ⇒ 决策树高度 ≥ log₂(n!) = Θ(n log n)（Stirling 公式）。

选 B。

易错提醒

① 这是基于比较的下界——计数排序等非比较排序可 O(n)；② 归并/堆排序达到该下界。