咨询在线获取的LeetCode题解（Quick Select）时间复杂度是否为O(n)

嘿，这个问题问得挺到位的！咱们来仔细聊聊你这段快速选择代码的时间复杂度～

核心结论 #

• 这个快速选择解法的平均时间复杂度是O(n)，但最坏情况下是O(n²)

为什么平均是O(n)？ #

快速选择的核心是分治思想：每次选一个pivot把数组分成三部分（大于pivot、等于pivot、小于pivot），然后只递归处理包含第k大元素的那一部分——不像快速排序那样需要处理所有子数组，这是它比快排高效的关键。

时间复杂度的计算可以拆解为：

• 第一次遍历数组划分元素：O(n)
• 第二次递归处理的子数组长度平均是原数组的1/2：O(n/2)
• 第三次递归处理的子数组长度平均是原数组的1/4：O(n/4)
• ...
• 直到子数组长度缩小到1

把这些步骤的时间加起来：n + n/2 + n/4 + ... + 1，这是一个等比数列求和，结果趋近于2n，所以整体是**O(n)**的时间复杂度。

为什么最坏情况是O(n²)？ #

如果每次选择的pivot都很“糟糕”——比如每次选到的都是当前数组里的最小值或最大值，那每次递归只能排除掉一个元素（pivot本身），此时时间复杂度就变成：
n + (n-1) + (n-2) + ... + 1，这是等差数列求和，结果是n(n+1)/2，也就是O(n²)。

你代码里选择nums[parseInt(nums.length/2)]作为pivot，比选首尾元素的情况要好很多，能大幅降低最坏情况出现的概率，但理论上还是存在极端场景触发最坏复杂度的可能。

额外补充 #

如果想要保证最坏情况下也是O(n)，可以采用更严谨的pivot选择策略，比如“中位数的中位数”方法，但在LeetCode的刷题场景中，你当前的写法已经足够通过绝大多数测试用例了——毕竟测试用例不会专门构造极端数据来卡这种实现。

内容的提问来源于stack exchange，提问作者motioncity