文章/答案/技术大牛

发布

社区首页 >问答首页 >随机快速排序，其中在分区后再次选择枢轴。

问随机快速排序，其中在分区后再次选择枢轴。
EN

Stack Overflow用户

提问于 2020-04-10 16:21:40

回答 2查看 356关注 0票数 1

我想就这个问题再提一次：

考虑随机快速排序算法的一种变化，其中选择支点是随机的，直到数组被分割时，较低的子阵L和较大的子阵G都包含3/4的数组元素。例如，如果随机选择的枢轴以L包含1/10元素的方式划分数组，则随机选择另一个pivot。分析了该算法的预期运行时间。

一开始，我把这个问题当作只是一个常规的快速排序问题，并提出了一个重复的问题：

T(n) = T(3/4n) + T(n/4) + Θ(n) (where Θ(n) comes from the partition)

如果我们有一个算法，它的分割总是1/4 : 3/4，那么这是有意义的。但是，我们在这里使用随机枢轴，并且每次不满足分区条件时，支点都会改变。我知道随机快速排序最坏的运行时间仍然是O(n^2)，但我认为在这种情况下，最坏的情况现在是不同的(比O(n^2)更糟糕)。到目前为止我走的路对吗？

发布于 2020-04-10 23:26:56

n/2有坏的支点。假设您从未两次选择相同的枢轴(如果选择了，最坏的情况总是选择一个糟糕的枢轴，即无限时间)，在最坏的情况下，您会重复分区n/2时间，这会导致分区阶段的Θ(n^2)复杂性。复发率

T(n) = T(n/4) + T(3n/4) + Θ(n^2)

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/61144386

复制

相似问题

问随机快速排序，其中在分区后再次选择枢轴。EN