median of medians算法推广：偶数规模分组的运行时间求解问询

云原生阿岚

2026-10-3

偶数规模分组的median of medians算法逻辑说明

1. 偶数分组的中位数约定

不需要纠结偶数规模分组的中位数"不存在于集合"的问题：median of medians算法的核心是找到一个足够好的枢轴，保证每次递归可以排除固定比例的元素，因此只需要统一约定取下中位数（分组中第g/2小的元素，存在于集合中）或者上中位数（分组中第g/2 +1小的元素）即可，两种选择的推导逻辑一致，仅系数有微小差异，渐近复杂度结果完全相同。

2. 推导逻辑（以约定取下中位数为例）

和奇数分组的推导逻辑完全一致：

将n个元素划分为大小为g的分组，忽略取整后分组总数为n/g
对每个分组排序，取每个分组的下中位数，共得到n/g个中位数
递归求解这n/g个中位数的中位数，作为全局枢轴pivot
统计比pivot小、等于、大的元素数量，递归求解目标元素所在的分区

最坏情况的子问题规模推导：
所有分组的中位数中，至少有一半小于等于pivot，另一半大于等于pivot。对于所有中位数大于pivot的分组，该分组中至少有g/2 +1个元素大于pivot（下中位数本身 + 所有比下中位数大的元素），因此总共至少有 (n/(2g))*(g/2 + 1) 个元素大于pivot，可以直接排除。
同理也可以排除至少同等数量小于pivot的元素，因此最坏情况下递归的子问题规模为：
n - (n/(2g))*(g/2 + 1) = n*(3g - 2)/(4g)

3. 通用递推式

忽略上下取整的情况下，偶数g对应的通用递推式为：
T(n) = T(n/g) + T(n*(3g-2)/(4g)) + cn
你的直觉推导基本正确，只需要明确中位数的选择约定即可，两种约定下的递推式都满足渐近复杂度的分析要求。
如果约定取上中位数，仅排除的元素方向相反，子问题规模和递推式系数完全相同。