Suchverfahren vergleichen

Wie aufwendig ein Suchverfahren ist, hängt davon ab, wo x steht. Deshalb vergleicht man drei Fälle, jeweils in Vergleichen für eine Reihung der Länge \(n\):

• * Durchschnitt:gemittelt über alle Positionen, wenn x vorkommt und jede Position gleich wahrscheinlich ist.
• Maßstab:entscheidend ist meist der ungünstigste Fall — er gilt garantiert für jede Eingabe.
• Voraussetzung:die lineare Suche arbeitet auf jeder Reihung, die binäre nur auf einer sortierten.

Ungünstigster Fall für wachsende Datenmengen:

• Linear:verdoppelt sich \(n\), verdoppeln sich die Vergleiche (+ n).
• Logarithmisch:verdoppelt sich \(n\), kommt genau ein Vergleich hinzu.
• Sortieren kostet:einfache Sortierverfahren brauchen etwa \(\frac{n(n-1)}{2}\approx\frac{n^2}{2}\) Vergleiche — so viel wie etwa \(\frac{n}{2}\) lineare Suchen im ungünstigsten Fall.

Stelle mit den Reglern die Datenmenge \(n\) und die Zahl \(k\) der Suchvorgänge ein. Oben siehst du eine einzelne Suche, unten den Gesamtaufwand für \(k\) Suchen — einmal nur linear, einmal erst sortieren und dann binär. Verdopple \(n\) mehrmals und finde heraus, ab welchem \(k\) sich das Sortieren lohnt.

Halte fest: Eine einzelne Suche ist binär fast kostenlos, aber das Sortieren vorab kostet etwa \(\frac{n^2}{2}\) Vergleiche — es lohnt sich erst, wenn man ungefähr \(\frac{n}{2}\) Mal oder öfter sucht.

• Einmal suchen, unsortiert:lineare Suche.
• Schon sortiert:binäre Suche — ab wenigen Dutzend Elementen deutlich schneller.
• Oft suchen, große Daten:einmal sortieren, dann binär; bei kleinen \(n\) ist der Unterschied unerheblich.
• Speicher:beide Verfahren arbeiten in-place auf der Reihung und brauchen nur wenige Hilfsvariablen (i bzw. links, rechts, mitte) — unabhängig von \(n\).