NOIP 提高 2011 第一轮 第 7 题：应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情

题目

应用快速排序的分治思想，可以实现一个求第 $K$ 大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（     ）。

选项

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

答案

C

题解

考点定位

本题考「快速选择复杂度」,对应大纲 4.1.1 复杂度（难度【3】）。

解题过程

快排分治思想求第 K 大：只递归一侧（quickselect），平均 O(n)（每层期望砍半，n+n/2+n/4+…=2n）。

选 C。

易错提醒

① 平均 O(n)、最坏 O(n²)；② 「不考虑极端最坏」= 按期望分析。