Big-O-Komplexitäts-Explorer

Sieh, wie Komplexitätsklassen von Algorithmen mit wachsender Eingabegröße N zunehmen.

Rechenbeispiel — Big-O-Komplexitäts-Explorer

O(1)	1
O(log N)	7
O(N)	100
O(N log N)	664
O(N²)	10.000

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Big-O-Komplexitäts-Explorer

Big-O ist eine obere Schranke für das Wachstum, keine Zeitmessung. Die Aussage, ein Algorithmus sei O(N²), bedeutet, dass sein Aufwand ab einer bestimmten Eingabegröße unter einem festen Vielfachen von N² bleibt — sie sagt nichts über Sekunden aus und überhaupt nichts über kleine Eingaben.

Was die einzelnen Symbole bedeuten

N: die Eingabegröße — wie viele Elemente dem Algorithmus übergeben werden. Das ist die oben eingestellte Zahl, irgendwo von 2 bis 1.000.000.
f(N): der tatsächlich bei dieser Größe geleistete Aufwand, gezählt in abstrakten Operationen statt in Sekunden.
c: ein konstanter Faktor, den die Notation verbergen darf. Die Aussage lautet f(N) ≤ c·g(N); c könnte 2 oder 2000 sein, und genau das ist die Information, die Big-O verwirft.
n₀: die Größe, ab der die Schranke gelten muss. Unterhalb von n₀ können die Klassen in beliebiger Reihenfolge liegen; deshalb drängen sich die fünf Zahlen oben bei kleinem N zusammen.

Woher die Formel kommt

Beginne mit der Aussage, die präzisiert werden muss: Der Aufwand f(N) wächst schließlich nicht schneller als eine Referenzfunktion g(N).
“Nicht schneller” muss einen konstanten Faktor zulassen, denn das Optimieren einer inneren Schleife ändert nur die Konstante, nicht den Verlauf. Erlaube also einen Faktor: f(N) ≤ c·g(N).
Und “schließlich” muss kleine Eingaben entschuldigen, bei denen alles passieren kann. Verlange die Ungleichung erst, sobald N ≥ n₀ gilt. Zusammen: f(N) = O(g(N)) bedeutet, dass ein c > 0 und ein n₀ existieren, sodass f(N) ≤ c·g(N) für jedes N ≥ n₀ gilt.

So liest du, was du siehst

Die fünf Zeilen zeigen eine Eingabegröße, angewendet auf fünf Wachstumsklassen mit allen Konstanten auf 1 gesetzt — es handelt sich also um Operationszahlen, nicht um Laufzeiten. Beim Standardwert N = 100 lauten sie 1, 7, 100, 664 und 10,000. Der Logarithmus ist zur Basis 2: log₂ 100 ≈ 6.64, weshalb O(log N) 7 anzeigt und O(N log N) 664 statt 700.

Setzt voraus: Dass eine Operation genauso viel kostet wie jede andere und dass die Anzahl exakt gezählt statt gemessen ist. Genau das macht den Vergleich sauber und ebenso abstrakt — Speicherzugriffsmuster, Cache-Verhalten und Festplatte liegen außerhalb dieses Modells, und auf realer Hardware entscheiden sie regelmäßig darüber, welcher von zwei Algorithmen gewinnt.
Versagt, wenn: Die Schranke verspricht unterhalb von n₀ nichts, und das lässt sich direkt beobachten: Stellt man N = 2 ein, lauten die fünf Klassen 1, 1, 2, 2 und 4 — kaum voneinander zu unterscheiden. Die von der Notation garantierte Reihenfolge zeigt sich erst, wenn N groß ist. So kann ein O(N²)-Verfahren mit einer kleinen Konstanten ein O(N log N)-Verfahren bei jeder Eingabe schlagen, die man in der Praxis tatsächlich jemals hat.

Wenn Wachstum jede Optimierung überholt 🖖

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.

Der Verdopplungstest 🖖

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.

Wenn die schnellere Klasse verliert 🖖

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.

Aufgabe vollständig gelöst

Wo sich die Kluft zwischen N log N und N ² auftut 5 Schritte
Bei N = 100 zeigt das Feld 664 für N log N und 10 000 für N² an. Das ist nur ein Faktor von fünfzehn – kaum der Abgrund, den Komplexitätsklassen eigentlich darstellen sollen. Finden Sie heraus, wo sich der Abgrund tatsächlich auftut.
1. Beginnen Sie mit den beiden Zahlen. log₂ 100 ist 6,6439, also ist N log₂ N gleich 664 und N² gleich 10 000.
  
  $N lo g_{2} N = 100 \times 6.6439 = 664, N^{2} = 10000$
2. Das Verhältnis zwischen ihnen ist keine Konstante, und genau darum geht es bei Komplexitätsklassen. Teilt man, kürzt sich N einmal heraus und es bleibt N/log N – eine Größe, die unbeschränkt wächst, nur langsam.
3. Bei N = 100 beträgt es 15,1. Das ist zwar spürbar, aber unbeeindruckend: Eine 15-fache Beschleunigung ist etwas, das ein besserer konstanter Faktor bewirken könnte – genau deshalb führen Benchmarks mit kleinen Eingaben in die Irre.
  
  $\frac{N ^{2}}{N lo g _{2} N} = \frac{N}{lo g _{2} N} = \frac{100}{6.6439} = 15.1$
4. Setzen Sie nun eine Million ein. Der Logarithmus hat sich kaum bewegt – von 6,6 auf 19,9, ein Faktor von drei –, während N um das Zehntausendfache gewachsen ist. Das Verhältnis beträgt nun 50 172.
  
  $N = 1 0^{6} : \frac{N}{lo g _{2} N} = \frac{1 0 ^{6}}{19.93} = 50172$
5. Und es kehrt sich nie wieder um. Die Ableitung von N/log N ist für jedes N größer als e positiv, sodass keine Eingabegröße existiert, ab der der quadratische Algorithmus wieder aufholt.
  
  $\frac{d}{d N} (\frac{N}{lo g _{2} N}) > 0 for N > e ⟹ the gap only widens$
Antwort

Das Werkzeug gibt 664 gegenüber 10 000 bei N = 100 aus. Die Zahl, die man sich merken sollte, ist die andere: Bei einer Million sind dieselben zwei Kurven um 50 172 voneinander entfernt. Komplexitätsklassen sind keine Aussagen über einhundert Elemente, und sie dort zu vergleichen ist der klassische Weg, sich für den falschen Algorithmus zu entscheiden – eine 15-fache Lücke sieht nach etwas aus, das eine schnellere Programmiersprache schließen könnte. Schieben Sie den Regler nach oben und beobachten Sie, wie das Verhältnis mitsteigt. Das ist auch der Grund, warum der Logarithmus in der Praxis so oft ignoriert wird: Er wuchs um den Faktor drei, während die Eingabe um das Zehntausendfache wuchs.

$\frac{N ^{2}}{N lo g N} = \frac{N}{lo g N} : 15 \times at 100, 50172 \times at 1 0^{6}$

Lernpfad

Arbeit zählen, nicht Sekunden

Führt zu sorting-race

Quellen (1)

The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.

Vom 42Math-Team · Aktualisiert 2026-06-10

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

Klein N=20 - Alle Kurven bei N=20
N=1000 - N=1000: polynomiale Kurven divergieren
Log-Skala - Logarithmische Skala macht Wachstumsunterschiede sichtbar
Verborgene Konstanten - Mit c=50 schneiden sich 50N log N und N² nahe N=439