随机二分搜索的预期 运行 时间

Question

我想计算以下伪代码的随机二分搜索的预期 运行 时间，其中选择了一个随机点，而不是将中点作为基准点：

BinarySearch(x, A, start, end)
    if(start == end)
        if(A[end] == x) 
            return end
        else
            return -1
    else
        mid = RANDOM(start, end)
        if(A[mid] == x)
            return mid
        else if(A[mid] > x)
            return BinarySearch(x, A, start, mid-1)
        else
            return BinarySearch(x, A, mid+1, end)

我查看了 this previous question，其中包含以下内容：

T(n) = sum ( T(r)*Pr(search space becomes r) ) + O(1) = sum ( T(r) )/n + O(1)

这是怎么得到的？

sum( T(r)*Pr(search space becomes r) ) 

而在最后一行计算中，这个是怎么得到的呢？

T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n)

Answer 1

sum( T(r)*Pr(search space becomes r) ) 

这条线是通过观察你可以选择任何点来划分数组的事实得到的，所以为了得到预期的时间你需要总结所有的可能性乘以它们的概率。参见 expected value。

T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n)

关于这一行。好吧，您可以将其视为 1/x 在 [1, n] 上的积分，它是 log(n) - log(1) = log(n)。参见 Harmonic series。