algorithm - 平均情况下 R-Select 与 Select 的运行时间？

Question

在最坏的情况下，R-select 是 O(n^2)，而 select 是 O(n)。有人可以解释和对比他们在一般情况下的行为吗？

Ps - 我不确定它是否是一个重复的问题。如果是这样我可以删除！谢谢！！

Answer 1

通过 R-select，我假设您正在谈论随机选择算法，该算法通过选择一个枢轴，在该枢轴上进行分区，然后从那里递归地进行。如果不是这样，请告诉我！

R-select 算法的最坏情况是 Θ(n ² ) 是正确的，但这在实践中极不可能出现。这要求您非常频繁地选择一个远离最小值或最大值的恒定元素数内的枢轴，并且发生这种情况的可能性呈指数级低。O(n) 的平均情况运行时间实际上很可能发生；例如，您可以证明对于任何常数 k，运行时间为 O(n log n) 的概率至少为 1 - 1/n ^k。

隐藏在 R-select 的 big-O 表示法中的常数项实际上非常低，实际上如此低，以至于 R-select 通常比中位数选择算法快得多。事实上，它们有时会结合在一起。introselect 算法通过运行 R-select 并查看运行时来工作，如果运行时最终看起来很糟糕，则切换到中位数选择算法。整个运行时间是最坏情况 O(n) 并且与 R-select 相当。