Big-O-Notation verstehen: Eine Schritt-für-Schritt-Anleitung mit aktuellen Beispielen (Mai 2026)

Einführung in die Big-O-Notation

Die Big-O-Notation ist ein fundamentales Werkzeug der Informatik, um die Effizienz von Algorithmen zu beschreiben. Sie gibt an, wie die Laufzeit oder der Speicherverbrauch eines Algorithmus mit der Größe der Eingabe wächst. In diesem Tutorial lernst du, wie man Funktionen nach ihrer Wachstumsrate ordnet – ein häufiges Thema in Kursen wie CSCI 570 oder vergleichbaren Algorithmen-Vorlesungen. Wir verwenden aktuelle Beispiele aus dem Jahr 2026, um die Konzepte greifbar zu machen.

Was bedeutet Big-O genau?

Formal sagt man: f(n) = O(g(n)), wenn es positive Konstanten c und n₀ gibt, so dass für alle n ≥ n₀ gilt: f(n) ≤ c · g(n). Intuitiv bedeutet das: g(n) ist eine obere Schranke für das Wachstum von f(n). Je kleiner die Wachstumsrate, desto effizienter ist der Algorithmus für große Eingaben.

Wichtige Funktionen und ihre Wachstumsraten

Betrachten wir typische Funktionen, die in Aufgaben wie „Ordnen Sie diese Funktionen unter Big-O in aufsteigender Reihenfolge“ vorkommen:

• Konstant: O(1) – unabhängig von n, z.B. Zugriff auf Array-Element.
• Logarithmisch: O(log n) – z.B. binäre Suche.
• Linear: O(n) – einfache Schleife.
• Linearithmisch: O(n log n) – effiziente Sortieralgorithmen wie Merge Sort.
• Quadratisch: O(n²) – verschachtelte Schleifen.
• Exponentiell: O(2ⁿ) – viele Backtracking-Probleme.
• Faktoriell: O(n!) – Permutationen.

Schritt-für-Schritt: Funktionen ordnen

Angenommen, wir haben folgende Funktionen (ähnlich wie in der Aufgabe): 2 log(n), 2^(3n), 3^(2n), n^(n log(n)), log(n), n log(n²), n^(n²), log(n!), log(log(nⁿ)). Wir wollen sie in aufsteigender Reihenfolge der Wachstumsrate ordnen.

1. Vereinfachen der Ausdrücke

• 2 log(n) = O(log n), da konstante Faktoren ignoriert werden.
• log(n) bleibt O(log n).
• log(log(nⁿ)): nⁿ ist riesig, aber der Logarithmus macht es klein: log(log(nⁿ)) = log(n log n) = log n + log log n = O(log n).
• n log(n²) = n · 2 log n = 2 n log n = O(n log n).
• log(n!): Nach der Stirling-Approximation: log(n!) ≈ n log n - n + O(log n) = O(n log n).
• 2^(3n) = (2³)ⁿ = 8ⁿ und 3^(2n) = (3²)ⁿ = 9ⁿ. Beide sind exponentiell, aber 9ⁿ wächst schneller als 8ⁿ.
• n^(n log n): n^(n log n) = e^(n log n · log n) = e^(n (log n)²). Das wächst schneller als jede Exponentialfunktion mit konstanter Basis, aber langsamer als n^(n²).
• n^(n²) = e^(n² log n) – das ist extrem schnell wachsend.

2. Sortieren nach Wachstumsrate

Die korrekte Reihenfolge (von langsam nach schnell) ist:

1. log(n), 2 log(n), log(log(nⁿ)) – alle O(log n).
2. n log(n²) und log(n!) – beide O(n log n).
3. 2^(3n) – exponentiell.
4. 3^(2n) – exponentiell, aber schneller als 2^(3n).
5. n^(n log n) – super-exponentiell.
6. n^(n²) – am schnellsten.

Wichtig: Innerhalb derselben Klasse (z.B. O(log n)) sind die Funktionen asymptotisch gleich; die Reihenfolge ist nicht eindeutig, aber für die Aufgabe reicht es, sie als Gruppe zu nennen.

Anschauliche Beispiele aus dem Jahr 2026

Stell dir vor, du entwickelst eine KI-gestützte Lern-App, die Schülern hilft, Vokabeln zu lernen. Die Anzahl der Vokabeln sei n. Verschiedene Algorithmen haben unterschiedliche Laufzeiten:

• Logarithmisch (O(log n)): Die App sucht ein Wort in einem sortierten Index – blitzschnell, selbst bei 1 Million Wörtern.
• Linear (O(n)): Die App geht alle Vokabeln durch, um diejenigen zu finden, die du heute lernen sollst – akzeptabel für 1000 Wörter.
• Quadratisch (O(n²)): Die App vergleicht jedes Wort mit jedem anderen, um ähnliche Paare zu finden – bei 10.000 Wörtern wird es langsam.
• Exponentiell (O(2ⁿ)): Die App probiert alle möglichen Kombinationen von Vokabeln für eine Lernsitzung aus – bereits bei 20 Wörtern unmöglich.

Ein weiteres Beispiel: Soziale Medien verwenden Graph-Algorithmen, um Freundschaften zu analysieren. Die Anzahl der Nutzer n wächst rasant. Ein Algorithmus mit O(n log n) skaliert gut, einer mit O(n²) wird bei Millionen Nutzern zum Problem.

Häufige Fehler vermeiden

• Konstanten ignorieren: 2 log n ist immer noch O(log n).
• Logarithmus-Basen: In der Big-O-Notation spielt die Basis keine Rolle, da log_a n = log_b n / log_b a – nur ein konstanter Faktor.
• Nicht verwechseln: n log n ist nicht dasselbe wie log(n!), aber beide sind O(n log n).
• Exponentiell vs. polynomiell: 2ⁿ wächst schneller als jedes Polynom n^k.

Übungsaufgabe zum Selbermachen

Ordne die folgenden Funktionen in aufsteigender Reihenfolge (unter Big-O): n³, 2ⁿ, n!, n log n, log n, n², n. (Lösung: log n, n, n log n, n², n³, 2ⁿ, n!).

Fazit

Die Big-O-Notation ist ein mächtiges Werkzeug, um Algorithmen zu vergleichen. Mit etwas Übung fällt das Ordnen von Funktionen leicht. Denk immer daran: Es geht um das asymptotische Verhalten für große n. Verwende die Vereinfachungen und vergleiche die Wachstumsraten. Viel Erfolg in deinem Kurs!