預期隨機二進制搜索

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)) 

通過觀察事實，你可以選擇任何點分隔陣列，你需要總結的所有possiblities乘以它們的概率，從而獲得預期的時間獲得這條線。請參閱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。