prev up next


Previous: Analyse der Laufzeit der Up: Lineare und binäre Suche Next: Klassenmethoden

Analyse der Laufzeit der binären Suche

Beh.:
In einem Schleifendurchlauf schrumpft ein Intervall der Länge 2k - 1 auf ein Intervall der Länge 2k - 1 - 1 .
Beweis:

Sei Länge vom alten Intervall =

  2k - 1 = $\mbox{ rechts }$ - $\mbox{ links }$ + 1    
$\Rightarrow$ 2k = $\mbox{ rechts }$ - $\mbox{ links }$ + 2    
$\Rightarrow$ 2k - 1 = ${\frac{\mbox{ rechts }- \mbox{ links}}{2}}$ + 1    
$\Rightarrow$ 2k - 1 - 1 = ${\frac{\mbox{ rechts }- \mbox{ links}}{2}}$ = ${\frac{\mbox{ rechts } +\mbox{ rechts } - \mbox{ links } - \mbox{ rechts}}{2}}$    
    = $\mbox{ rechts }$ - (${\frac{\mbox{ links } + \mbox{ rechts }}{2}}$ +  1) + 1    
    = neue Intervallänge im THEN-Zweig    
Korollar:
2k - 1 Zahlen verursachen höchstens k Schleifendurchläufe, da nach k Halbierungen die Intervallänge 1 beträgt.

Beispiel für eine Folge von 31 sortierten Zahlen:

Schleifendurchlauf 1 2 3 4 5
aktuelle Intervallänge 25 - 1 24 - 1 23 - 1 22 - 1 21 - 1
  = 31 = 15 = 7 = 3 = 1

Anders formuliert:
n Zahlen verursachen höchstens $\log_{2}^{}$n Schleifendurchläufe.


prev up next
Previous: Analyse der Laufzeit der Up: Lineare und binäre Suche Next: Klassenmethoden