中位数的中位数算法：分组为4的递归式与时间复杂度影响

为什么选择大小为5的块？ #

选择5作为分组大小是线性时间复杂度的最小平衡点，核心原因有两点：

1. 递归规模可控：将数组划分为5元素块后，通过中位数的中位数选主元，能保证主元至少比3/10的元素小、同时至少比3/10的元素大。这意味着递归处理划分后的数组时，规模最多为7n/10，结合递归找中位数的中位数的规模n/5，两者系数和为1/5 + 7/10 = 9/10 < 1，满足主定理条件，最终得到线性时间复杂度Θ(n)。
2. 开销与效率平衡：奇数分组无需处理偶数分组中“双中位数取平均”的额外逻辑，减少常数级开销。5是满足“递归系数和小于1”的最小奇数——分组更小（如3）会导致递归剩余规模系数过大（2n/3），系数和1/3+2/3=1，时间复杂度退化为Θ(n log n)；分组更大（如7）虽能缩小剩余规模，但每组排序的常数开销会增加，实际运行效率不如5。

划分为大小为4的块的影响 #

当分组大小为4时，递归式和时间复杂度都会发生本质变化：

递归式推导 #

• 将数组划分为n/4个块，每个块排序后取中位数（通常选两个中间元素中的一个，如下中位数）。
• 以这些块中位数的中位数作为主元时，能保证主元至少比1/4的元素小（至少一半的块的中位数≤主元，每个块中有2个元素≤该块的中位数），同理至少比1/4的元素大。
• 因此递归处理划分后的数组规模最多为n - n/4 = 3n/4，加上递归找中位数的中位数的规模n/4，以及分组排序的线性开销Θ(n)，最终递归式为：

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

时间复杂度变化 #

这个递归式无法得到线性时间复杂度。通过递归树分析：每层总开销为n（T(n/4)+T(3n/4)的开销之和为n，加上线性分组开销），递归深度为log_{4/3}n，总时间复杂度退化为Θ(n log n)，和普通快速排序的最坏时间复杂度一致，失去了中位数的中位数算法的线性时间优势。

为什么推荐奇数分组？ #

奇数分组的核心价值在于明确的中位数位置和可控的递归规模下界：

• 奇数个元素的块中，中位数是唯一的中间元素，无需额外处理偶数块的“双中位数”选择问题，避免了逻辑复杂度和常数开销。
• 更关键的是，对于奇数k，每组中位数能保证比(k-1)/2个元素大、比(k-1)/2个元素小。当取所有块中位数的中位数作为主元时，至少有一半的块的中位数≤主元，因此主元至少比一定比例的元素小，只有当这个比例足够大，使得递归剩余规模的系数与递归找中位数的系数之和小于1时，才能得到线性时间复杂度。
  • 例如k=5时，最终剩余规模为7n/10，系数和9/10<1，满足线性时间要求；而偶数k（如4）无法达到这个效果，会导致系数和等于1，时间复杂度退化。

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