Big-O-Komplexitäts-Explorer

Big-O beschreibt, wie der Aufwand mit wachsender Eingabegröße zunimmt. Eine einzelne Schleife wächst etwa mit N, verschachtelte Schleifen oft mit N², und verzweigte Rekursion kann exponentiell wachsen. Die wichtige Lehre ist die Größenordnung: bei kleinem N sehen viele Ansätze ähnlich aus, bei größerem N dominiert die Wachstumsklasse die Laufzeit.

Am deutlichsten spürt man eine Wachstumsklasse, wenn man die Eingabe verdoppelt und beobachtet, was mit dem Aufwand passiert. Bei O(log N) bewegt er sich kaum — die binäre Suche findet ein Element unter einer Million in etwa 20 Vergleichen. Bei O(N) verdoppelt sich die Arbeit, bei O(N²) vervierfacht sie sich. Schiebe N in diesem Tool und sieh, wie die Abstände von unsichtbar bis überwältigend wachsen.

Eine niedrigere Wachstumsklasse garantiert kein schnelleres Programm. Informatiker nennen die Ausnahmen galaktische Algorithmen: Verfahren mit besserer O-Notation, deren verborgener konstanter Faktor so gewaltig ist, dass sie einfachere Methoden erst bei Eingaben übertreffen, die größer sind als alles im physikalischen Universum. Mehrere rekordverdächtige Algorithmen zur Matrixmultiplikation werden genau deshalb nie eingesetzt — Big-O lässt stillschweigend die Konstanten weg, die über die tatsächliche Geschwindigkeit entscheiden.