Big-O — benenne die Komplexität des Codes
Lies den Ausschnitt, benenne seine Laufzeitkomplexität, sieh die Wachstumskurve. Sechs Klassen, sechs Runden. Kostenlos.
Fünf Ausschnitte, fünf der sechs Komplexitätsklassen, jede einmal.
So wird gespielt
- Lies den Ausschnitt und wähle seine Laufzeitkomplexität aus den sechs.
- Die Wachstumskurve wird nach jeder Antwort gezeichnet — deine rot, die richtige grün.
- Fünf der sechs Klassen pro Durchlauf, ohne Wiederholung — immer dasselbe zu antworten ist also höchstens einmal richtig.
- Aufeinanderfolgende richtige Antworten bringen mehr. Eine falsche setzt die Serie zurück.
So funktioniert es
Jede Runde zeigt ein kurzes Stück Code und fragt nach seiner Laufzeitkomplexität. Du antwortest, und die Wachstumskurve wird gezeichnet — deine gegen die richtige — so dass die Wahl aufhört, ein Etikett zu sein, und zu einer Form wird, die man sehen kann. Ein Durchlauf fragt fünf der sechs Klassen, gemischt und ohne Wiederholung — immer dasselbe zu antworten ist also höchstens einmal richtig, und welche Klasse ausfällt wechselt, sodass die letzte Runde nie durch Ausschluss geschenkt ist. Die Ausschnitte sind so gewählt, dass jeder eine vertretbare Antwort hat: keine vorzeitigen Rücksprünge, keine versteckten Bibliothekskosten und nichts, das seine eigene Komplexität in einem Kommentar verrät. Sortieren gilt durchgehend als O(n log n), also das, was jede gängige Standardbibliothek liefert. Läuft auf deinem Gerät, es wird nichts verschickt, und man muss sich nirgends anmelden.
Big-O beschreibt, wie die Kosten wachsen, nicht wie hoch sie sind. Ein O(n²) mit guten Konstanten schlägt ein aufgeblähtes O(n log n) bei den Größen, die echter Code meistens sieht — das Thema eines anderen Spiels auf dieser Seite.
Häufig gestellte Fragen
Warum ist die Kurve logarithmisch skaliert?
Weil sechs Klassen sonst nicht in ein Diagramm passen. Bei n=24 kostet eine konstante Funktion 1 und eine exponentielle sechzehn Millionen, auf einer linearen Achse wären also fünf der sechs Kurven dieselbe flache Linie am Boden. Eine log-Skala macht aus jeder Klasse eine unterscheidbare Steigung, und genau die lohnt sich zu sehen.
Ist Sortieren wirklich O(n log n)?
Für Vergleichssortierer ja — das ist eine bewiesene untere Schranke und das, was jede gängige Standardbibliothek liefert. Counting- und Radixsort unterbieten sie, indem sie nicht vergleichen, brauchen dafür aber Annahmen über die Schlüssel. Wenn ein Ausschnitt hier sort() aufruft, kostet das n log n.
Warum gibt es keine Ausschnitte mit vorzeitigem Rücksprung?
Weil ein vorzeitiger Rücksprung einen schlechtesten Fall zu einem durchschnittlichen macht und die Antwort dann keine einzelne Klasse mehr ist. Eine lineare Suche, die beim ersten Treffer zurückkehrt, ist im schlechtesten Fall O(n) und O(1), wenn der Treffer immer vorn liegt — nach „der“ Komplexität zu fragen wäre unfair. Die binäre Suche ist die Ausnahme: sie springt früh zurück und ist trotzdem exakt O(log n).
Zählt die Serie?
Ja. Jede zweite richtige Antwort in Folge erhöht, was die nächste einbringt, bis zu einer Obergrenze — ein sauberer Durchlauf ist also deutlich mehr wert als vier richtige und zwei falsche. Eine falsche setzt sie zurück.