algorithm - 更改随机选择算法对运行时的影响

Question

如果我们将代码中的第 8 行从 q-1 更改为 CLRS 书籍第 216 页中的 q，随机选择算法的运行时间会怎样？

我发现算法应该仍然有效并且运行时间不应该有任何变化，因为它只依赖于 RANDOMIZED PARTITION 子例程。是真的吗？

Randomized-Select (A,p,r,i)
// Finds the ith smallest value in A[p .. r].
if (p = r)
    return A[p]
q = Randomized-Partition(A,p,r)
k = q-p+1   // k = size of low side + 1 (pivot)
if (i = k)
    return A[q]
else if (i<k)
    return Randomized-Select(A,p,q-1,i)
else
    return Randomized-Select(A,q+1,r,i-k)

Answer 1

第 I 个统计信息可能在:
左边部分 - 范围 p ..q-1
右侧 - 范围 q+1..r
恰好在索引 q

最后一种情况发生在条件满足时:

if (i = k)
   return A[q] 

否则我们知道第 q 个元素永远不会是第 i 个统计量，因此在以后的迭代(递归级别)中一次又一次地对待它是不明智的。

提议的修改不会改变复杂性，但实际运行时间可能会增加一点

(平均情况 n + n/2 + n/4 + ... + 1=2n vs n + (n/2+1) + (n/4+1 ) + ... + 1=2n+log(n))