关于Median of Medians高效算法的疑问：教授内容与资料不符

我明白你查了大量资料却没理清教授讲法和其他教材内容的关系，确实容易搞混——其实这俩说的是同一个算法的不同环节，完全不冲突，我给你拆解一下：

• 教授讲的是算法的核心pivot选取步骤
  把数组按每组5个元素拆分，找出每组的中位数组成新数组，再递归对这个新数组执行同样的分组找中位数操作，直到得到单个元素——这个元素就是我们要找的基准点（pivot）。这正是Median of Medians算法用来保证高效性的核心步骤，目的是选出一个足够“好”的pivot，避免像普通快速选择那样出现最坏O(n²)的情况。

• 其他资料提到的30:70分割，是这个pivot划分原数组后的最坏比例
  当用刚才选出的pivot去把原数组分成“小于等于pivot”和“大于等于pivot”两部分时，最坏情况下，其中一部分的规模最多是原数组的70%，另一部分至少是30%。这个比例是可以推导出来的：
  假设原数组有n个元素，分成n/5组；新数组的中位数pivot，至少比新数组里一半的中位数要大（或小）。对应到原数组的分组里，这一半的分组中，每组至少有3个元素（中位数+组里比中位数大的2个）是大于等于pivot的，算下来就是至少3*(n/10)=0.3n个元素大于等于pivot，反过来也至少有0.3n个元素小于等于pivot。所以划分后，递归处理的子数组规模最多是0.7n。

• 两者结合才是O(n)时间复杂度的来源
  算法的时间复杂度递归式可以写成 T(n) = T(n/5) + T(7n/10) + O(n)，解这个式子就能得到T(n)=O(n)——这正是教授说的线性时间复杂度的依据。

简单来说，教授聚焦的是“怎么选pivot”，其他资料聚焦的是“选出来的pivot能保证划分成什么样的比例”，两者是同一个算法的前后环节，本质是统一的。

内容的提问来源于stack exchange，提问作者Geeky-Alam