隨機二進制搜索的運行時間

Question

考慮以下二進制搜索的愚蠢隨機變體。您將得到一個有n個整數的排序數組，並且您正在搜索的整數v是從A中隨機選擇的。 然後，不是將v與數組中間的值進行比較，而是使用隨機二分搜索 變體選擇從1到n的隨機數r，並將v與A [r]進行比較。取決於 v是大於還是小，對左側子陣列或右側子陣列 遞歸地重複該過程，直到找到v的位置。證明該算法的預期運行時間的嚴格界限。

這是我得到的T（n）的

T(n) = T(n-r) + T(r) + Θ(1)

但是，我不知道如何獲得一個緊約束。

Answer 1

你的公式T（n）並不完全正確。其實，

讓我們試着看看所有的情況。當我們通過在任意隨機點上劃分陣列來減小問題的大小時，減少的子問題將具有一致的概率從1到n的任何大小。因此，以概率1/n，搜索空間變爲r。因此，預計運行時間變得

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

其中給出，隨機二進制形式的

T(n) = average(T(r)) + O(1)

讓預期的時間複雜度爲T（N）。

T(n) = [ T(1)+T(2)+...+T(n)]/n + 1 
n*T(n) = T(1)+T(2)+...+T(n) + n 
(n-1)*T(n-1) = T(1)+T(2)+...+T(n-1) + n-1  [substituiting n by n-1] 
n*T(n) - (n-1)*T(n-1) = T(n) + 1 
(n-1)*T(n) - (n-1)*T(n-1) = 1 
(n-1)*T(n) = (n-1)*T(n-1) + 1 
T(n) = 1/(n-1) + T(n-1) 
T(n) = 1/(n-1) + 1/(n-2) + T(n-2)    [ T(n-1) = T(n-2) + 1/(n-2) ] 
... 
T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n) 
[ H(n) = reciprocal sum of first n natural numbers ] 

所以，T(n) = O(log n)

Harmonic number

bound of H(n)