Zum Menü springen.

Übungsblatt 8: Fortgeschrittene Suchverfahren

Aufgabe 8-1*

Das Prinzip der binären Suche besteht darin, die Mitte des (sortierten) 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 = l + (r − l) · ½ = (r + l) / 2

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 − Al) / (Ar − Al)

Implementieren Sie das Verfahren der Interpolationssuche in einer Methode analog zu Aufgabe 7-2.

Aufgabe 8-2

Die folgenden Teilaufgaben beziehen sich allgemein auf die in der Vorlesung behandelten Verfahren zum Suchen und Finden von Daten; es können beliebige Bedingungen an die Speicherung der Daten gestellt werden (etwa, dass sie sortiert sein müssen). Begründen Sie jeweils Ihre Antwort, z. B. durch Nennung des Namens eines geeigneten Verfahrens.

  1. Gibt es ein Suchverfahren, das regelmäßig (also im average case) mit konstantem Zeitaufwand O(1) zum Ergebnis führt?
  2. Gibt es ein Suchverfahren, das im average case einen höheren als linearen Zeitaufwand O(n) hat?
  3. Gibt es ein Suchverfahren, das im worst case einen geringeren als linearen Zeitaufwand O(n) hat?
  4. Welche(s) Verfahren sollten Sie selbst bevorzugt einsetzen? Weshalb?

Zusatzaufgabe 8-3*

Beim Schritt von der binären Suche in Aufgabe 7-2 zur Interpolationssuche in 8-1 wurde die Effizienz der Suche verbessert, indem die Anzahl der nötigen Vergleiche deutlich minimiert wurde bei gleichzeitiger Inkaufnahme eines leicht erhöhten Rechenaufwands.

Die Fibonacci-Suche verfolgt einen anderen Ansatz zur (theoretischen) Verbesserung der Effizienz der binären Suche: Sie benötigt in etwa gleich viele Vergleiche, hat dabei aber (theoretisch) einen noch geringeren Rechenaufwand als die binäre Suche.

Implementieren Sie das Verfahren der Fibonacci-Suche in einer Methode analog zu Aufgabe 7-2.

$Id: HEADER.html,v 1.6 2007/12/20 17:19:26 arne Exp $