O-Notation: Warum ist O(n log n) so viel besser als O(n²) – und wie lese ich das aus Code ab?

Hi,

in Algorithmen und Datenstrukturen sind wir jetzt bei der Laufzeitanalyse. Ich kann die Liste auswendig (O(1), O(log n), O(n), O(n log n), O(n²)), aber ehrlich gesagt verstehe ich nicht, warum man sich darüber so aufregt. Computer sind doch schnell?

Und in der Übung sollen wir bei Code-Schnipseln die Komplexität bestimmen. Bei einer Schleife ist klar O(n), aber sobald Funktionen aufgerufen werden oder die Schleife „halbiert“, bin ich raus. Gibt es da ein System, oder muss man das einfach sehen? 😅

Die O-Notation beschreibt nicht, wie schnell ein Programm ist, sondern wie die Laufzeit wächst, wenn die Eingabe größer wird. Deshalb fallen Konstanten weg: Ob eine Schleife 3 oder 5 Befehle pro Durchlauf hat, ändert am Wachstum nichts.

Warum das auch bei schnellen Computern zählt – Beispiel mit n = 1.000.000 Datensätzen und grob 10⁹ einfachen Operationen pro Sekunde:

• O(n log n): 1.000.000 · ca. 20 = 20 Millionen Schritte → etwa 0,02 Sekunden
• O(n²): 10¹² Schritte → rund 1.000 Sekunden, also über eine Viertelstunde

Und verdoppelst du n, wird O(n²) viermal so langsam, O(n log n) nur gut doppelt so langsam. Ein schnellerer Rechner verschiebt das Problem nur, das Wachstum bleibt.

Das System zum Ablesen:

1. Einzelne Anweisungen ohne Schleife: O(1).
2. Hintereinander stehende Teile: addieren, der größte Term gewinnt. O(n) + O(n²) = O(n²).
3. Verschachtelte Schleifen: multiplizieren. Äußere läuft n-mal, innere n-mal → O(n²).
4. Schleife, die den Bereich jedes Mal halbiert (z. B. i = i / 2 oder binäre Suche): O(log n). Frage dich: Wie oft kann ich n halbieren, bis 1 übrig ist? Genau log₂ n mal – bei einer Million sind das nur ca. 20.
5. Funktionsaufrufe nicht als 1 zählen, sondern die Kosten der Funktion einsetzen. Ein contains auf einer Liste in einer Schleife ist schon O(n) · O(n).

Merksatz: Nacheinander → addieren, ineinander → multiplizieren, halbieren → log.

Ein Praxisbeispiel, weil genau das im Job ständig passiert: Dubletten in einer Kundenliste finden.

• Naiv: jeden Eintrag mit jedem anderen vergleichen → zwei verschachtelte Schleifen → O(n²). Mit 500 Testdaten merkt man nichts, mit 2 Millionen Kunden im Produktivsystem läuft der Job über Nacht.
• Sortieren, dann Nachbarn vergleichen: Sortieren kostet O(n log n), der Durchlauf danach O(n) → insgesamt O(n log n).
• Mit Hash-Set: jeden Eintrag einmal nachschlagen/einfügen, im Schnitt O(1) → insgesamt O(n), dafür mehr Speicher.

Das zeigt auch den typischen Trade-off: Zeit gegen Speicher. Und es zeigt, warum die Wahl der Datenstruktur oft wichtiger ist als Mikrooptimierung im Code.

Für die Übung noch ein Hinweis: Achte darauf, ob nach Worst Case oder Durchschnitt gefragt ist. Quicksort ist im Schnitt O(n log n), im schlechtesten Fall aber O(n²). Das wird in Klausuren gern abgefragt.