Viele Algorithmen für ein Problem
Ein Algorithmus ist eine Reihe genauer Schritte, die ein Problem lösen. Die meisten Probleme lassen sich mit mehr als einem Algorithmus lösen. Um zum Beispiel einen Namen in einer Liste zu finden, kannst du jeden Namen prüfen oder (wenn die Liste sortiert ist) die Liste immer wieder halbieren.
Beide liefern die richtige Antwort. Der Unterschied ist die Effizienz: wie viel Arbeit und Speicher jeder braucht. Gute Programmierer wählen den Algorithmus, der auch bei großen Datenmengen schnell bleibt.
Algorithmen nach der benötigten Zeit vergleichen
Mit der Stoppuhr zu messen ist unfair: Ein schneller Computer lässt einen langsamen Algorithmus gut aussehen. Deshalb zählen wir Grundschritte (Vergleiche, Vertauschungen, Additionen) in Abhängigkeit von der Eingabegröße n.
Bester, durchschnittlicher und schlechtester Fall
Der beste Fall ist die glücklichste Eingabe (13 liegt in der ersten Kiste: 1 Schritt). Der schlechteste Fall ist die unglücklichste (13 ist nicht da: n Schritte). Meistens nennen wir den schlechtesten Fall, denn er ist ein Versprechen: Der Algorithmus wird nie langsamer als das.
Zeitkomplexität und Speicherkomplexität
Die Zeitkomplexität sagt, wie die Zahl der Schritte mit n wächst. Die Speicherkomplexität sagt, wie der zusätzliche Speicher mit n wächst. Merge-Sort ist schnell, braucht aber zusätzlichen Speicher; Bubble-Sort braucht fast keinen zusätzlichen Speicher, ist aber langsam.
Big-O-Notation
Big O beschreibt die Wachstumsrate und ignoriert kleine Details. Wir behalten nur den größten Term und lassen konstante Zahlen weg: 3n² + 5n + 2 wird zu O(n²), weil bei großem n der n²-Teil fast alles ausmacht.
| Big O | Name | n = 16 | n = 1000 | Beispiel |
|---|---|---|---|---|
| O(1) | konstant | 1 | 1 | Element 5 eines Arrays lesen |
| O(log n) | logarithmisch | 4 | etwa 10 | binäre Suche |
| O(n) | linear | 16 | 1000 | lineare Suche, größte Zahl finden |
| O(n log n) | n log n | 64 | etwa 10.000 | Merge-Sort |
| O(n²) | quadratisch | 256 | 1.000.000 | Bubble-Sort, verschachtelte Schleifen |
Faustregel für Code: Eine Schleife über n Elemente ist O(n); eine Schleife in einer Schleife ist O(n²); wenn das Problem jedes Mal halbiert wird, ist es O(log n).
Effizienz von linearer und binärer Suche
Die lineare Suche prüft die Elemente eins nach dem anderen. Schlechtester Fall: n Vergleiche, also O(n). Sie funktioniert bei jeder Liste, sortiert oder nicht.
Die binäre Suche braucht eine sortierte Liste. Schau auf die Mitte; ist sie zu groß, wirf die rechte Hälfte weg, sonst die linke. Jeder Schritt halbiert die Liste, also sind es im schlechtesten Fall etwa log₂ n + 1 Vergleiche: O(log n). Bei 1.000.000 Elementen sind das etwa 20 Schritte statt 1.000.000.
Effizienz von Sortieralgorithmen
Bubble-, Insertion- und Selection-Sort benutzen eine Schleife in einer Schleife und brauchen daher etwa n²/2 Vergleiche: O(n²). Insertion-Sort ist im besten Fall (eine schon sortierte Liste) O(n).
Merge-Sort halbiert die Liste etwa log₂ n Mal und leistet auf jeder Ebene etwa n Arbeit: O(n log n). Er braucht O(n) zusätzlichen Speicher.
Die binäre Suche braucht eine sortierte Liste. Wenn du nur einmal suchst, kostet das Sortieren vorher (n log n) mehr als eine lineare Suche (n). Wenn du oft suchst, lohnt sich einmaliges Sortieren.
Vorbedingung, Nachbedingung und Fallen der Rekursion
Eine Vorbedingung ist das, was vor dem Start des Algorithmus gelten muss (binäre Suche: die Liste ist sortiert). Eine Nachbedingung ist das, was am Ende versprochen wird (Sortieren: jedes Element ist kleiner oder gleich dem nächsten). Wenn du sie aufschreibst, kannst du den Algorithmus leichter testen und beweisen.
Rekursion heißt, dass eine Funktion sich selbst für ein kleineres Problem aufruft. Häufige Fehler:
- Kein Basisfall oder ein Basisfall, der nie erreicht wird: Die Aufrufe hören nie auf (Stack Overflow).
- Das Problem wird bei jedem Aufruf nicht kleiner.
- Dieselbe Arbeit wird wiederholt: Ein einfaches rekursives Fibonacci ruft fib(3) immer wieder auf und wächst deshalb wie O(2ⁿ). Antworten zu speichern (Memoisation) macht daraus O(n).
- Sehr tiefe Rekursion braucht viel Speicher, einen Stack-Frame pro Aufruf.
Probier es aus: zwei Suchen im Wettrennen
Schreibe die Zahlen 1 bis 32 auf Papierzettel und lege sie in der richtigen Reihenfolge mit der Schrift nach unten hin. Eine Freundin oder ein Freund denkt sich eine geheime Zahl aus. Suche zuerst Zettel für Zettel und zähle, wie viele Zettel du umdrehst. Suche dann, indem du immer den mittleren Zettel umdrehst. Wiederhole das 5 Mal. Welche Methode brauchte nie mehr als 6 Umdrehungen? Prüfe es mit dem Regler im letzten 3D-Schritt (n = 32: log₂ 32 = 5).
Wichtige Formeln und Definitionen
- Lineare Suche: schlechtester Fall n Vergleiche → O(n)
- Binäre Suche: schlechtester Fall etwa log₂ n + 1 Vergleiche → O(log n)
- Bubble- / Insertion- / Selection-Sort: etwa n(n − 1)/2 Vergleiche → O(n²)
- Merge-Sort: etwa n log₂ n Vergleiche → O(n log n)
- Big-O-Regel: größten Term behalten, Konstanten weglassen (5n² + 3n → O(n²))
- n verdoppeln: O(1) gleich, O(log n) +1, O(n) ×2, O(n²) ×4
Gelöste Beispiele
1. Eine Liste hat 50 Namen. Wie viele Vergleiche braucht die lineare Suche im besten und im schlechtesten Fall?
Bester Fall: Der Name steht an erster Stelle → 1 Vergleich. Schlechtester Fall: Der Name steht ganz hinten oder fehlt → 50 Vergleiche. Die lineare Suche ist O(n).
2. Wie viele Vergleiche braucht die binäre Suche höchstens bei einer sortierten Liste mit 1024 Elementen?
Jeder Schritt halbiert die Liste: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Das sind 10 Halbierungen plus die letzte Prüfung: höchstens 11 Vergleiche (log₂ 1024 = 10).
3. Gib das Big O von f(n) = 4n² + 10n + 7 an.
Behalte den größten Term (4n²) und lass die Konstante 4 weg: O(n²).
4. Eine Schleife lässt i von 1 bis n laufen, und darin läuft eine zweite Schleife mit j von 1 bis n. Wie oft läuft die innere Zeile?
n Mal für jeden der n Werte von i: n × n = n². Zeitkomplexität O(n²).
5. Ein O(n²)-Programm sortiert 1000 Elemente in 2 Sekunden. Wie lange dauert es ungefähr für 3000 Elemente?
n wird 3 Mal so groß, also wird n² zu 3² = 9 Mal so groß: etwa 2 × 9 = 18 Sekunden.
6. Vergleiche Bubble-Sort und Merge-Sort für n = 1000 Elemente.
Bubble-Sort: etwa n²/2 = 500.000 Vergleiche. Merge-Sort: etwa n log₂ n = 1000 × 10 = 10.000. Merge-Sort leistet etwa 50 Mal weniger Arbeit, braucht aber zusätzlichen Speicher.
Häufige Fehler
- Die Geschwindigkeit nur mit einer Stoppuhr auf einem Computer messen. Zähle stattdessen die Schritte in Abhängigkeit von n.
- Binäre Suche auf einer unsortierten Liste benutzen. Ihre Vorbedingung ist eine sortierte Liste.
- Konstanten in Big O behalten, zum Beispiel O(2n) schreiben. Das ist einfach O(n).
- Eine rekursive Funktion ohne Basisfall schreiben, oder eine, die das Problem nicht kleiner macht.