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$](img103.gif) |
![$=$](img49.gif) |
![$\mbox{ rechts } - \mbox{ links } +1$](img104.gif) |
|
|
![$\Rightarrow$](img105.gif) |
![$2^{k}$](img106.gif) |
![$=$](img49.gif) |
![$\mbox{ rechts } - \mbox{ links } +2$](img107.gif) |
|
|
![$\Rightarrow$](img105.gif) |
![$2^{k-1}$](img108.gif) |
![$=$](img49.gif) |
![$\frac{\mbox{ rechts }- \mbox{ links}}
{2} +1$](img109.gif) |
|
|
![$\Rightarrow$](img105.gif) |
![$ 2 ^{k - 1} -1 $](img102.gif) |
![$=$](img49.gif) |
![$\frac{\mbox{ rechts } - \mbox{ links}}
{2}= \frac{\mbox{ rechts } +\mbox{ rechts } - \mbox{ links } - \mbox{ rechts}}{2}$](img110.gif) |
|
|
|
|
![$=$](img49.gif) |
![$\mbox{ rechts }-(\frac{\mbox{ links } + \mbox{ rechts }}
{2} +~1) + 1$](img111.gif) |
|
|
|
|
![$=$](img49.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$](img113.gif) |
![$ 2^{4}-1$](img114.gif) |
![$ 2^{3}-1$](img115.gif) |
![$2^{2}-1$](img116.gif) |
![$2^{1}-1$](img117.gif) |
|
![$=31$](img118.gif) |
![$=15$](img119.gif) |
![$=7$](img120.gif) |
![$=3$](img121.gif) |
![$=1$](img122.gif) |
Anders formuliert:
Zahlen verursachen höchstens
Schleifendurchläufe.
@
Previous: Analyse der Laufzeit der linearen Suche
Up: Lineare und binäre Suche
Next: Klassenmethoden