andblackcheck
Big-O Cheat Sheet
DATENSTRUKTUREN & ZEITKOMPLEXITÄT · DSA-GRUNDLAGEN · INTERVIEW-VORBEREITUNG
Quelle: Instagram — algomasterio ↗
Kernidee: Diese Tabelle ist der Spickzettel für Algorithmen-Interviews und System-Design: Sie zeigt, wie schnell die 4 wichtigsten Operationen (Access, Search, Insert, Delete) auf 8 gängigen Datenstrukturen sind — gemessen in Big-O. Wer die Auswahl der Datenstruktur an den Bedarf koppelt („oft lesen? oft einfügen?"), schreibt effizientere Programme.
Basics: Was bedeutet Big-O?
Big-O beschreibt, wie die Laufzeit eines Algorithmus wächst, wenn die Eingabemenge n größer wird — also die „Wachstumsordnung", nicht die exakte Zeit:
- O(1) — konstante Zeit: egal wie groß die Daten, immer gleich schnell (z. B. Array-Zugriff per Index).
- O(log n) — logarithmisch: wächst sehr langsam, verdoppeln der Daten = nur +1 Schritt (z. B. balancierte Baum-Suche).
- O(n) — linear: doppelte Daten = doppelte Zeit (z. B. einmal alles durchsuchen).
- O(n log n), O(n²), … — noch langsamer (Sortieren, verschachtelte Schleifen).
Faustregel für die Reihenfolge (schnell → langsam): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Für Interviews gilt: Die Datenstruktur bestimmt oft, welche Operationen schnell sind — man kann nicht alles gleichzeitig schnell haben.
Die 8 Datenstrukturen — Zeitkomplexität
| Struktur | Access | Search | Insert | Delete | Hinweis |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | blitzschneller Index-Zugriff; Einfügen/Löschen schiebt alles um |
| Linked List | O(n) | O(n) | O(1) | O(1) | am Kopf O(1); sonst durchlaufen |
| Stack (LIFO) | O(1) | O(n) | O(1) | O(1) | nur Spitze: push/pop O(1) |
| Queue (FIFO) | O(1) | O(n) | O(1) | O(1) | nur vorne/hinten: enqueue/dequeue O(1) |
| Hash Map | O(1)* | O(1)* | O(1)* | O(1)* | * Average Case; Kollisionen = O(n) |
| BST (balanciert) | O(log n) | O(log n) | O(log n) | O(log n) | balanciert; sonst entartet zu O(n) |
| Heap (Min-Heap) | O(1) | O(n) | O(log n) | O(log n) | peek min O(1); sift up/down O(log n) |
| Trie | O(L) | O(L) | O(L) | O(L) | L = Schlüssellänge; für Präfix-Suche/Wörterbücher |
Wahl-Hilfe nach Use-Case: Häufig per Index lesen → Array · häufig am Anfang einfügen/löschen → Linked List · LIFO (rückgängig, Klammern) → Stack · FIFO (Warteschlange) → Queue · schnelle Key-Suche (Cache, Lookups) → Hash Map · geordnete Suche / Stichwort → BST · immer das Min/Max holen (Prioritätswarteschlange) → Heap · Präfix-/Wortsuche (Autocomplete) → Trie. Wichtig: Manche dieser Werte gelten für „average/optimal" — z. B. Hash-Map sollt mit guter Hashfunktion eingesetzt werden.
Selbsttest
- Welche Datenstruktur hat O(1)-Access per Index? (Array)
- Was bedeutet O(1)? (Konstante Zeit — unabhängig von der Datenmenge)
- Welche Struktur eignet sich für „immer das Minimum holen"? (Heap — peek min O(1))
- Wofür steht das Sternchen bei der Hash Map? (Average Case; bei Kollisionen kann es O(n) werden)
- Warum sind O(1) < O(log n) < O(n)? (Reihenfolge des Wachstums: konstant am schnellsten, dann logarithmisch, dann linear)