Zum Inhalt springen
Zurück zur Themenübersicht

Praktische Informatik

Suchalgorithmen: linear, binär und über Streuspeicherung

Wie aus einer Million Vergleichen zwanzig werden und welche Voraussetzung man dafür bezahlen muss.

Benötigte Grundlagen

Dieses Vorwissen brauchst du für das Kapitel. Schau kurz nach, wenn dir etwas davon nicht mehr präsent ist, sonst leg direkt los.

Einführung

Suchen ist die häufigste Tätigkeit eines Programms. Jede Datenbankabfrage, jede Autovervollständigung, jeder Wörterbuchzugriff läuft darauf hinaus.

Bei einer Million Einträgen braucht das eine Verfahren im schlechtesten Fall eine Million Vergleiche, das zweite zwanzig und das dritte einen einzigen.

Der Unterschied ist gewaltig, aber nichts davon ist umsonst. Jedes schnellere Verfahren verlangt eine Voraussetzung, und der eigentliche Inhalt dieses Kapitels ist die Frage, welche das jeweils ist und was sie kostet.

Das kannst du nach diesem Kapitel

  • die lineare Suche beschreiben und ihren Aufwand angeben.

  • die binäre Suche durchführen und ihre Voraussetzung benennen.

  • begründen, warum die binäre Suche O(log⁡n)O(\log n) Schritte braucht.

  • abschätzen, ab wann sich vorheriges Sortieren lohnt.

  • das Prinzip der Streuspeicherung (Hashing) erläutern (Vertiefung).

Kurz aufgefrischt

Vorausgesetzt werden und aus Algorithmen entwerfen, die aus Aufwand von Algorithmen und das Feld aus Datentypen und Datenstrukturen.

Die lineare Suche

Der einfachste Weg: von vorn durchgehen und vergleichen.

Eingabe: Feld a mit n Elementen, gesuchter Wert x

für i von 0 bis n-1:
    wenn a[i] = x:
        gib i zurück
gib "nicht gefunden" zurück
FallVergleicheAufwand
bester1 (steht vorn)O(1)O(1)
mittlerern/2n/2O(n)O(n)
schlechtesternn (hinten oder nicht da)O(n)O(n)

Beachte, dass der mittlere Fall n/2n/2 Vergleiche braucht und trotzdem in O(n)O(n) liegt: Der Faktor 12\tfrac{1}{2} ist konstant und fällt weg.

Ihre große Stärke ist die fehlende Voraussetzung. Sie funktioniert auf unsortierten , auf Feldern wie auf , und sie braucht keinerlei Vorbereitung. Für kleine Datenmengen oder für eine einmalige Suche ist sie die richtige Wahl.

Lineare Suche: der schlechteste Fall

7[0]3[1]9[2]1[3]5[4]12[5]4[6]

Das Feld ist unsortiert, und daraus folgt alles Weitere. Weil kein Wert etwas über seine Nachbarn verrät, bleibt nur: von vorn durchgehen und jeden vergleichen. Gesucht ist hier die 4. Sie steht ganz hinten, also werden alle sieben Zellen angesehen. Das ist der schlechteste Fall, und er tritt genauso ein, wenn der Wert gar nicht enthalten ist: Auch dann muss man bis zum Ende gehen, um das sagen zu können. Bei nn Elementen sind das nn Vergleiche, im Mittel n/2n/2. Beides ist O(n)O(n), denn der Faktor 12\tfrac{1}{2} ist konstant und fällt weg. 🔴 Und trotzdem ist das kein schlechtes Verfahren: Es setzt nichts voraus, keine Sortierung und keine Vorbereitung.

Die binäre Suche

Denk an ein Wörterbuch. Niemand fängt auf Seite 1 an. Man schlägt in der Mitte auf, schaut, ob das gesuchte Wort davor oder dahinter liegt, und halbiert so den Suchbereich.

Genau das ist die binäre Suche:

Eingabe: SORTIERTES Feld a, gesuchter Wert x

links = 0
rechts = n-1

solange links ≤ rechts:
    mitte = (links + rechts) ganzzahlig geteilt durch 2
    wenn a[mitte] = x:
        gib mitte zurück
    wenn a[mitte] < x:
        links = mitte + 1        // rechte Hälfte weitersuchen
    sonst:
        rechts = mitte - 1       // linke Hälfte weitersuchen
gib "nicht gefunden" zurück

🔴 Die Voraussetzung ist die Sortierung, und sie ist nicht verhandelbar. Nur weil die sortiert sind, sagt ein einziger Vergleich, in welcher Hälfte der gesuchte Wert liegen kann. Auf unsortierten Daten liefert dieses Verfahren keine langsame Antwort, sondern eine falsche: Es meldet „nicht gefunden", obwohl der Wert vorhanden ist.

Warum O(log⁡n)O(\log n)? Nach jedem Schritt ist höchstens die Hälfte übrig. Nach kk Schritten also n/2kn/2^k Elemente, und man ist fertig, wenn eines übrig ist:

n2k=1⟺2k=n⟺k=log⁡2n\frac{n}{2^k} = 1 \quad \Longleftrightarrow \quad 2^k = n \quad \Longleftrightarrow \quad k = \log_2 n

Die Zahlen dazu sind eindrucksvoll:

nnlineare Suchebinäre Suche
1001007
10 00010 00014
1 000 0001 000 00020
1 000 000 00010910^930

Von einer Million auf eine Milliarde: Die lineare Suche wird tausendmal teurer, die binäre braucht zehn Schritte mehr. Das ist der Charakter des Logarithmus.

Binäre Suche: ein Vergleich, eine Hälfte

noch möglich: alle 71[0]3[1]4[2]5[3]7[4]9[5]12[6]

Dieselben sieben Zahlen, jetzt sortiert, und damit wird ein einziger Vergleich unverhältnismäßig wertvoll. Angesehen wird die Mitte, hier a[3]=5a[3] = 5. Ist der gesuchte Wert kleiner, kann er nur links davon liegen; ist er größer, nur rechts. In beiden Fällen fallen mit einem Vergleich drei der sieben Zellen weg. Genau das ist der Unterschied zum Bild darüber: Dort sagt ein Vergleich nur etwas über eine Zelle, hier über die halbe Menge. 🔴 Die Sortierung ist deshalb keine Bequemlichkeit, sondern die Voraussetzung, ohne die der Schluss „dann liegt er links“ gar nicht zulässig wäre. Auf unsortierten liefert das Verfahren keine langsame Antwort, sondern eine falsche.

Die Suche nach der 12, Schritt für Schritt

SchrittBereichMittea[Mitte]Vergleichmit 1210–63512 > 5,rechts24–65912 > 9,rechts36–6612gefundenSieben Werte, drei Schritte. Bei1000 Werten wären es 10, bei einerMillion 20.

Hier läuft das Verfahren aus dem Bild darüber wirklich ab, und die Spalte „Bereich“ ist die interessante: 7 Werte, dann 3, dann 1. Jeder Schritt halbiert. Daraus folgt der Aufwand, und zwar ohne Handwedeln: Nach kk Schritten sind noch n/2kn/2^k Werte übrig, fertig ist man bei einem, also 2k=n2^k = n und k=log⁡2nk = \log_2 n. Rechne die Fußzeile nach, denn erst dort wird der Logarithmus greifbar: Von tausend auf eine Million wächst die Datenmenge um das Tausendfache, die Zahl der Schritte um zehn.

Was die Sortierung kostet

Die naheliegende Frage: Wenn die binäre Suche so viel besser ist, warum sortiert man nicht immer vorher?

Weil Sortieren O(nlog⁡n)O(n \log n) kostet, also mehr als eine einzige lineare Suche mit O(n)O(n).

Die Rechnung entscheidet nach der Anzahl der Suchvorgänge. Bei mm Suchen in nn :

VorgehenAufwand
mm-mal linear suchenO(m⋅n)O(m \cdot n)
einmal sortieren, dann mm-mal binärO(nlog⁡n+mlog⁡n)O(n \log n + m \log n)

Für m=1m = 1 gewinnt die lineare Suche deutlich. Für großes mm gewinnt die Vorsortierung, denn dort steht m⋅nm \cdot n gegen mlog⁡nm \log n.

🔴 Daraus folgt die Faustregel: Einmal suchen heißt linear suchen. Oft suchen heißt einmal sortieren. Genau deshalb legen Datenbanken einen Index an: Er ist eine sortierte Struktur, die einmal aufgebaut und danach millionenfach benutzt wird.

Zwei Nebenbedingungen gehören dazu. Ändern sich die Daten laufend, muss die Sortierung mitgepflegt werden, und das kostet erneut. Und sortieren lässt sich nur, wo eine Ordnung besteht; auf Daten ohne sinnvolle Vergleichsordnung ist der Weg versperrt.

Vertiefung: Streuspeicherung

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Zwanzig Schritte sind gut. Geht auch einer?

Die Idee der Streuspeicherung (Hashing) ist verblüffend einfach: Man berechnet aus dem Wert selbst, wo er stehen soll.

Eine Streuwertfunktion hh bildet jeden Schlüssel auf einen Index ab:

h(Schlu¨ssel)→Indexh(\text{Schlüssel}) \to \text{Index}

Ein sehr einfaches Beispiel für Namen in einem Feld der Größe 26: hh liefert die Position des Anfangsbuchstabens.

Speichern: h(x)h(x) berechnen und xx dort ablegen. Suchen: h(x)h(x) berechnen und dort nachsehen.

Beides braucht eine Berechnung, also O(1)O(1), unabhängig von der Datenmenge.

Das Problem sind Zusammenstöße. Zwei verschiedene Schlüssel können denselben Index liefern; „Anna" und „Anton" beginnen beide mit A. Man nennt das eine Kollision, und sie ist unvermeidlich: Es gibt mehr mögliche Schlüssel als Plätze, also müssen sich welche einen Platz teilen. Das ist wieder das Schubfachprinzip.

Zwei übliche Auswege:

  • Verkettung: An jedem Index hängt eine aller Werte, die dorthin fallen.
  • Sondieren: Bei Belegung wird der nächste freie Platz genommen.

Damit gilt O(1)O(1) nur im mittleren Fall. Landen alle Schlüssel auf demselben Index, entsteht eine einzige lange Liste, und die Suche fällt auf O(n)O(n) zurück. Entscheidend ist deshalb eine Streuwertfunktion, die gleichmäßig verteilt; der Anfangsbuchstabe wäre in der Praxis ungeeignet, weil manche Buchstaben viel häufiger vorkommen als andere.

Der Preis gegenüber der binären Suche: Eine Streuspeicherung kennt keine Ordnung. Fragen wie „alle Namen zwischen F und K" oder „der nächstgrößere Wert" lassen sich nicht beantworten, denn benachbarte Schlüssel landen an völlig unzusammenhängenden Stellen. Wer sortierte Ausgabe oder Bereichsabfragen braucht, ist mit einer sortierten Struktur besser bedient.

Streuspeicherung mit Verkettung

h(x) = Anfangsbuchstabe imAlphabet, mod 5Anna→ 0Ben→ 1Cem→ 2Anton→ 00Anna → Anton1Ben2Cem3leer4leerAnna und Anton kollidieren: A istA, egal was danach kommt.

Die Regel oben ist die ganze Idee: Der Platz wird aus dem Schlüssel gerechnet, nicht gesucht. „Cem“ landet auf Platz 2, weil C der dritte Buchstabe ist, und beim Nachschlagen rechnet man dieselbe Zahl noch einmal aus und sieht direkt dort nach. Eine Rechnung, unabhängig davon, ob zehn oder zehn Millionen Schlüssel gespeichert sind: O(1)O(1). 🔴 Und im selben Bild steht der Haken. „Anna“ und „Anton“ ergeben beide 0, also teilen sie sich einen Platz; das ist eine Kollision, und sie ist unvermeidlich, weil es mehr mögliche Schlüssel als Plätze gibt, dasselbe Schubfachprinzip wie bei den nichtregulären Sprachen. Hier hängen die beiden als Kette aneinander, und wer sie sucht, muss die Kette durchgehen. Landen alle Schlüssel auf demselben Platz, ist aus O(1)O(1) wieder O(n)O(n) geworden. Deshalb zählt eine Streuwertfunktion, die gleichmäßig verteilt, der Anfangsbuchstabe tut das gerade nicht. Die beiden leeren Plätze sind übrigens kein Versehen, sondern der Preis: Eine Tabelle ohne Luft kollidiert ständig.

Die drei im Vergleich

VerfahrenAufwandVoraussetzungOrdnung nutzbar
linearO(n)O(n)keine–
binärO(log⁡n)O(\log n)sortiertja
StreuspeicherungO(1)O(1) im Mittelgute Streuwertfunktionnein

Das ist der eigentliche Ertrag des Kapitels: Geschwindigkeit wird mit Voraussetzungen bezahlt. Es gibt kein Verfahren, das schneller ist und nichts verlangt.

Binäre Suche Schritt für Schritt

Suche die 23 im sortierten Feld [2,5,8,12,16,23,38,56,72,91][2, 5, 8, 12, 16, 23, 38, 56, 72, 91] mit den Indizes 0 bis 9.

  1. 1

    Start: links=0\texttt{links} = 0, rechts=9\texttt{rechts} = 9.

  2. 2

    Schritt 1: mitte=(0+9):2=4\texttt{mitte} = (0+9) : 2 = 4 (ganzzahlig). Dort steht 16. Es gilt 16<2316 < 23, also liegt 23 rechts davon: links=5\texttt{links} = 5.

  3. 3

    Noch im Spiel sind die Indizes 5 bis 9, also fünf statt zehn Elemente.

  4. 4

    Schritt 2: mitte=(5+9):2=7\texttt{mitte} = (5+9) : 2 = 7. Dort steht 56. Es gilt 56>2356 > 23, also links weitersuchen: rechts=6\texttt{rechts} = 6.

  5. 5

    Schritt 3: mitte=(5+6):2=5\texttt{mitte} = (5+6) : 2 = 5. Dort steht 23. Gefunden an Index 5.

  6. 6

    Bilanz: drei Vergleiche statt sechs bei der linearen Suche. Bei zehn Elementen ist der Unterschied klein. Die Rechnung log⁡210≈3,3\log_2 10 \approx 3{,}3 passt dazu, und bei einer Million wären es 20 statt einer Million.

  7. 7

    Gegenprobe mit einem nicht vorhandenen Wert, etwa 40: Der Bereich schrumpft, bis links>rechts\texttt{links} > \texttt{rechts} wird. Die Schleifenbedingung ist dann verletzt, und das Verfahren meldet zu Recht „nicht gefunden". Genau dieser Abbruch ist der Grund für die Bedingung links≤rechts\texttt{links} \le \texttt{rechts}.

23 steht an Index 5, gefunden in drei Schritten. Der Suchbereich schrumpfte von 10 über 5 auf 2 Elemente.

Lohnt sich das Sortieren?

Ein Feld hat n=1 000 000n = 1\,000\,000 Einträge. Fall A: Es wird einmal gesucht. Fall B: Es wird 10 000-mal gesucht. Was ist jeweils günstiger?

  1. 1

    Die drei Größen aufschreiben:

    Lineare Suche: n=106n = 10^6 Schritte je Suche. Sortieren: nlog⁡2n≈106⋅20=2⋅107n \log_2 n \approx 10^6 \cdot 20 = 2 \cdot 10^7 Schritte, einmalig. Binäre Suche: log⁡2n≈20\log_2 n \approx 20 Schritte je Suche.

  2. 2

    Fall A, eine Suche. Linear: 10610^6. Sortieren und binär: 2⋅107+20≈2⋅1072 \cdot 10^7 + 20 \approx 2 \cdot 10^7.

  3. 3

    Die Vorsortierung ist hier etwa zwanzigmal teurer. Für eine einzige Suche lohnt sie sich eindeutig nicht.

  4. 4

    Fall B, 10 000 Suchen. Linear: 104⋅106=101010^4 \cdot 10^6 = 10^{10}. Sortieren und binär: 2⋅107+104⋅20=2⋅107+2⋅105≈2⋅1072 \cdot 10^7 + 10^4 \cdot 20 = 2 \cdot 10^7 + 2 \cdot 10^5 \approx 2 \cdot 10^7.

  5. 5

    Jetzt ist die Vorsortierung etwa 500-mal billiger. Bemerkenswert: Die 10 000 Suchen kosten zusammen nur ein Hundertstel des Sortierens; nach dem Sortieren fällt der Suchaufwand praktisch nicht mehr ins Gewicht.

  6. 6

    Die Grenze bestimmen: Gleichsetzen von m⋅nm \cdot n und nlog⁡n+mlog⁡nn \log n + m \log n ergibt hier etwa m≈20m \approx 20. Ab ungefähr zwanzig Suchvorgängen lohnt das Sortieren also bereits. Genau deshalb legen Datenbanken einen Index an, sobald eine Spalte regelmäßig durchsucht wird.

Fall A: linear suchen, die Vorsortierung wäre zwanzigmal teurer. Fall B: sortieren, das ist etwa 500-mal billiger. Die Grenze liegt bei rund 20 Suchvorgängen.

Typischer Fehler

„Die binäre Suche ist immer besser, also nimmt man sie überall."

Sie ist nur unter einer Bedingung besser, und ohne diese Bedingung ist sie nicht langsamer, sondern falsch.

Nimm das unsortierte Feld [38,5,91,2,56][38, 5, 91, 2, 56] und suche die 5. Die binäre Suche prüft die Mitte, findet dort 91, folgert 91>591 > 5 und sucht nur noch links. Die 5 steht an Index 1, liegt also tatsächlich links, aber im nächsten Schritt trifft sie auf 38, folgert wieder „links" und landet bei 38 allein. Das Verfahren meldet „nicht gefunden", obwohl die 5 im Feld steht.

Das ist der gefährlichste Fehlertyp überhaupt: Das Programm stürzt nicht ab und meldet keinen Fehler, sondern liefert ein plausibel aussehendes falsches Ergebnis.

Zwei weitere Fälle, in denen die lineare Suche vorzuziehen ist:

Kleine Datenmengen. Bei zehn Elementen sind es 10 gegen 3 Vergleiche; der Unterschied ist bedeutungslos, und die lineare Suche ist kürzer und weniger fehleranfällig zu schreiben.

Einmalige Suche in unsortierten . Das Sortieren kostet O(nlog⁡n)O(n \log n) und damit mehr als die eine lineare Suche mit O(n)O(n).

Die richtige Frage lautet also nicht „welches Verfahren ist schneller?", sondern „sind die Daten sortiert, und wie oft wird gesucht?".

Übung 1

leicht

a) Wie viele Vergleiche braucht die lineare Suche im schlechtesten Fall bei n=500n = 500? b) Wie viele braucht die binäre Suche bei n=1024n = 1024? c) Welche Voraussetzung hat die binäre Suche?

Tipp anzeigen

Zu b): Wie oft lässt sich 1024 halbieren?

Lösung anzeigen

a) 500 Vergleiche. Der schlechteste Fall ist erreicht, wenn der Wert ganz hinten steht oder gar nicht vorhanden ist.

b) log⁡21024=10\log_2 1024 = 10, denn 210=10242^{10} = 1024. Zehn Halbierungen führen von 1024 auf ein Element.

c) Die müssen sortiert sein. Nur dann sagt der Vergleich mit dem mittleren Element, in welcher Hälfte der gesuchte Wert liegen kann. Auf unsortierten Daten liefert das Verfahren falsche Ergebnisse, keine langsamen.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Der schlechteste Fall der linearen Suche

    500 Vergleiche. Der schlechteste Fall ist erreicht, wenn der Wert ganz hinten steht oder gar nicht vorhanden ist, in beiden Fällen muss jedes Element angesehen werden.

    Zwischenergebnis

    500 Vergleiche.

  2. 2

    b) Die binäre Suche bei 1024: wie oft lässt sich halbieren?

    log⁡21024=10\log_2 1024 = 10, denn 210=10242^{10} = 1024. Zehn Halbierungen führen von 1024 auf ein Element: 1024→512→256→128→64→32→16→8→4→2→11024 \to 512 \to 256 \to 128 \to 64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1.

    210=10242^{10} = 1024, also log⁡21024=10\log_2 1024 = 10

    Zwischenergebnis

    10 Vergleiche.

  3. 3

    c) Die Voraussetzung, und was ohne sie passiert

    Die Daten müssen sortiert sein. Nur dann sagt der Vergleich mit dem mittleren Element, in welcher Hälfte der gesuchte Wert liegen kann. Wichtig: Auf unsortierten Daten liefert das Verfahren falsche Ergebnisse, keine langsamen.

Übung 2

mittel

Gegeben ist das sortierte Feld [3,7,11,18,25,31,44,52,60,77,88][3, 7, 11, 18, 25, 31, 44, 52, 60, 77, 88] mit den Indizes 0 bis 10.

a) Suche die 44 binär. Schreibe alle Schritte mit links, rechts und mitte auf. b) Suche die 20. Wie erkennt das Verfahren, dass sie fehlt? c) Wie viele Vergleiche hätte die lineare Suche jeweils gebraucht? d) Ein Programm sucht 5-mal in 1000 unsortierten Datensätzen. Lohnt sich Sortieren?

Tipp anzeigen

Zu a): mitte\texttt{mitte} wird abgerundet.

Lösung anzeigen

a) Ablauf:

Schrittlinksrechtsmittea[mitte]VergleichFolge
101053131<4431 < 44links = 6
261086060>4460 > 44rechts = 7
367644gefundenIndex 6

Drei Vergleiche.

b) Ablauf:

Schrittlinksrechtsmittea[mitte]VergleichFolge
101053131>2031 > 20rechts = 4
20421111<2011 < 20links = 3
33431818<2018 < 20links = 4
44442525>2025 > 20rechts = 3

Jetzt ist links=4>3=rechts\texttt{links} = 4 > 3 = \texttt{rechts}, die Schleifenbedingung ist verletzt. Das Verfahren meldet „nicht gefunden". Der leere Bereich ist also das Erkennungsmerkmal: Es gibt keine Stelle mehr, an der die 20 stehen könnte.

c) Für die 44 an Index 6: sieben Vergleiche (Indizes 0 bis 6). Für die fehlende 20: elf Vergleiche, also das ganze Feld.

d) Nein. Fünf lineare Suchen kosten 5⋅1000=50005 \cdot 1000 = 5000 Vergleiche. Sortieren kostet etwa 1000⋅log⁡21000≈1000⋅10=10 0001000 \cdot \log_2 1000 \approx 1000 \cdot 10 = 10\,000 Schritte, dazu noch 5⋅10=505 \cdot 10 = 50 für die Suchen. Die Vorsortierung ist damit etwa doppelt so teuer.

Die Grenze liegt hier bei ungefähr log⁡21000=10\log_2 1000 = 10 Suchvorgängen. Ab etwa zehn Suchen lohnt sich das Sortieren, bei fünf noch nicht.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Teil a): Tabelle führen statt im Kopf rechnen

    Man legt eine Tabelle mit links, rechts, mitte und dem Wert an und füllt sie Zeile für Zeile. mitte\texttt{mitte} wird abgerundet.

    \texttt{mitte} = (0+10) : 2 = 5

    Zwischenergebnis

    Erster Vergleich mit a[5]=31a[5] = 31.

    Nach jedem Vergleich wandert genau eine Grenze, und zwar um eins über die Mitte hinaus. So kann die schon geprüfte Mitte nicht noch einmal drankommen.

  2. 2

    Teil b): Wie ein Fehlschlag aussieht

    Man rechnet weiter, bis der Bereich leer wird. Das passiert, wenn links\texttt{links} größer als rechts\texttt{rechts} wird.

    Zwischenergebnis

    Nach vier Schritten links=4>rechts=3\texttt{links}=4 > \texttt{rechts}=3.

  3. 3

    Teil c): Den Vergleich ehrlich ziehen

    Man zählt bei der linearen Suche bis zur Fundstelle, beim Fehlschlag durch das ganze Feld. Bei nur elf Elementen ist der Unterschied gering, aber er wächst mit nn.

    7 \text{ gegen } 3 \qquad 11 \text{ gegen } 4

    Zwischenergebnis

    Binär gewinnt schon hier, aber unspektakulär.

    Genau deshalb lohnt sich bei kleinen Feldern die lineare Suche: Der Vorteil ist gering, der Aufwand beim Schreiben und die Fehleranfälligkeit dagegen höher.

  4. 4

    Teil d): Die Grenze ausrechnen, nicht schätzen

    Man stellt beide Gesamtaufwände einander gegenüber und vergleicht die Zahlen. Erst dann steht die Antwort fest.

    5 \cdot 1000 = 5000 \quad \text{gegen} \quad 10,000 + 50

    Zwischenergebnis

    Sortieren lohnt sich hier nicht.

Übung 3

schwer

a) Begründe rechnerisch, warum die binäre Suche log⁡2n\log_2 n Schritte braucht. b) Zeige an einem eigenen Beispiel, dass die binäre Suche auf unsortierten ein falsches Ergebnis liefern kann. c) (Vertiefung) Erkläre das Prinzip der Streuspeicherung und warum Kollisionen unvermeidlich sind. d) (Vertiefung) Nenne einen Fall, in dem eine sortierte Struktur der Streuspeicherung überlegen ist, obwohl diese schneller sucht.

Tipp anzeigen

Zu c): Wie viele mögliche Schlüssel gibt es, wie viele Plätze?

Lösung anzeigen

a) Nach jedem Schritt ist höchstens die Hälfte des Bereichs übrig. Nach kk Schritten sind es also n/2kn / 2^k Elemente. Das Verfahren endet, wenn nur noch eines übrig ist:

n2k=1  ⟺  2k=n  ⟺  k=log⁡2n\frac{n}{2^k} = 1 \;\Longleftrightarrow\; 2^k = n \;\Longleftrightarrow\; k = \log_2 n

Anschaulich: Jede Verdopplung der Datenmenge kostet genau einen zusätzlichen Schritt, denn eine Halbierung mehr genügt, um wieder bei einem Element anzukommen.

b) Feld [9,2,7,1,5][9, 2, 7, 1, 5], gesucht wird die 2 an Index 1.

Schritt 1: mitte=2\texttt{mitte} = 2, dort steht 7. Es gilt 7>27 > 2, also sucht das Verfahren links weiter: rechts=1\texttt{rechts} = 1. Schritt 2: mitte=(0+1):2=0\texttt{mitte} = (0+1):2 = 0, dort steht 9. Es gilt 9>29 > 2, also rechts=−1\texttt{rechts} = -1. Jetzt ist links=0>−1=rechts\texttt{links} = 0 > -1 = \texttt{rechts}, und das Verfahren meldet „nicht gefunden", obwohl die 2 im Feld steht.

Das Programm stürzt nicht ab und meldet keinen Fehler; es liefert schlicht ein falsches Ergebnis. Genau das macht diesen Fehlertyp so gefährlich.

c) Eine Streuwertfunktion hh berechnet aus dem Schlüssel unmittelbar den Speicherplatz: h(Schlu¨ssel)→Indexh(\text{Schlüssel}) \to \text{Index}. Gespeichert und gesucht wird an genau diesem Platz, weshalb beides nur eine Berechnung kostet, also O(1)O(1) im Mittel.

Kollisionen sind unvermeidlich, weil es mehr mögliche Schlüssel als Plätze gibt. Bei einer Tabelle mit 1000 Plätzen und beliebig langen Namen als Schlüsseln müssen zwangsläufig verschiedene Namen auf denselben Index abgebildet werden; das ist genau das Schubfachprinzip. Behandelt werden sie durch Verkettung (an jedem Platz hängt eine Liste) oder Sondieren (der nächste freie Platz wird genommen). Deshalb gilt O(1)O(1) nur im mittleren Fall: Fallen alle Schlüssel auf denselben Index, entsteht eine einzige lange Liste und die Suche wird wieder O(n)O(n).

d) Immer dann, wenn die Ordnung gebraucht wird. Beispiele:

  • „Alle Kundennummern zwischen 1000 und 2000", eine Bereichsabfrage.
  • „Der nächstgrößere vorhandene Wert", etwa bei einer Terminsuche.
  • „Gib alle Einträge sortiert aus."

Eine Streuspeicherung kann das nicht, weil sie die Schlüssel absichtlich über die Tabelle verstreut; benachbarte Schlüssel landen an unzusammenhängenden Stellen, und die Struktur weiß nichts über „größer" oder „kleiner". Bei einer sortierten Struktur ist eine Bereichsabfrage dagegen sehr billig: Man sucht die untere Grenze binär und liest von dort der Reihe nach weiter.

Das ist ein gutes Beispiel für die Kernaussage des Kapitels: Die Streuspeicherung erkauft ihre Geschwindigkeit damit, dass sie eine Eigenschaft der Daten aufgibt.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Die Schrittzahl der binären Suche herleiten

    Nach jedem Schritt ist höchstens die Hälfte des Bereichs übrig, nach kk Schritten also n/2kn / 2^k Elemente. Das Verfahren endet, wenn nur noch eines übrig ist: n2k=1⇔2k=n⇔k=log⁡2n\frac{n}{2^k} = 1 \Leftrightarrow 2^k = n \Leftrightarrow k = \log_2 n.

    n2k=1⇔k=log⁡2n\frac{n}{2^k} = 1 \Leftrightarrow k = \log_2 n

  2. 2

    b) Ein Gegenbeispiel für das falsche Ergebnis auf unsortierten Daten

    Feld [9,2,7,1,5][9, 2, 7, 1, 5], gesucht die 2 an Index 1. Schritt 1: mitte=2\texttt{mitte} = 2, dort steht 7; wegen 7>27 > 2 sucht das Verfahren links weiter (rechts=1\texttt{rechts} = 1). Schritt 2: mitte=0\texttt{mitte} = 0, dort steht 9; wegen 9>29 > 2 wird rechts=−1\texttt{rechts} = -1. Jetzt ist links>rechts\texttt{links} > \texttt{rechts}, das Verfahren meldet „nicht gefunden“, obwohl die 2 im Feld steht.

    [9,2,7,1,5][9, 2, 7, 1, 5]: mitte 7 → links; mitte 9 → links; links >> rechts → nicht gefunden

  3. 3

    c) (Vertiefung) Streuspeicherung und die Unvermeidbarkeit von Kollisionen

    Eine Streuwertfunktion hh berechnet aus dem Schlüssel unmittelbar den Speicherplatz: h(Schlu¨ssel)→Indexh(\text{Schlüssel}) \to \text{Index}. Gespeichert und gesucht wird an genau diesem Platz, weshalb beides nur eine Berechnung kostet, also O(1)O(1) im Mittel.

  4. 4

    d) (Vertiefung) Wo eine sortierte Struktur überlegen ist

    Immer dann, wenn die Ordnung gebraucht wird: „Alle Kundennummern zwischen 1000 und 2000“ (Bereichsabfrage), „der nächstgrößere vorhandene Wert“ (etwa bei einer Terminsuche), „gib alle Einträge sortiert aus“. Eine Streuspeicherung kann das nicht, weil sie die Schlüssel absichtlich über die Tabelle verstreut.

Zusammenfassung

Die lineare Suche geht die von vorn durch und braucht im schlechtesten Fall nn Vergleiche; ihr Vorteil ist, dass sie überhaupt keine Voraussetzung stellt und deshalb immer funktioniert. Die binäre Suche halbiert in jedem Schritt den Bereich und kommt mit log⁡2n\log_2 n Vergleichen aus, weil nach kk Schritten nur noch n/2kn/2^k Elemente übrig sind; sie setzt aber sortierte Daten voraus und liefert ohne diese Sortierung nicht ein langsames, sondern ein falsches Ergebnis. Da Sortieren selbst O(nlog⁡n)O(n \log n) kostet, lohnt es sich erst ab etwa log⁡n\log n Suchvorgängen, weshalb Datenbanken für regelmäßig durchsuchte Spalten einen Index anlegen, ihn aber nicht für jede einmalige Abfrage aufbauen. Die Streuspeicherung berechnet den Speicherplatz direkt aus dem Schlüssel und erreicht damit im Mittel O(1)O(1), muss dafür aber Kollisionen behandeln, die nach dem Schubfachprinzip unvermeidlich sind, und gibt jede Ordnung der Daten auf. Damit zeigt sich der rote Faden des Kapitels: Jede Steigerung der Geschwindigkeit wird mit einer zusätzlichen Voraussetzung oder einer aufgegebenen Eigenschaft bezahlt.