Previous: Analyse der Laufzeit der linearen Suche
Up: Lineare und binäre Suche
Next: Klassenmethoden
- Beh.:
- In einem Schleifendurchlauf schrumpft ein Intervall der Länge
auf ein Intervall der Länge
.
Beweis:
Sei Länge vom alten Intervall =
|
![$2^{k}-1$](img105.gif) |
![$=$](img45.gif) |
![$\mbox{ rechts } - \mbox{ links } +1$](img106.gif) |
|
|
![$\Rightarrow$](img107.gif) |
![$2^{k}$](img108.gif) |
![$=$](img45.gif) |
![$\mbox{ rechts } - \mbox{ links } +2$](img109.gif) |
|
|
![$\Rightarrow$](img107.gif) |
![$2^{k-1}$](img110.gif) |
![$=$](img45.gif) |
![$\frac{\mbox{ rechts }- \mbox{ links}}
{2} +1$](img111.gif) |
|
|
![$\Rightarrow$](img107.gif) |
![$ 2 ^{k - 1} -1 $](img104.gif) |
![$=$](img45.gif) |
![$\frac{\mbox{ rechts } - \mbox{ links}}
{2}= \frac{\mbox{ rechts } +\mbox{ rechts } - \mbox{ links } - \mbox{ rechts}}{2}$](img112.gif) |
|
|
|
|
![$=$](img45.gif) |
![$\mbox{ rechts }-(\frac{\mbox{ links } + \mbox{ rechts }}
{2} +~1) + 1$](img113.gif) |
|
|
|
|
![$=$](img45.gif) |
neue Intervalllänge im THEN-Zweig |
|
|
- Korollar:
Zahlen verursachen höchstens
Schleifendurchläufe, da nach
Halbierungen die Intervallänge
beträgt.
Beispiel für eine Folge von 31 sortierten Zahlen:
Schleifendurchlauf |
1 |
2 |
3 |
4 |
5 |
aktuelle Intervalllänge |
![$2^{5}-1$](img114.gif) |
![$ 2^{4}-1$](img115.gif) |
![$ 2^{3}-1$](img116.gif) |
![$2^{2}-1$](img117.gif) |
![$2^{1}-1$](img118.gif) |
|
![$=31$](img119.gif) |
![$=15$](img120.gif) |
![$=7$](img121.gif) |
![$=3$](img122.gif) |
![$=1$](img123.gif) |
Anders formuliert:
Zahlen verursachen
höchstens
Schleifendurchläufe.
Previous: Analyse der Laufzeit der linearen Suche
Up: Lineare und binäre Suche
Next: Klassenmethoden