Big-O-Notation und Laufzeitkomplexität: Leitfaden mit Übungen

Die Big-O-Notation beschreibt, wie Laufzeit oder Speicherbedarf eines Algorithmus mit der Eingabegröße wachsen. Sie beantwortet nicht die Frage „Wie viele Sekunden braucht dieser Code?“, sondern „Wie viel mehr Arbeit entsteht, wenn sich die Eingabe verdoppelt?“. In Klausuren zu Algorithmen und Datenstrukturen begegnet sie Ihnen in zwei Formen: „Bestimmen Sie die Komplexität dieses Codes“ und „Vergleichen Sie diese beiden Algorithmen“. Dieser Leitfaden liefert zuerst die Intuition, dann die exakte Definition, danach die Analyse von Schleifen und Rekursion und zum Schluss Übungen mit Lösungen.

Die Beispiele sind in C# geschrieben; wenn Ihnen die Syntax neu ist, genügt der Beitrag zu Klassen und Objekten in C# als Einstieg, die Schleifen sehen aber in fast jeder Sprache gleich aus.

Intuition: Wir messen Wachstum, nicht Sekunden

Derselbe Code läuft auf verschiedenen Rechnern unterschiedlich schnell; wer Sekunden zählt, misst die Maschine und nicht den Algorithmus. Stattdessen schreiben wir die Zahl der Elementaroperationen als Funktion der Eingabegröße n. Angenommen, ein Code führt 3n² + 5n + 2 Operationen aus. Für n = 1000 beträgt der Term 3n² genau 3.000.000, der Term 5n nur 5.000: Bei großem n bestimmt n² das Bild. Auch der konstante Faktor 3 hängt von Maschine und Compiler ab. Beides lassen wir weg und sagen: „Dieser Algorithmus ist O(n²).“

Die exakte Definition und der Unterschied zwischen O, Ω und Θ

f(n) = O(g(n)) bedeutet: Es gibt Konstanten c > 0 und n₀, sodass f(n) ≤ c·g(n) für alle n ≥ n₀ gilt. Im Beispiel oben funktionieren c = 4 und n₀ = 6: Für n ≥ 6 ist 5n + 2 ≤ n², also 3n² + 5n + 2 ≤ 4n².

• O (Groß-O) ist eine obere Schranke: „wächst höchstens so schnell“.
• Ω (Omega) ist eine untere Schranke: „wächst mindestens so schnell“.
• Θ (Theta) ist beides zugleich: „wächst genau so schnell“.

Ein wichtiges Detail: 3n² + 5n + 2 ist auch O(n³); das stimmt, ist aber eine grobe Schranke. In der Klausur wird die scharfe Schranke erwartet, also eigentlich Θ; im Alltag nennt man auch das „Big O“. Die drei Symbole sind unabhängig von Best Case und Worst Case; auf diese Verwechslung komme ich bei den Fehlern zurück.

Gängige Komplexitätsklassen

Von langsam zu schnell wachsend: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

// O(1): unabhängig von der Eingabegröße
static int First(int[] a) => a[0];

// O(log n): der Bereich halbiert sich in jedem Schritt (Array muss sortiert sein)
static int BinarySearch(int[] a, int target)
{
    int low = 0, high = a.Length - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

// O(n): jedes Element wird einmal besucht
static long Sum(int[] a)
{
    long total = 0;
    foreach (int x in a) total += x;
    return total;
}

// O(n²): jedes Paar wird geprüft
static int CountEqualPairs(int[] a)
{
    int count = 0;
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) count++;
    return count;
}

// O(2ⁿ): jeder Aufruf erzeugt zwei weitere Aufrufe
static long Fib(int n) => n < 2 ? n : Fib(n - 1) + Fib(n - 2);

Das typische Beispiel für O(n log n) ist Merge Sort; den Ablauf und den Vergleich mit den anderen Sortierverfahren finden Sie im Beitrag Sortieralgorithmen: Prüfungsfragen mit Lösungsweg.

Schleifen analysieren

Vier Regeln decken den größten Teil der Arbeit ab:

1. Aufeinanderfolgende Blöcke werden addiert: O(n) + O(n²) = O(n²).
2. Verschachtelte Schleifen werden multipliziert, aber nur, wenn die Durchlaufzahl der inneren Schleife nicht von der äußeren abhängt: n × m Durchläufe.
3. Wird der Zähler multipliziert oder dividiert (i *= 2, i /= 2), läuft die Schleife log₂ n-mal.
4. Hängt die innere Schleife vom äußeren Zähler ab (j < i), wird summiert statt multipliziert: 0 + 1 + ... + (n−1) = n(n−1)/2, also O(n²).

Bei Regel vier passieren die meisten Fehler. Eine abhängige Schleife ergibt manchmal weniger als n²: siehe Übung 3 und 7.

Rekursion: linear, binär und Teile-und-herrsche

Bei rekursivem Code stellen wir zwei Fragen: Wie viele Aufrufe gibt es, und wie viel Arbeit leistet jeder Aufruf für sich?

// Lineare Rekursion: n Aufrufe, je O(1) -> O(n)
static long SumTo(int n) => n == 0 ? 0 : n + SumTo(n - 1);

// Teile und herrsche: zwei halb so große Probleme + O(n) Mischen
static void MergeSort(int[] a, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);       // T(n/2)
    MergeSort(a, mid + 1, right);  // T(n/2)
    Merge(a, left, mid, right);    // O(n)
}

Für SumTo gilt T(n) = T(n−1) + O(1): Die Kette hat n Glieder, also O(n). Das obige Fib ist binäre Rekursion: T(n) = T(n−1) + T(n−2) + O(1). Der Aufrufbaum verdoppelt sich pro Ebene höchstens und hat die Tiefe n, die obere Schranke O(2ⁿ) gilt also (die scharfe Schranke liegt bei etwa 1,618ⁿ; in Klausuren wird meist O(2ⁿ) akzeptiert).

Bei Merge Sort ist T(n) = 2T(n/2) + O(n). Ohne schwere Mathematik lässt sich das so sehen: Auf der obersten Ebene kostet das Mischen n. Eine Ebene tiefer gibt es zwei Teile der Größe n/2, zusammen wieder n. Jede Ebene kostet insgesamt n, und bis die Teile auf ein Element geschrumpft sind, entstehen log₂ n Ebenen. Ergebnis: n × log n = O(n log n). Die Methode Merge selbst steht im Sortierbeitrag.

Das Werkzeug, das solche Rekursionsgleichungen mechanisch löst, ist das Master-Theorem: Für T(n) = a·T(n/b) + f(n) vergleicht man f(n) mit n^(log_b a). Merge Sort hat a = 2, b = 2, also n^(log₂ 2) = n; f(n) = Θ(n) hat dieselbe Größenordnung, es gilt Fall zwei und T(n) = Θ(n log n). Die rekursive binäre Suche hat a = 1, b = 2, f(n) = Θ(1): n^(log₂ 1) = 1, wieder Fall zwei, T(n) = Θ(log n).

Speicherkomplexität

Dieselbe Notation gilt für den Zusatzspeicher; die Eingabe selbst zählt in der Regel nicht mit. Übersehen wird meist die Rekursion: Jeder aktive Aufruf belegt Platz auf dem Stack. SumTo(n) sieht aus, als bräuchte es eine einzige Variable, die n verschachtelten Aufrufe kosten aber O(n) Speicher, und bei großem n endet das Programm mit einer StackOverflowException. Als Schleife geschrieben sinkt der Bedarf auf O(1). Merge Sort nutzt ein Hilfsarray der Größe O(n); Fib(n) läuft zwar exponentiell lange, es sind aber höchstens n Aufrufe gleichzeitig aktiv, der Speicherbedarf ist also O(n).

Übungen: Welche Komplexität hat dieser Code?

Lösen Sie die Aufgaben zuerst selbst und vergleichen Sie dann.

// 1
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

// 2
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < n; j++)
        count++;

// 3
for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;

// 4
for (int i = 0; i < n; i++) count++;
for (int j = 0; j < m; j++) count++;
for (int k = 0; k < n; k++)
    for (int t = 0; t < 100; t++)
        count++;

// 5
int s = 0;
while (s * s < n) s++;

// 6
static int F(int n)
{
    if (n <= 0) return 1;
    return F(n - 1) + F(n - 1);
}

// 7
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        count++;

// 8
static int Search(int[] a, int target, int low, int high)
{
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == target) return mid;
    return a[mid] < target
        ? Search(a, target, mid + 1, high)
        : Search(a, target, low, mid - 1);
}

Lösungen:

1. Die innere Schleife läuft i-mal: 0 + 1 + ... + (n−1) = n(n−1)/2. O(n²). Für n = 16 sind das genau 120 Durchläufe.
2. Die äußere Schleife läuft log₂ n-mal, die innere jeweils n-mal: O(n log n). Für n = 16: 4 × 16 = 64.
3. Die innere Schleife hängt von der äußeren ab: n + n/2 + n/4 + ... + 1 < 2n. O(n). „Außen log n, innen n, also n log n“ ist hier die Falle; für n = 1024 steht der Zähler am Ende bei 2047, nicht bei 10.240.
4. n + m + 100n. Die Konstante 100 entfällt; n und m sind unabhängige Eingaben, beide bleiben stehen: O(n + m).
5. Die Schleife endet, sobald s den Wert √n erreicht: O(√n).
6. Jeder Aufruf erzeugt zwei Aufrufe, Tiefe n: insgesamt 2ⁿ⁺¹ − 1 Aufrufe, Laufzeit O(2ⁿ). Der Speicherbedarf ist O(n), weil immer nur ein Ast aktiv ist. Als 2 * F(n - 1) geschrieben ließe sich dasselbe Ergebnis in O(n) berechnen.
7. Die innere Schleife läuft etwa n/i-mal: n/1 + n/2 + ... + n/n = n × (1 + 1/2 + ... + 1/n). Die Klammer ist die harmonische Reihe, ungefähr ln n: O(n log n).
8. Der Bereich halbiert sich mit jedem Aufruf: T(n) = T(n/2) + O(1), Laufzeit O(log n). Die rekursive Variante braucht auch O(log n) Speicher; das iterative BinarySearch von oben erledigt dieselbe Arbeit mit O(1) Speicher.

Ein kleines Szenario: Duplikate erkennen

Stellen Sie sich ein Anmeldeformular vor, bei dem geprüft werden muss, ob eine Liste eingehender Nummern ein Duplikat enthält. Die erste Idee ist, jedes Paar zu vergleichen; die zweite, bereits gesehene Werte in einem HashSet zu halten.

static bool HasDuplicateSlow(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

static bool HasDuplicateFast(int[] a)
{
    var seen = new HashSet<int>();
    foreach (int x in a)
        if (!seen.Add(x)) return true; // Add liefert false, wenn das Element schon vorhanden ist
    return false;
}

Die erste Variante braucht O(n²) Zeit und O(1) Speicher, die zweite im Mittel O(n) Zeit und O(n) Speicher. Das ist ein typischer Tausch von Zeit gegen Speicher: Geschwindigkeit wird mit zusätzlichem Speicher bezahlt. Der Best Case ist bei beiden gleich (sind die ersten beiden Elemente gleich, kehren beide sofort zurück); der Unterschied zeigt sich im Worst Case, wenn es gar kein Duplikat gibt.

Wann verwenden – und wann nicht?

Big O zahlt sich aus, wenn die Eingabe wachsen kann und Sie zwischen zwei Ansätzen wählen: Kann n in die Millionen gehen, ist der Unterschied zwischen O(n²) und O(n log n) der Unterschied zwischen Code, der funktioniert, und Code, der es nicht tut. Auch die Wahl einer Datenstruktur beruht auf dieser Analyse; ein binärer Suchbaum etwa sucht in O(log n), solange er balanciert ist, und in O(n), sobald er entartet.

Es gibt Fälle, in denen die Notation allein nicht reicht. Bei kleinem, beschränktem n (eine Menüliste mit zehn Einträgen) entscheiden die konstanten Faktoren; ein Insertion Sort mit O(n²) kann einen Merge Sort mit O(n log n) schlagen. Auch beim Vergleich zweier Algorithmen derselben Klasse sagt die Notation nichts aus. Die Alternative ist dann das Messen: mit Stopwatch oder einer Benchmark-Bibliothek auf echten Daten. Big O sagt Ihnen, was zu messen ist; die Messung ersetzt es nicht.

Häufige Fehler

1. Den falschen Term streichen. In O(n² + n log n) dominiert n², also entfällt n log n. In O(n + m) darf m dagegen nicht entfallen: Es ist eine eigene Eingabe und kann größer als n sein. Ebenso ist O(2n) oder O(n/2) ein Notationsfehler; beides ist O(n). Auch die Basis des Logarithmus ist ein konstanter Faktor: O(log₂ n) und O(log₁₀ n) sind dieselbe Klasse.

2. Best Case mit Ω verwechseln. Best, Average und Worst Case beschreiben, welche Eingabe betrachtet wird; O, Ω und Θ beschreiben, welche Art von Schranke man für die Funktion dieses Falls angibt. Der Best Case von Insertion Sort ist Θ(n), der Worst Case Θ(n²). Der Satz „Insertion Sort ist Ω(n)“ stimmt, bedeutet aber nicht „Best Case“; er sagt, dass jede Eingabe mindestens n Operationen kostet.

3. Zwei Schleifen sehen und n² sagen. Zwei Schleifen hintereinander sind O(n). Selbst verschachtelte Schleifen können n log n oder n ergeben, wie die Übungen 2, 3 und 7 zeigen. Zählen Sie nicht die Schleifen, sondern berechnen Sie, wie oft der innerste Rumpf insgesamt läuft.

4. Versteckte Kosten übersehen. Eine in der Schleife aufgerufene Methode muss nicht O(1) sein:

for (int i = 0; i < list.Count; i++)
    if (list.Contains(target - list[i])) return true; // Contains ist O(n) -> insgesamt O(n²)

List<T>.Contains sucht linear; dieser Code sieht nach einer Schleife aus, ist aber O(n²). Mit einem HashSet<T> sinkt der Aufwand im Mittel auf O(n).

Wenn Sie solche Aufgaben an den Altklausuren Ihrer eigenen Vorlesung üben möchten, finden Sie Näheres auf der Seite zur Prüfungsvorbereitung.

Häufig gestellte Fragen

Beschreibt Big O immer den Worst Case?

Nein. Big O ist eine Notation für obere Schranken und lässt sich auf Best, Average und Worst Case anwenden. In der Praxis wird sie meist für den Worst Case benutzt, daher die Verwechslung.

Welche Basis hat der Logarithmus in O(n log n)?

Meist 2, weil er aus wiederholtem Halbieren stammt, für die Notation spielt das aber keine Rolle. Verschiedene Basen unterscheiden sich nur um einen konstanten Faktor, und konstante Faktoren entfallen bei Big O.

Lässt sich das Master-Theorem auf jede Rekursionsgleichung anwenden?

Nein, nur auf Teile-und-herrsche-Gleichungen der Form T(n) = a·T(n/b) + f(n). Für Gleichungen, die das Problem durch Subtraktion verkleinern, etwa T(n) = T(n−1) + O(1) oder Fibonacci, verwendet man die Aufrufkette oder die Rekursionsbaum-Methode.

Was ist wichtiger, Laufzeit- oder Speicherkomplexität?

Das hängt vom Fall ab. Klausuren und die meisten Anwendungen fragen zuerst nach der Laufzeit; ist der Speicher knapp oder die Rekursionstiefe groß, wird der Speicher entscheidend. Eine gute Antwort nennt beides.