如果您将随机快速排序算法更改为重复随机选择一个主元并运行分区,直到找到“好的”主元,那么该算法最坏情况的成本是多少?如果我们跟踪到目前为止使用的枢轴,这样我们就不会为同一个数组使用相同的枢轴两次。
在最坏的情况下,随机主元始终是最大或最小可能值,在这种情况下,运行时间为 O(n^2)。 如需更详细的分析,请查看此处。 不过,运行时间的预期值仍然是 O(n * log n)。
以上答案都不正确。这个问题简化为拉斯维加斯算法,它没有最坏情况的上限。
考虑这个算法:
repeat:
k = RandInt(n)
if isGoodPivot(A[k]),
return k;
假设
isGoodPivot
对于 A 中 80% 的元素返回 True
,对于 A 中 20% 的元素返回 False
。在最坏的情况下,该算法永远不会终止,因为您可能总是选择 A 中 20% 的元素。其中 isGoodPivot
返回 False
的元素。如果算法永远不会终止,则时间复杂度是不确定的。