algorithm - 随机化快速排序在时间复杂度方面与随机化选择算法有何不同

Question

使用 randomize_quicksort()，我们知道平均情况复杂度为 O(nlgn)，因为我们在随机过程中选择了主元。然而，当我寻找randomize 选择算法时，我们也随机选择了类似于 randomize_quicksort() 的主元，在最坏的情况下我们最终得到了 O(n^2) 复杂度。我不明白是什么让它以二次方时间运行，尽管我们使用的是选择枢轴元素的相同策略。

谢谢

Answer 1

您的问题已包含答案。您正在谈论快速排序的平均情况和选择算法的最坏情况。这不是一回事。在最坏的情况下，这两种算法都是二次算法。