algorithm - 中位数选择算法 - 它找到绝对中位数，还是接近绝对中位数的 "median of medians"？

Question

CLRS 第 3 版第 9.3 节“最坏情况线性时间的选择”讨论了“选择”算法(由于 Blum、Floyd、Pratt、Rivest 和 Tarjan，有时称为 BFPRT 算法)用于查找 a 的中值在最坏的情况下在 O(n) 时间内列出。当我试图在白板上运行示例时，我有点困惑。我知道每次调用“选择”时都可以消除一定数量的元素(我读过 30% 被消除，而 70% 需要再次检查)，我感到困惑的是数组的哪一部分可以消除，即如果数组被可视化为一个高度为 5，宽度为 n/5 的矩阵，那么被消除的元素位于哪个或哪些象限？我最初认为它是两个对角相邻的象限，但现在我认为它只是一个象限，具体取决于中位数的中位数是多少(请参阅步骤 5、6 和 7 here)。

所以我去维基百科看看有没有比CLRS分析更少的快速解释(为了在我跳回CLRS分析之前理解算法)。我来了this ，特别是“最后，选择“中位数的中位数”作为枢轴。”从维基百科的描述来看，“选择”并没有找到真正的中位数，而是找到了一个足够中位数的元素，以便为快速排序选择一个枢轴。

那么“选择”在真实中位数方面做了什么，它是如何做到的？通过所有这些想到的短语是“部分层次结构”，据我所知，这是“选择”起作用的原因，但是根据这个部分层次结构，您可以根据什么逻辑从列表中消除元素作为中值？

Answer 1

它找到绝对中位数。

正如您所说，“选择”并未找到真正的中值，而是找到一个足够中值的元素，以便为快速排序选择一个基准。特别是它的中值足够大，它是保证在每次迭代中至少丢弃 30% 的数据集。不幸的是，这也是一项昂贵的操作。

关键思想是每5个元素中位数小于等于3个中位数的中位数小于等于3个。因此，对于 5 个一组的一半，每 5 个元素中有 3 个小于或等于 3，因此至少有 30% 的集合小于或等于它。所以它在数据集中最大的 70%。

同样是在最小的70%的数据集中。

这保证您可以避免 quickselect 的潜在陷阱，即选择具有极值的枢轴点。

如果您希望将效率和最坏情况结合起来，您可以将其与快速选择结合起来。例如 4 轮快速选择，然后是 1 轮快速选择，然后是 4 轮快速选择，等等。昂贵的 BFPRT 轮保证 O(n)，而平均而言快速选择会很快。通过推迟第一轮 BFPRT 直到完成几轮快速选择，您可以使额外的运行时间仅比快速选择平均多几个百分点。 (最坏的情况成本会增加很多，但我们预计不会遇到这种情况。)