ランダム化バイナリ検索の実行時間

Question

次のバイナリ検索の無作為ランダム化バリアントを考えてみましょう。あなたは並べ替えられた配列を与えられます n個の整数のAとあなたが探している整数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）を提供します

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