algorithm - 随机二分查找的期望运行时间

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, n] 上 1/x 的积​​分，它是 log(n) - log(1) = log (n)。参见 Harmonic series .