algorithm - 如果我们以一定的概率选择主元，那么快速排序的运行时间是多少

Question

如果我们需要随机选择主元 x 进行快速排序，概率为 0.5，则 x 是中位数；概率为 0.5，x 是最小值。我理解选择最小值时的运行时间是 O(n^2)，选择中值时的运行时间是 O(n logn)。如果我们将它们组合在一起，总运行时间是否仍然是 O(n logn)？

Answer 1

在 Corman 等人中有一个关于好的 split 和坏 split 的很好的计算。阿尔。当好的拆分后接坏的拆分时，运行时间将为 O(nlogn)。

甚至，当拆分一直发生 10/100 时，运行时间将为 O(nlogn)。

如果您的问题是；有 1/2 的概率有一个好的拆分，有 1/2 的概率有一个坏的拆分，答案将是预期的运行时间是 O(nlogn)。因为总是有运气很差的情况，我们会分得不好。