Laufzeit der randomisierten binären Suche

Question

Betrachten Sie die folgende alberne randomisierte Variante der binären Suche. Sie erhalten ein sortiertes Array A von n ganzen Zahlen und die Ganzzahl v, nach der Sie suchen, wird einheitlich zufällig aus A ausgewählt. Dann, anstatt v mit dem Wert in der Mitte des Arrays zu vergleichen, die randomisierte binäre Suche Variante wählt eine Zufallszahl r von 1 bis n und vergleicht v mit A [r]. Abhängig davon, ob v größer oder kleiner ist, wird dieser Prozess rekursiv auf dem linken Sub-Array oder dem rechten Sub-Array wiederholt, bis die Position von v gefunden wird. Beweisen Sie eine enge Grenze für die erwartete Laufzeit dieses Algorithmus.

Hier ist, was ich für die T bekam (n)

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

Allerdings habe ich keine Ahnung, wie eine enge gebunden zu bekommen.

Answer 1

Ihre Formulierung von T (n) ist nicht vollständig korrekt. Eigentlich

Lets versuchen, über alle Fälle zu sehen. Wenn wir die Problemgröße reduzieren, indem wir das Array über einen zufälligen Punkt partitionieren, wird das reduzierte Subproblem eine beliebige Größe von 1 bis n mit einer gleichmäßigen Wahrscheinlichkeit haben. Daher wird der Suchraum mit der Wahrscheinlichkeit 1/n zu r. So erwartete Laufzeit wird

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

Welche,

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

Let erwartete Zeitkomplexität von zufälligen binären Art sein T (n) gibt.

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 ] 

so, T(n) = O(log n)

Harmonic number

bound of H(n)