Algorithmen und Datenstrukturen 2

Übungsblatt 4: Suchverfahren

Aufgabe 4-1 *

Das Prinzip der binären Suche besteht darin, die Mitte des Suchraums zu betrachten und anschließend den Suchraum für die weitere Suche auf eine der beiden Hälften einzuschränken. Die Mitte des Suchraums ergibt sich aus folgender Formel:
m = (r + l) / 2 = l + (r − l) · ½

Anstatt ungezielt die Mitte zu nehmen, kann man auch schätzen, an welcher Position sich der gesuchte Schlüssel wahrscheinlich befindet. Anstelle der Mitte wird dann diese geschätzte Position betrachtet. Die folgende Formel ersetzt den Faktor ½ durch eine lineare Interpolation.
m = l + (r − l) · (k − A_l) / (A_r − A_l)

1. Implementieren Sie die Interpolationssuche in einer Methode findeInterpoliert analog zu Aufgabe 3-1.
2. Nennen Sie die Vorbedingungen der Interpolationssuche.

Aufgabe 4-2 *

Geben Sie die Zeitkomplexität der bisher behandelten Suchalgorithmen in der Groß-O-Notation an. Nennen Sie jeweils die Komplexität für den best case, den average case und den worst case.

1. sequentielle Suche (iterativ)
2. sequentielle Suche (rekursiv)
3. binäre Suche (rekursiv)
4. Interpolationssuche (rekursiv)

Aufgabe 4-3

Wandeln Sie die Rekursion im Algorithmus der binären Suche in eine Iteration um.

1. Formulieren Sie den iterativen Algorithmus der binären Suche. Verwenden Sie wahlweise „natürliche Sprache“ nach Dr. Bürg, eine Java-Implementierung oder eine andere geeignete Art und Weise.
2. Geben Sie die Zeitkomplexität Ihrer Lösung aus Teilaufgabe (a) im average case an.
3. Messen Sie den tatsächlich benötigten Zeitaufwand. Begründen Sie den Unterschied zu Ihrem Ergebnis aus Teilaufgabe (b).

Zusatzaufgabe 4-4

1. Erweitern Sie die Klasse Menge aus Übungsblatt 3 mit einer Objektmethode void bogoSort (), die den internen Array aufsteigend sortiert. Verwenden Sie den nachfolgend angegebenen Algorithmus.
2. Begründen Sie, weshalb die Implementierung in Java iterativ erfolgen muss.

$Id: HEADER.html 2009-05-11 $