如果我们需要随机选取快速排序的轴x，概率为0.5，x是中值；概率为0.5，x是最小值我知道选择最小值时的运行时间是o（n^2），选择中值时的运行时间是o（n logn）。如果我们把它们结合起来，总运行时间还会是o（n logn）吗？
最佳答案
有一个很好的计算关于一个好的分裂和一个坏的分裂在科曼等人当好的分割接坏的分割时，运行时间为o（nlogn）。
即使当分裂一直发生在10/100时，运行时间也是o（nlogn）。
如果你的问题是：1/2的概率有一个好的分割，1/2的概率有一个坏的分割，答案是预期的运行时间是O（nlogn）因为总有一种情况，如果运气不好的话，我们会分道扬镳。
关于algorithm - 如果我们以一定的概率选择数据透视，那么快速排序的运行时间是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52541224/