如果您不断随机选择一个主元并进行分区,直到找到一个好的主元,那么随机快速排序的最坏情况运行时间

问题描述 投票:0回答:2

如果您将随机快速排序算法更改为重复随机选择一个主元并运行分区,直到找到“好的”主元,那么该算法最坏情况的成本是多少?如果我们跟踪到目前为止使用的枢轴,这样我们就不会为同一个数组使用相同的枢轴两次。

algorithm time-complexity big-o quicksort
2个回答
1
投票

在最坏的情况下,随机主元始终是最大或最小可能值,在这种情况下,运行时间为 O(n^2)。 如需更详细的分析,请查看此处。 不过,运行时间的预期值仍然是 O(n * log n)。


0
投票

以上答案都不正确。这个问题简化为拉斯维加斯算法,它没有最坏情况的上限。

考虑这个算法:

repeat:
    k = RandInt(n)
    if isGoodPivot(A[k]),
        return k;

假设

isGoodPivot
对于 A 中 80% 的元素返回
True
,对于 A 中 20% 的元素返回
False
。在最坏的情况下,该算法永远不会终止,因为您可能总是选择 A 中 20% 的元素。其中
isGoodPivot
返回
False
的元素。如果算法永远不会终止,则时间复杂度是不确定的。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.