algorithm - 选择算法中的 good pivot VS "bad pivot"有什么区别？

Question

我正在尝试理解 Select algorithm我遇到了 a good pivot VS a bad pivot 。我可以看到该算法正在使用 Partition 算法来分隔右侧的较大元素pivot 和 pivot 左侧的较小元素。

• 但是坏的枢轴是什么意思？
• 错误的数据透视 怎么可能将总运行时间投入到 O(n^2) 中？

谢谢

Answer 1

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

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

希望这对您有所帮助!