有人能告诉我随机选择算法是如何给出O（n）的平均时间复杂度的吗？我看到如果随机选择的轴心点（在第1个过程中）是列表中的第k个元素，那么它将具有最佳的大小写o（n）。但这怎么可能是一般情况呢我们不能保证每次运行算法时，我们都会在第一个过程中命中正确的一个rt？
最佳答案
在第一次通过之后，你就知道第k个元素的“一半”在哪了现在你在“一半”上重复这个过程。
所以，在第一次迭代的平均情况下，你要执行n个步骤，在第二次迭代中执行n/2个步骤，然后执行n/4个步骤，依此类推作为包络计算的后盾，假设n=2**k。步骤总数为
2**k + 2**k/2 + 2**k/4 + ... = 2**k + 2**(k-1) + 2**(k-2) + ... + 2 + 1
= 2**(k+1) - 1
= 2n - 1
所以，算法是O（2n-1）=O（n）。