Komplexität von Algorithmen – O(log n), O(n), O(n log n), O(n²) und ein Sortierrennen
InformatikAlgorithmen und ProblemlösenAlter 15–16
Wofür nutzen Sie diese Simulation hauptsächlich?
Im Unterricht einsetzen: Ihre Schülerinnen und Schüler öffnen sie über einen Link oder QR-Code, ganz ohne Konto.
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. Ein zweiter Bildschirm, „Handlungsreisender“, setzt Städte auf eine Karte und vergleicht Brute Force, die alle (n − 1)!/2 Rundreisen prüft und bald unzumutbar lange dauert, mit der schnellen Heuristik des nächsten Nachbarn.
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 Eingabegröße n wächst, ohne konstante Faktoren zu beachten. Das Diagramm vergleicht log₂n, n, n·log₂n und n²; die Messwerte zeigen Bubblesort bei etwa n²/2 Vergleichen und Quicksort bei etwa 1,4·n·log₂n. Manche Probleme sind weit schlimmer. Der Bildschirm Handlungsreisender probiert jede Rundreise aus, insgesamt (n − 1)!/2 Stück: Jede weitere Stadt vervielfacht den Aufwand, und 16 Städte würden Stunden dauern. Eine Heuristik wie der nächste Nachbar antwortet in n(n − 1)/2 Schritten, schnell, aber nicht immer mit der kürzesten Rundreise.
So funktioniert es
Ziehen Sie im Diagramm, um n zu ändern, und schalten Sie Log-Skala für die Schrittachse ein, wenn die Kurven weit auseinanderliegen; drücken Sie Rennen, um die Sortierverfahren zu verfolgen. Drücken Sie dann Rundreise: Tippen Sie auf die Karte, um Städte hinzuzufügen, drücken Sie Alle prüfen und Nächster Nachbar, und vergleichen Sie Rundreisen und Schritte. Ändern Sie Anzahl der Städte und Rechengeschwindigkeit, um die Zeit explodieren 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, n, n², 2ⁿ und n!
- Log-Skala für die Schrittachse
- Renngeschwindigkeit 5–200 Schritte/s
- Bildschirm Komplexitätsdiagramm, Handlungsreisender
- Anzahl der Städte (Handlungsreisender) 4–16
- Zufallsstartwert für die Städte 1–999
- Rechengeschwindigkeit 10⁶ Schritte pro Sekunde, 10⁹ Schritte pro Sekunde, 10¹² Schritte pro Sekunde
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?