Ein Ratespiel

Lass uns ein kleines Spiel spielen, um dir eine Vorstellung davon zu geben, wie verschiedene Algorithmen für das gleiche Problem sehr unterschiedliche Effizienzen haben können. Der Computer wählt zufällig eine ganze Zahl zwischen 1 und 15 aus. Du rätst so lange, bis du die Zahl des Computers gefunden hast, und der Computer sagt dir jedes Mal, ob deine Schätzung zu hoch oder zu niedrig war:

Wenn du die Zahl gefunden hast, überlege dir, welche Technik du benutzt hast, um zu entscheiden, welche Zahl du als nächstes erraten musst.

Vielleicht hast du zuerst 1, dann 2, dann 3, dann 4 usw. geraten, bis du die richtige Zahl erraten hast. Wir nennen diese Vorgehensweise lineare Suche, weil du die Zahlen so geraten hast, als ob sie hintereinander aufgereiht wurden. Das würde funktionieren. Aber was ist die höchste Zahl der Versuche die du benötigst? Wenn der Computer 15 auswählt, benötigst du 15 Versuche. Dann wiederum, wenn du wirklich Glück hast, wählt der Computer 1 aus und du errätst die richtige Zahl gleich. Wie wäre es mit dem arithmetischen Mittel? Wenn der Computer die gleiche Wahrscheinlichkeit hat, irgendeine Zahl zwischen 1 und 15 auszuwählen, dann benötigst du im Schnitt 8 Versuche.

Aber du könntest etwas viel Effizienteres machen als nur die Zahlen 1, 2, 3, 4 zu raten, richtig? Nachdem dir der Computer sagt, ob dein Vorschlag zu niedrig, zu hoch, oder richtig war, kannst du die Zahl 8 als deinen ersten Versuch nehmen. Wenn die Zahl, die der Computer ausgewählt hat, kleiner als 8 ist, dann weißt du, dass 8 zu hoch ist, und kannst somit alle Zahlen von 8 bis 15 eliminieren. Wenn die ausgewählte Zahl des Computers größer als 8 ist, dann kannst du die Zahlen 1 bis 8 eliminieren. In beiden Fällen kannst du die Hälfte der Zahlen eliminieren. Bei deinem nächsten Versuch eliminiere die Hälfte der übrigen Zahlen. Mach immer so weiter und eliminiere immer die Hälfte der verbleibenden Zahlen.

Wir nennen diese Vorgehensweise, bei der du halbierst, Binärsuche. Egal welche Zahl zwischen 1 und 15 der Computer ausgewählt hat, du solltest in der Lage sein innerhalb von 4 Versuchen die richtige Zahl mit dieser Technik zu erraten.

Versuche hier eine Zahl zwischen 1 und 300 zu erraten. Du solltest nicht mehr als 9 Versuche benötigen.

Wie viele Versuche hast du benötigt um die Zahl dieses Mal zu finden? Warum solltest du nicht mehr als 9 Versuche benötigen? (Kannst du dir das mit einer mathematischen Vorgehensweise erklären?)

Wir werden auf die Binärsuche zurückkommen und sehen wie man effizient nach einem Element in JavaScript sucht. Aber lassen wir das zunächst mal. Jetzt schauen wir uns eine knifflige Algorithmus-Aufgabe an.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.