为了避免快速选择的 O(n^2) 最坏情况，我知道 2 个选项：
随机选择一个枢轴索引
使用中位数的中位数 (MoM) 选择一个近似中位数并以此为中心
当使用快速选择的 MoM 时，我们可以保证最坏情况 O(n)。当使用(1)时，我们不能保证最坏情况O(n)，但是算法到O(n^2)的概率应该是极小的。(2) 的开销成本远高于 (1)，后者几乎不会增加额外的复杂性。
那么我们什么时候应该使用其中一个呢？
问问题
196 次
1 回答
1
正如您所指出的，中位数方法比快速选择慢，但具有更好的最坏情况运行时间。假设 quickselect 确实在每一步使用了一个随机选择的枢轴，您可以证明不仅预期的运行时间为 O(n)，而且其运行时间超过 Θ(n log n) 的概率非常非常小（在对于常数 k 的任何选择，最多 1 / n k )。所以从这个意义上说，如果您能够随机选择枢轴，那么快速选择可能会更快。
但是，并非所有快速选择的实现都对枢轴使用真正的随机性，有些使用确定性的枢轴选择算法。不幸的是，这可能导致触发 Θ(n 2 ) 最坏情况运行时的病态输入，如果您有对抗性选择的输入，这将是一个问题。
一旦两者之间的良好折衷是introselect. introselect 背后的基本思想是将快速选择与确定性枢轴选择算法一起使用。在算法运行时，它会跟踪选择枢轴的次数，而不会丢弃至少 30% 的输入数组。如果该数字超过某个阈值，它将停止使用随机枢轴选择并切换到中位数方法来选择一个好的枢轴，从而强制减小 30% 的大小。这种方法意味着，在快速选择快速减小输入大小的常见情况下，introselect 与快速选择基本相同，但记账开销很小。然而，在快速选择会降级为二次的情况下，introselect 停止并切换到最坏情况下的有效中位数方法，确保最坏情况下的运行时间为 O(n)。从本质上讲，这为您提供了两全其美的效果-它
于 2021-04-06T01:19:19.130 回答