Big O-Notation: Der ultimative Interview-Leitfaden

2. März 2026

performance algorithmen typescript interview-vorbereitung informatik

In this article

1. Das Kernkonzept: Worst-Case-Analyse
2. Gängige Komplexitäten (Rangfolge)
3. Speicherkomplexität: Der stille Killer
4. Big O berechnen wie ein Profi
Regel 1: Konstanten weglassen
Regel 2: Nicht-dominante Terme weglassen
Regel 3: Verschiedene Eingaben, verschiedene Variablen
5. Datenstrukturen Cheat Sheet
6. Die BUD-Methode zur Optimierung
7. Praktische Implementierung: Duplikate finden
Suboptimaler Ansatz (O(n²) Zeit, O(1) Speicher)
Optimaler Ansatz (O(n) Zeit, O(n) Speicher)
8. Interview-Strategie: Komplexität kommunizieren
9. Zusammenfassung

In technischen Interviews ist die Big O-Notation die wichtigste Sprache, um Ihre Fähigkeit zu bewerten, skalierbaren Code zu schreiben. Es geht nicht nur um Mathematik, sondern darum, Abwägungen zwischen Geschwindigkeit und Speicher zu treffen. Dieser Leitfaden deckt alles ab, was Sie wissen müssen, um souverän in Ihr nächstes Interview zu gehen.

1. Das Kernkonzept: Worst-Case-Analyse

Die Big O-Notation beschreibt die obere Schranke der Wachstumsrate eines Algorithmus. Während wir oft den “Average Case” erwähnen, interessieren sich Interviewer fast immer für das Worst-Case-Szenario.

Zeitkomplexität: Wie viele Operationen führt der Algorithmus aus, wenn $n$ wächst?
Speicherkomplexität: Wie viel zusätzlichen Speicher (RAM) verbraucht der Algorithmus im Verhältnis zu $n$ ?

Big O Komplexitätsdiagramm mit O(1), O(log n), O(n), O(n log n), O(n^2) und O(2^n)

2. Gängige Komplexitäten (Rangfolge)

Notation	Name	Geschwindigkeit	Praxisbeispiel
$O(1)$	Konstant	Exzellent	Zugriff auf einen Array-Index oder einen Hash Map-Schlüssel.
$O(\log n)$	Logarithmisch	Großartig	Binäre Suche in einer sortierten Sammlung.
$O(n)$	Linear	Gut	Finden des maximalen Elements in einer unsortierten Liste.
$O(n \log n)$	Linearithemisch	Akzeptabel	Die effizientesten Sortieralgorithmen (Merge Sort).
$O(n^2)$	Quadratisch	Schwach	Verschachtelte Schleifen (Überprüfung jedes Paares in einer Liste).
$O(2^n)$	Exponentiell	Schrecklich	Rekursives Fibonacci oder Generierung einer Potenzmenge.
$O(n!)$	Faktoriell	Katastrophal	Lösung des Problems des Handlungsreisenden mittels Brute-Force.

3. Speicherkomplexität: Der stille Killer

Interviewer “warten” oft darauf, dass Sie den Speicherbedarf erwähnen. Wenn Sie die Zeit durch Verwendung einer Hash Map optimieren, tauschen Sie Speicher gegen Zeit.

$O(1)$ Speicher: Sie verwenden nur wenige Variablen, unabhängig von der Eingabegröße.
$O(n)$ Speicher: Sie erstellen ein neues Array oder eine Map der Größe $n$ .
$O(\log n)$ Speicher: Häufig bei rekursiven Aufrufen (Tiefe des Call Stacks).

4. Big O berechnen wie ein Profi

Befolgen Sie diese drei Regeln während Ihrer Whiteboard-Session:

Regel 1: Konstanten weglassen

$O(n + 100)$ ist einfach $O(n)$ . $O(2n)$ ist einfach $O(n)$ . Konzentrieren Sie sich auf den Trend, nicht auf die exakte Anzahl.

Regel 2: Nicht-dominante Terme weglassen

In $O(n^2 + n)$ wächst der $n^2$ -Term so viel schneller, dass das $n$ irrelevant wird.

$O(n^2 + 500n + \log n) \rightarrow O(n^2)$

Regel 3: Verschiedene Eingaben, verschiedene Variablen

Wenn Ihre Funktion zwei verschiedene Listen verarbeitet, gehen Sie nicht davon aus, dass sie die gleiche Größe haben.

listA und listB $\rightarrow O(a + b)$ oder $O(a \times b)$ , wenn verschachtelt.

5. Datenstrukturen Cheat Sheet

Prägen Sie sich diese für $O(1)$ - vs. $O(n)$ -Entscheidungen ein. Vertiefende Informationen und Implementierungen finden Sie in unserem Leitfaden für Datenstrukturen.

Datenstruktur	Zugriff	Suche	Einfügen	Löschen
Array	$O(1)$	$O(n)$	$O(n)$	$O(n)$
Hash Map / Set	n/a	$O(1)$	$O(1)$	$O(1)$
Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Stack / Queue	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Binary Search Tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
Graph	n.v.	$O(V+E)$	$O(1)$	$O(1)$

6. Die BUD-Methode zur Optimierung

Wenn ein Interviewer fragt: “Können wir es besser machen als $O(n^2)$ ?”, nutzen Sie BUD:

Bottlenecks (Engpässe): Welcher Teil dauert am längsten? (z. B. ein verstecktes indexOf innerhalb einer Schleife).
Unnecessary Work (Unnötige Arbeit): Verarbeiten Sie Elemente, die Sie nicht benötigen?
Duplicated Work (Doppelte Arbeit): Berechnen Sie Werte mehrfach? (Nutzen Sie Memoization).

7. Praktische Implementierung: Duplikate finden

Suboptimaler Ansatz (O(n²) Zeit, O(1) Speicher)

function hasDuplicates(arr: number[]): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true; // Verschachtelte Schleife!
    }
  }
  return false;
}

Optimaler Ansatz (O(n) Zeit, O(n) Speicher)

Wir tauschen Speicher (das Set) gegen eine deutlich schnellere Ausführung.

function hasDuplicatesOptimized(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const num of arr) {
    if (seen.has(num)) return true; // Set-Lookup ist O(1)
    seen.add(num);
  }
  return false;
}

8. Interview-Strategie: Komplexität kommunizieren

Nennen Sie nicht nur das Ergebnis. Erklären Sie das “Warum”:

Nennen Sie die Komplexität sofort, nachdem Sie Ihre Lösung geschrieben haben.
Schlüsseln Sie es auf: “Die äußere Schleife läuft $n$ -mal, und darin machen wir einen Set-Lookup, der $O(1)$ ist, was zu einer Gesamtzeit von $O(n)$ führt.”
Erwähnen Sie den Speicher: “Da wir Elemente in einem Set speichern, beträgt die Speicherkomplexität $O(n)$ im Worst-Case, wenn alle Elemente eindeutig sind.”
Diskutieren Sie Abwägungen: “Ich habe $O(n)$ Zeit gegenüber $O(n^2)$ gewählt, da wir Eingaben mit hohem Verkehrsaufkommen erwarten. Wäre der Speicher jedoch extrem begrenzt, könnten wir eine vorherige Sortierung in Betracht ziehen ( $O(n \log n)$ Zeit, $O(1)$ Speicher).“

9. Zusammenfassung

Bei Big O geht es nicht darum, ein Mathe-Genie zu sein; es geht darum, ein Optimierungs-Architekt zu sein. Suchen Sie immer nach Wegen, von $O(n^2)$ zu $O(n \log n)$ oder $O(n)$ zu gelangen, und seien Sie bereit, die Kosten des Speichers zu erklären, den Sie dafür einsetzen.