有人能告诉我随机选择算法是如何给出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)。