Bester, ungünstigster, durchschnittlicher Fall
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\):
| Fall | lineare Suche | binäre Suche |
|---|---|---|
| bester | 1 (x an Index 0) | 1 (x in der ersten Mitte) |
| ungünstigster | \(n\) (x hinten oder fehlt) | \(\lfloor\log_2 n\rfloor + 1\) |
| durchschnittlich* | \(\frac{n+1}{2}\) | knapp 1 weniger als im ungünstigsten Fall |
- * Durchschnitt:gemittelt über alle Positionen, wenn
xvorkommt 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.
Steht x an Index \(i\), kostet das \(i + 1\) Vergleiche — also 1, 2, …, \(n\) für die \(n\) möglichen Positionen.
Summe der Zahlen 1 bis \(n\) (kleiner Gauß): \(\frac{n(n+1)}{2}\).
Durch \(n\) teilen. Beispiel \(n = 9\): im Mittel 5 Vergleiche — der Treffer liegt im Schnitt in der Mitte.
Drei Fälle: Der Aufwand hängt davon ab, wo \(x\) steht; man zählt Vergleiche bei Länge \(n\).
Linear: bester Fall 1, ungünstigster Fall \(n\) (x hinten oder fehlt), durchschnittlich \(\frac{n+1}{2}\).
Binär: bester Fall 1, ungünstigster Fall \(\lfloor\log_2 n\rfloor + 1\), durchschnittlich knapp 1 weniger.
Maßstab: Meist zählt der ungünstigste Fall, denn er gilt für jede Eingabe. Die binäre Suche braucht eine sortierte Reihung.
Wachstum und Entscheidung
Ungünstigster Fall für wachsende Datenmengen:
| \(n\) | linear | binär |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
- 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 (
ibzw.links,rechts,mitte) — unabhängig von \(n\).
Wachstum: Verdoppelt sich \(n\), verdoppeln sich die Vergleiche der linearen Suche; bei der binären kommt nur ein Vergleich hinzu.
Sortieren: Einfache Sortierverfahren brauchen etwa \(\frac{n^2}{2}\) Vergleiche, also soviel wie etwa \(\frac{n}{2}\) lineare Suchen.
Entscheidung: Einmal suchen: linear. Schon sortiert oder oft suchen in großen Daten: binär, nötigenfalls nach einmaligem Sortieren.
Allgemeine Hinweise
Durchschnitt nicht verwechseln
Die \(\frac{n+1}{2}\) Vergleiche gelten nur, wenn x vorkommt. Fehlt x, braucht die lineare Suche immer alle \(n\) Vergleiche.
Verdopplung als Test
Um ein Verfahren einzuschätzen, frage: Was passiert bei doppelter Datenmenge? Doppelt so viel (linear), ein Schritt mehr (logarithmisch) oder viermal so viel (quadratisch)?
Sortieren ist nicht gratis
Wer für eine einzige Suche erst sortiert, hat mehr Arbeit als mit der linearen Suche. Das lohnt sich nur, wenn danach oft gesucht wird und sich die Daten kaum ändern.