algorithm - Select算法中的好支点VS“坏支点”有什么区别？

Question

我试图理解Select 算法，但我遇到了a good pivot VS a bad pivot. 我可以看到该算法正在使用Partition算法来分离枢轴右侧的较大元素和枢轴左侧的较小元素。

• 但这意味着什么bad pivot？
• 怎么能把bad pivot总运行时间扔进去O(n^2)？

谢谢

Answer 1

如果选择算法在每一步都可以丢弃大量的数组，它将很快。一个好的枢轴是对于“很多”的某些定义导致算法丢弃“很多”数组元素的枢轴。错误的枢轴是算法丢弃数组标题的枢轴。

在最坏的情况下，主元可能是数组的最大或最小元素。如果发生这种情况，那么算法将以一组值为空的方式对元素进行分区，因为要么没有小于枢轴的元素，要么没有大于枢轴的元素。这个划分步骤需要时间 O(n)，并且必须运行 O(n) 次，因为每次迭代都会将数组的大小减一。这将算法运行时间降级为 O(n ² )。有趣的是，这也是快速排序退化到时间 O(n ² ) 的方法。

希望这可以帮助！