CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 5 题

在一个长度为 $n$ 的数组中找到第 $k$ 大的数字，平均的算法时间复杂度最低的是：

这题考的是‘找第k大’的平均时间复杂度。别一上来就排序，要想到快速选择（Quickselect）：用随机枢轴把数组分成左右两部分，只递归处理包含第k大元素的那一半，这样期望比较次数是线性的。

很多学生会误选O(nlog n)，理由是‘排序最快就是O(nlog n)’，却忘了题目问的是‘第k大’而非‘全部有序’。还有人会纠结最坏情况O(n^2)，以为平均也是O(n^2)，其实随机枢轴把坏情况概率压到极低，平均就是O(n)。

这道题考查的是‘在无序数组中找第k大元素’的算法复杂度，核心在于区分‘排序’与‘选择’两种任务的本质差异。命题人喜欢挖坑的地方，就是把‘排序最慢也要O(nlog n)'这个常识套用到‘找第k大’上，诱导学生选C；或者让学生忽略‘平均’二字，只盯着最坏情况，从而误选D。要避开这些坑，必须从算法设计思路入手：如果我们要找第k大，真的需要把整个数组排好吗？显然不需要，只要能把数组划分成‘比目标大’和‘比目标小’的两部分，且目标落在其中一部分，我们就能直接丢弃另一部分，继续只处理包含目标的那一半。这就是快速选择（Quickselect）的核心思想。具体操作是：随机选一个枢轴pivot，用一次线性扫描把数组分成左、右两段，左段全≥pivot，右段全<pivot。如果第k大恰好落在左段，就递归处理左段；否则处理右段。关键在于‘随机枢轴’：虽然最坏情况下（每次都选到最大或最小值）复杂度会退化为O(n^2)，但随机选择的期望比较次数是O(n)。为什么？因为无论数组多大，每次划分平均能排除掉大约一半的元素，递归深度期望为O(log n)，每层总工作量O(n)，乘起来就是O(n log n)？不对，这里有个微妙之处：快速选择的递归树并不是平衡的，但随机枢轴使得‘只处理包含目标的那一半’的概率很大，实际期望总比较次数是线性的，证明可以用归纳法或积分法，结论就是O(n)。相比之下，排序法（如快排、归并）必须处理所有元素，复杂度天然O(nlog n)；冒泡或插入排序最坏O(n^2)，平均也是O(n^2)；O(nk)是每次线性扫描找第k大，显然太慢。因此正确答案是A。在考试中，看到‘第k大’‘平均’‘线性’这些关键词，就要立刻联想到Quickselect，而不是盲目套用排序复杂度。