基于分位数的快速排序：25-75分割为何时间复杂度为O(n log n)？

嘿，我完全懂你的困惑！当初我第一次琢磨分位数分割的快排复杂度时，递归树分析也让我绕了好一阵子，咱们一步步把这个问题拆明白。

先明确25-75分割的核心特点 #

首先，这种策略下，每次选择基准并分割数组后，两个子问题的大小都不会超过原问题的75%（对应另一部分至少占25%）。和普通快排最坏情况（每次分割成1和n-1）不同，这里子问题的规模被严格限制在原问题的3/4以内——这是复杂度能稳定在O(n log n)的关键。

用递推式+递归树双角度分析 #

1. 递推式推导 #

设T(n)为处理n个元素的时间复杂度：

• 每次分割数组需要遍历所有元素，耗时O(n)；
• 递归处理最大的子问题（规模最多为3n/4），耗时T(3n/4)；
• 更小的子问题（规模≥n/4）的耗时肯定不会超过T(3n/4)，所以可以统一写成：

  T(n) ≤ T(3n/4) + O(n)
  

2. 递归树展开分析 #

我们把递归过程拆成树状结构来看：

• 第一层（根节点）：处理n个元素，耗时O(n)；
• 第二层：处理一个规模为3n/4的子问题和一个规模为n/4的子问题，两者总元素数还是n，总耗时依然是O(n)；
• 第三层：两个子问题各自分割后，最大的子问题规模是(3/4)²n，所有子问题的总元素数还是n，总耗时O(n)；
• ...以此类推，直到子问题规模缩小到1（叶子节点）。

关键：递归树的层数

我们需要算树有多少层：当子问题规模缩小到1时，(3/4)^k * n ≤ 1，解这个不等式得k ≈ log_{4/3}n——这是一个对数级别的层数（底数不影响大O符号，因为log_b n = log n / log b，是常数倍数关系）。

总复杂度计算 #

每一层的总耗时都是O(n)，层数是O(log n)，所以总时间复杂度就是O(n * log n)。

对比普通快排的最坏情况 #

普通快排最坏情况是每次分割成1和n-1，递归树层数是O(n)，总耗时是n + (n-1) + (n-2) + ... + 1 = O(n²)。而25-75分割通过限制子问题的最小规模，直接把层数从线性压到了对数级别，自然就避免了最坏情况的平方复杂度。

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