Komplexität von Algorithmen – O(log n), O(n), O(n log n), O(n²) und ein Sortierrennen
InformatikAlgorithmen und ProblemlösenAlter 15–16
Im Unterricht einsetzen: Ihre Schülerinnen und Schüler öffnen sie über einen Link oder QR-Code, ganz ohne Konto.
Als Nächstes in Algorithmen und Problemlösen
Ein Diagramm zeigt die Schrittzahl in Abhängigkeit von der Eingabegröße n für die Funktionen log₂n, n, n·log₂n und n², zusammen mit live gemessenen Vergleichszahlen von Bubblesort und Quicksort. Die Lernenden ziehen die n-Markierung im Diagramm, um Werte abzulesen, und klicken dann auf „Rennen“, um beide Algorithmen dasselbe Array mit gleicher Schrittrate sortieren zu sehen: Quicksort (n log n) ist vor Bubblesort (n²) fertig, und der Abstand wächst mit n.
Lektion: Algorithmen bewerten: Anzahl der Operationen in Abhängigkeit von der Eingabegröße, O-Notation, Vergleich von Bubblesort und Quicksort
Was sie zeigt
Die Komplexität eines Algorithmus beschreibt, wie die Zahl der Operationen mit der Datengröße n wächst, ohne konstante Faktoren zu beachten. Das Diagramm vergleicht vier Wachstumsraten: log₂n steigt kaum, n wächst proportional, n·log₂n etwas schneller, und n² vervierfacht sich, sobald sich n verdoppelt. Die Messwerte bestätigen die Theorie: Auf einem zufälligen Array braucht Bubblesort etwa n²/2 Vergleiche, Quicksort etwa 1,4·n·log₂n. Bei kleinem n spielt der Unterschied kaum eine Rolle; bei großen Datenmengen entscheidet die Wahl des Algorithmus, ob ein Programm Sekunden oder Stunden braucht.
So funktioniert es
Beginnen Sie mit Angezeigte theoretische Kurven auf allen vier Funktionen und ziehen Sie im Diagramm, um n zu ändern und die Werte jeder Kurve abzulesen. Liegen die Kurven zu weit auseinander, schalten Sie Log-Skala für die Schrittachse ein. Starten Sie dann das Rennen, damit beide Algorithmen dasselbe Array im gleichen Schritttakt sortieren, und wiederholen Sie es mit Neues Array und größerem n, um den wachsenden Abstand zu sehen.
Einstellbare Parameter
- Datengröße n 4–100
- Angezeigte theoretische Kurven log₂n, n, n·log₂n, n², n und n², log₂n, n und n·log₂n
- Log-Skala für die Schrittachse
- Renngeschwindigkeit 5–200 Schritte/s
Fragen zum Erkunden
- Um welchen Faktor wächst n², wenn sich n von 50 auf 100 verdoppelt, und um welchen Faktor ungefähr n·log₂n?
- Warum bleibt die Kurve log₂n fast flach, während die Kurve n² steil ansteigt?
- Wie viele Vergleiche mehr braucht Bubblesort bei n = 10 als Quicksort, und spielt dieser Unterschied praktisch eine Rolle?
