3

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

所以我去维基百科看看是否有一个比CLRS分析更少的快速解释（为了在我跳回CLRS进行分析之前理解算法）。我想到了这一点，特别是“最后，选择“中位数的中位数”作为支点。” 从维基百科中描述的声音来看，“选择”没有找到真正的中位数，而是一个足够中位数的元素，用于选择快速排序的枢轴。

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

4

1 回答 1

3

它找到绝对中位数。

正如您所说，“选择”没有找到真正的中位数，而是一个足够中位数的元素，用于选择快速排序的枢轴。 特别是它足够中值，可以保证在每次迭代中至少丢弃 30% 的数据集。不幸的是，这也是一项昂贵的操作。

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

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

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

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

于 2012-01-25T15:09:34.063 回答