MINT lernen

Übungen: Suchverfahren vergleichen

Zehn Übungen zum Vergleich der Suchverfahren — von den drei Fällen bis zur Frage, wann Sortieren sich lohnt.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.

A1
Drei Fälle
AFB I

Es geht um den besten, ungünstigsten und durchschnittlichen Fall der beiden Suchverfahren. Geben Sie alle zutreffenden Aussagen an.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Der beste Fall der binären Suche ist x in der ersten Mitte, nicht an Index 0. Ihr Durchschnitt liegt nur knapp einen Vergleich unter dem ungünstigsten Fall, weil die meisten Elemente erst in den letzten Halbierungsstufen erreicht werden. Drei Hilfsvariablen sind konstanter Zusatzspeicher — unabhängig von n, genau wie das i der linearen Suche.
Ansatz: Wo schaut die binäre Suche zuerst hin?
Weiter: Die Hälfte aller Elemente wird erst beim letzten möglichen Vergleich erreicht.
A2
Höchstens so viele Vergleiche
AFB I

Alle Reihungen sind sortiert. Ermitteln Sie für jede Länge n die höchstens nötige Zahl der Vergleiche der binären Suche und verbinden Sie.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
\(\lfloor\log_2 n\rfloor + 1\): \(2^2 \le 7 < 2^3\) → 3; \(8 = 2^3\) → 4; \(2^5 \le 60 < 2^6\) → 6; \(2^8 \le 500 < 2^9\) → 9; \(2^{12} = 4096 \le 5000\) → 13. Achtung bei Zweierpotenzen: n = 8 braucht einen Vergleich mehr als n = 7.
Ansatz: Suchen Sie jeweils die größte Zweierpotenz, die nicht größer als n ist.
Weiter: Ist \(2^k \le n < 2^{k+1}\), dann sind es \(k + 1\) Vergleiche.
A3
Stimmt's? — Wachstum
AFB I

Fünf Behauptungen zum Wachstum der Vergleichszahlen im ungünstigsten Fall. Nennen Sie jeweils, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Die binäre Suche braucht zusätzliche Vergleiche nur bei einer Verdopplung der Datenmenge — deshalb bleibt sie selbst bei riesigen Reihungen bei wenigen Dutzend Vergleichen.
Ansatz: Setzen Sie für n eine konkrete Zahl ein und verdoppeln Sie sie.
Weiter: \(2^{10} \approx 1000\), \(2^{20} \approx 1\,000\,000\).
A4
Welches Verfahren passt?
AFB II

Entscheiden Sie für jede Situation, welches Vorgehen den geringsten Gesamtaufwand an Vergleichen hat. Sortieren kostet etwa \(\frac{n^2}{2}\) Vergleiche.

Klicken Sie die Felder an, die zutreffen. Ein zweiter Klick nimmt die Markierung zurück.
Situationlineare Suchebinäre Sucheerst sortieren, dann binär
unsortierte Liste mit 40 Namen, ein einziges Nachschlagen
sortierte Reihung mit 2 Mio. Artikelnummern, 50 Anfragen
unsortierte Reihung mit 5 000 Werten, 100 000 Anfragen
unsortierte Reihung mit 1 Mio. Werten, genau eine Anfrage
Messreihe nach Zeit geordnet, gesucht wird der erste Tag über 30 °C
Nur zwei Fragen entscheiden: Ist die Reihung schon sortiert? Und wird oft genug gesucht, dass sich \(\frac{n^2}{2}\) Sortiervergleiche verteilen? Bei 5 000 Werten kostet Sortieren etwa 12,5 Mio. Vergleiche, 100 000 lineare Suchen aber bis zu 500 Mio. Die Messreihe ist nach Zeit, nicht nach Temperatur sortiert — binär suchen geht nicht, und Sortieren würde die Zeitinformation zerstören.
Ansatz: Zuerst: Ist die Reihung nach dem Suchkriterium sortiert?
Weiter: Vergleichen Sie \(k \cdot n\) mit \(\frac{n^2}{2}\).
A5
Wenn die Daten wachsen
AFB II

Wie ändert sich die Zahl der Vergleiche (ungünstigster Fall, wenn nicht anders angegeben)? Schätzen Sie jede Veränderung ab, ohne zu rechnen.

Wählen Sie für jede Zeile eine Stufe: 1 = bleibt gleich, 2 = wächst um 1, 3 = wächst um 3, 4 = verdoppelt sich, 5 = vervierfacht sich etwa. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = bleibt gleich5 = vervierfacht sich etwa
lineare Suche, n verdoppeln
binäre Suche, n verdoppeln
binäre Suche, n verachtfachen
Sortieren mit ≈ n²/2 Vergleichen, n verdoppeln
lineare Suche, bester Fall, n verdoppeln
Verachtfachen heißt dreimal verdoppeln — bei der binären Suche also drei Vergleiche mehr. Beim Sortieren wird n quadriert: \((2n)^2 = 4n^2\). Der beste Fall der linearen Suche hängt gar nicht von n ab.
Ansatz: Zerlegen Sie „verachtfachen“ in einzelne Verdopplungen.
Weiter: Beim Quadrat gilt \((2n)^2 = 4 \cdot n^2\).
A6
Lohnt sich das Sortieren?
AFB II

Eine unsortierte Reihung enthält n = 1 499 Seriennummern. Sortieren kostet \(\frac{n(n-1)}{2}\) Vergleiche. Berechnen Sie Schritt für Schritt.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Mittlere Vergleichszahl der linearen Suche, wenn die Nummer vorhanden ist: Vergleiche
  2. Höchstzahl der Vergleiche der binären Suche nach dem Sortieren: Vergleiche
  3. Vergleiche für das einmalige Sortieren: Vergleiche
  4. Ab so vielen Suchen (ungünstigster Fall) ist „sortieren + binär“ günstiger als „nur linear“: Suchen
\(\frac{1500}{2} = 750\); \(2^{10} = 1024 \le 1499\) → 11; \(\frac{1499 \cdot 1498}{2} = 1\,122\,751\). Bedingung \(k \cdot 1499 > 1\,122\,751 + 11k\), also \(k > \frac{1\,122\,751}{1488} \approx 754{,}5\) — ab 755 Suchen, rund \(\frac{n}{2}\).
Ansatz: Durchschnitt: \(\frac{n+1}{2}\); binär: \(\lfloor\log_2 n\rfloor + 1\).
Weiter: Stellen Sie \(k \cdot n\) und Sortierkosten \(+\, k \cdot 11\) gegenüber und lösen Sie nach \(k\) auf.
A7
Was wächst mit n?
AFB II Mix

Der Aufwand hängt unterschiedlich stark von der Länge n der Reihung ab. Ordnen Sie jede Größe in die passende Wachstumsklasse ein.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1konstant
2logarithmisch
3linear
Beide Suchverfahren arbeiten in-place: Sie brauchen nur ein paar Hilfsvariablen, egal wie lang die Reihung ist. Linear wachsen dagegen die Reihung selbst, die Zahl ihrer Indizes und der mittlere Aufwand \(\frac{n+1}{2}\) der linearen Suche — auch halb so viel wächst noch linear.
Ansatz: Fragen Sie jeweils: Was passiert bei doppeltem n?
Weiter: \(\frac{n+1}{2}\) verdoppelt sich ungefähr mit n — das ist linear.
A8
Fehlersuche im Referat
AFB III

Aus einem Referat über Suchverfahren stammen die folgenden Sätze. Überprüfen Sie die Aussagen und markieren Sie die drei falschen.

In diesem Text stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen bleiben stehen.
Am häufigsten falsch eingeschätzt wird die Größenordnung: \(\log_2\) einer Million ist rund 20, nicht die Wurzel 1 000. Und die Schnelligkeit der binären Suche gilt nur, wenn die Sortierung schon vorliegt — ihre Kosten muss man sonst mitrechnen.
Ansatz: Drei Sätze sind falsch — prüfen Sie Zahlen, Voraussetzungen und Speicher.
Weiter: \(2^{20} = 1\,048\,576\).
A9
Die glatte Zweierpotenz
AFB III Trick

Bei \(n = 1\,000\,000\) braucht die binäre Suche höchstens 20 Vergleiche. Bestimmen Sie die Höchstzahl der Vergleiche für eine sortierte Reihung mit \(n = 1\,048\,576 = 2^{20}\) Elementen.

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
\(\lfloor\log_2 2^{20}\rfloor + 1 = 20 + 1 = 21\). Bei einer Zweierpotenz passt genau eine Halbierung mehr hinein: Nach 20 Vergleichen ohne Treffer kann noch ein Element übrig sein. Mit \(n = 2^{20} - 1\) wären es wieder 20.
Ansatz: Setzen Sie in \(\lfloor\log_2 n\rfloor + 1\) ein — der Logarithmus ist hier glatt.
Weiter: Die Abrundung ändert nichts, \(\log_2 2^{20} = 20\).
A10
Der Fahrradverleih
AFB III

Ein Fahrradverleih hat 3 000 Räder, deren Rahmennummern unsortiert gespeichert sind. Täglich werden 400 Nummern geprüft. Sortieren kostet \(\frac{n(n-1)}{2}\) Vergleiche. Beurteilen Sie, ob sich Sortieren lohnt.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

Pro Tag nur linear (ungünstigster Fall): Vergleiche

Einmaliges Sortieren: Vergleiche

Pro Tag binär nach dem Sortieren: Vergleiche

Am ersten Tag ist .

Ändern sich die Daten nicht, ist „sortieren + binär“ insgesamt günstiger ab Tag .

Linear: \(400 \cdot 3000 = 1\,200\,000\) pro Tag. Sortieren: \(\frac{3000 \cdot 2999}{2} = 4\,498\,500\) einmalig, danach \(400 \cdot 12 = 4\,800\) pro Tag (\(2^{11} = 2048 \le 3000\)). Nach 3 Tagen: 3,6 Mio. gegen 4,51 Mio.; nach 4 Tagen: 4,8 Mio. gegen 4,52 Mio. — ab Tag 4 lohnt sich das Sortieren, vorausgesetzt, die Nummern ändern sich nicht.
Ansatz: Rechnen Sie die Summen für Tag 1, 2, 3, … nebeneinander aus.
Weiter: Binär: \(\lfloor\log_2 3000\rfloor + 1 = 12\) Vergleiche pro Prüfung.