Big-O-Notation in der Praxis: Laufzeit und Speicher einschätzen

Komplexitätsklassen, versteckte Schleifen, Laufzeiten eingebauter JavaScript-Methoden und der Abgleich mit echten Messungen
Aktualisiert:
Abstract
- #Big O Notation
- #Algorithmen-Analyse
- #Zeitkomplexität
- #Speicherkomplexität
- #Softwareentwicklung
- #JavaScript
- #Datenstrukturen
- #Performance
Warum Code mit 1.000 Datensätzen flott läuft und mit 100.000 stehen bleibt – und wie Sie das vorher erkennen
Angenommen, ein Mittelständler importiert jede Nacht seine Kundendaten aus dem ERP-System in einen Webshop. Ein kleines Skript prüft vorher, ob E-Mail-Adressen doppelt vorkommen. Im Test mit 1.000 Datensätzen dauert das einen Wimpernschlag. Ein Jahr später sind es 200.000 Datensätze, und der Import läuft plötzlich Minuten statt Sekunden. Am Code hat sich nichts geändert, nur an der Datenmenge.
Genau solche Fälle beschreibt die Big-O-Notation. Sie sagt nicht, wie viele Millisekunden ein Programm braucht, sondern wie sein Aufwand wächst, wenn die Eingabe wächst. Wer sie lesen kann, erkennt die Duplikatprüfung aus dem Beispiel schon im Code-Review als Problem – lange bevor sie im Betrieb auffällt. Die folgenden Abschnitte erklären das Konzept mit lauffähigen JavaScript-Beispielen, zeigen die Kosten gängiger eingebauter Methoden und ordnen ein, wo die Notation an ihre Grenzen stößt.
Was die Big-O-Notation aussagt und was nicht
Die Notation beschreibt eine obere Schranke für das Wachstum. Schreibt man, ein Algorithmus liege in O(n), heißt das: Ab einer gewissen Eingabegröße wächst sein Aufwand höchstens proportional zu n. Dabei steht n für die Größe der Eingabe, etwa die Zahl der Datensätze, der Zeichen in einem Text oder der Knoten in einem Graphen. Welche Größe gemeint ist, sollte man immer dazusagen. Bei zwei Listen unterschiedlicher Länge schreibt man sauberer O(n + m) oder O(n · m) statt alles in ein einziges n zu packen.
Zwei Vereinfachungen machen die Notation handlich. Erstens fallen konstante Faktoren weg: Ein Programm, das jedes Element dreimal anfasst, liegt ebenso in O(n) wie eines, das es einmal anfasst. Zweitens zählt nur der am schnellsten wachsende Term. Aus 3n² + 50n + 1.000 wird O(n²), weil bei großen Datenmengen der quadratische Anteil alles andere überdeckt.
Daraus folgt auch, was die Notation nicht leistet. Sie vergleicht keine absoluten Laufzeiten. Ein O(n)-Verfahren mit hohem konstantem Aufwand kann bei kleinen Listen langsamer sein als ein O(n²)-Verfahren mit sehr billigen Einzelschritten. Big O beantwortet die Frage „Was passiert, wenn die Daten zehnmal so groß werden?“, nicht die Frage „Welche Variante ist heute bei 50 Einträgen schneller?“.
Meist betrachtet man den schlimmsten Fall, also die ungünstigste Eingabe einer bestimmten Größe. Daneben gibt es den durchschnittlichen Fall und die amortisierte Betrachtung, auf die ein eigener Abschnitt weiter unten eingeht. Wer über Komplexität spricht, sollte klarstellen, welche dieser Sichten gemeint ist.
Die wichtigsten Komplexitätsklassen an Beispielen
In der Alltagspraxis begegnen Ihnen vor allem sechs Klassen. Die Tabelle zeigt, wie viele Grundschritte grob anfallen, wenn n von tausend auf eine Million steigt:
| Klasse | Bezeichnung | Typisches Beispiel | n = 1.000 | n = 1.000.000 |
|---|---|---|---|---|
| O(1) | konstant | Zugriff auf ein Array-Element per Index | 1 | 1 |
| O(log n) | logarithmisch | binäre Suche in einer sortierten Liste | ca. 10 | ca. 20 |
| O(n) | linear | eine Liste einmal durchlaufen | 1.000 | 1.000.000 |
| O(n log n) | linearithmisch | gute Sortierverfahren | ca. 10.000 | ca. 20 Millionen |
| O(n²) | quadratisch | jedes Element mit jedem anderen vergleichen | 1 Million | 1 Billion |
| O(2ⁿ) | exponentiell | alle Teilmengen einer Menge durchprobieren | nicht machbar | nicht machbar |
Der Sprung zwischen den Zeilen ist der eigentliche Lehrstoff. Eine Billion Vergleiche dauert auch auf schneller Hardware viel zu lange für einen interaktiven Webdienst, während 20 Millionen Schritte für einen Sortiervorgang üblich sind.
Die logarithmische Klasse wirkt am wenigsten anschaulich, ist aber leicht zu verstehen: Jeder Schritt halbiert den Suchraum. Das kennt jeder, der in einem gedruckten Telefonbuch geblättert hat. Im Code sieht das so aus:
function binaereSuche(sortiert, gesucht) {
let links = 0;
let rechts = sortiert.length - 1;
let schritte = 0;
while (links <= rechts) {
schritte++;
const mitte = Math.floor((links + rechts) / 2);
if (sortiert[mitte] === gesucht) return { index: mitte, schritte };
if (sortiert[mitte] < gesucht) links = mitte + 1;
else rechts = mitte - 1;
}
return { index: -1, schritte };
}
// eine Million gerader Kundennummern: 0, 2, 4, …
const kundennummern = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
console.log(binaereSuche(kundennummern, 1_337_000)); // { index: 668500, schritte: 16 }
console.log(binaereSuche(kundennummern, 3)); // { index: -1, schritte: 20 }
Selbst wenn der gesuchte Wert fehlt, sind nach höchstens 20 Schritten alle Möglichkeiten ausgeschlossen, denn 2²⁰ ist etwas mehr als eine Million. Die Voraussetzung ist allerdings eine sortierte Liste. Muss sie dafür erst sortiert werden, kostet das O(n log n). Das lohnt sich nur, wenn danach viele Suchen folgen.
Laufzeit aus dem Code ablesen
Für eine erste Abschätzung genügen wenige Regeln. Einzelne Anweisungen wie Zuweisungen, Vergleiche oder Rechenoperationen gelten als konstant. Eine Schleife über n Elemente multipliziert den Aufwand ihres Rumpfs mit n. Zwei Schleifen hintereinander addieren sich, zwei ineinander verschachtelte multiplizieren sich. Die Duplikatprüfung aus der Einleitung ist das Lehrbuchbeispiel:
// O(n²): jedes Element wird mit allen folgenden verglichen
function hatDuplikateNaiv(liste) {
for (let i = 0; i < liste.length; i++) {
for (let j = i + 1; j < liste.length; j++) {
if (liste[i] === liste[j]) return true;
}
}
return false;
}
// O(n): ein Set merkt sich, was schon vorkam
function hatDuplikate(liste) {
const gesehen = new Set();
for (const wert of liste) {
if (gesehen.has(wert)) return true;
gesehen.add(wert);
}
return false;
}
const emails = ['a@example.com', 'b@example.com', 'a@example.com'];
console.log(hatDuplikateNaiv(emails), hatDuplikate(emails)); // true true
Die zweite Variante tauscht Speicher gegen Zeit: Das Set belegt im schlimmsten Fall Platz für alle n Werte, dafür entfällt die innere Schleife. Wie ein Set intern nachschlägt und warum das im Mittel in konstanter Zeit gelingt, erklärt unser Beitrag zu Dictionaries und Hash Tables in JavaScript.
Die versteckte Schleife
Tückischer sind Fälle, in denen die zweite Schleife gar nicht als Schleife im Code steht. Methoden wie includes(), indexOf() oder find() durchsuchen ein Array von vorn bis hinten. Stehen sie in einem Callback von filter() oder map(), entsteht unauffällig ein quadratisches Verfahren:
const bestellteArtikel = ['A-100', 'B-200', 'C-300', 'D-400'];
const lagerArtikel = ['B-200', 'D-400', 'E-500'];
// O(n · m): includes() durchsucht lagerArtikel bei jedem Aufruf von vorn
const verfuegbarLangsam = bestellteArtikel.filter((nr) =>
lagerArtikel.includes(nr),
);
// O(n + m): einmal ein Set aufbauen, dann in konstanter Zeit nachschlagen
const lager = new Set(lagerArtikel);
const verfuegbar = bestellteArtikel.filter((nr) => lager.has(nr));
console.log(verfuegbarLangsam, verfuegbar); // ['B-200', 'D-400'] ['B-200', 'D-400']
Bei vier und drei Einträgen ist der Unterschied bedeutungslos. Bei 50.000 Bestellpositionen und 20.000 Lagerartikeln sind es eine Milliarde Vergleiche gegen rund 70.000 Schritte. Dasselbe Muster steckt oft in Datenbankzugriffen: Eine Abfrage pro Element einer Liste, das sogenannte N+1-Problem, ist ebenfalls eine versteckte Schleife, nur mit deutlich teureren Einzelschritten.
Was eingebaute JavaScript-Methoden kosten
Wer die Komplexität eigenen Codes abschätzt, muss wissen, was die verwendeten Bausteine kosten. Der ECMAScript-Standard schreibt für Arrays keine Laufzeiten vor, die Angaben unten beschreiben das übliche Verhalten der großen Engines wie V8 in Chrome und Node.js. Für Map und Set verlangt der Standard immerhin Zugriffszeiten, die im Mittel sublinear sind, also langsamer wachsen als die Zahl der Elemente.
| Operation | Aufwand |
|---|---|
arr[i], arr.at(i), arr.length | O(1) |
push(), pop() | O(1) amortisiert |
shift(), unshift() | O(n), alle Elemente rücken |
splice(), toSpliced() | O(n) |
includes(), indexOf(), find(), some() | O(n) |
slice(), Spread [...arr], concat() | O(n), es entsteht eine Kopie |
sort(), toSorted() | O(n log n) |
Set.prototype.has(), Map.prototype.get() | im Mittel O(1) |
Zwei Zeilen verdienen besondere Aufmerksamkeit. shift() wirkt harmlos, verschiebt aber den gesamten Rest des Arrays. Wer ein Array als Warteschlange nutzt und vorn entnimmt, landet bei großen Mengen schnell bei quadratischem Gesamtaufwand. Wie sich eine Warteschlange mit konstanten Kosten an beiden Enden bauen lässt, zeigt der Beitrag über FIFO-Queues und Deques in JavaScript. Am Ende eines Arrays dagegen sind push() und pop() billig, weshalb sich ein Array gut als Stapel eignet, wie im Tutorial zum Stack in JavaScript und TypeScript beschrieben.
Die zweite Stelle sind Kopien. Methoden wie toSorted() oder der Spread-Operator erzeugen jedes Mal ein neues Array. Das ist für die Lesbarkeit oft richtig, kostet aber Zeit und Speicher in O(n). Welche Methoden ein Array verändern und welche eine Kopie liefern, sortiert der Beitrag zu Best Practices für JavaScript-Arrays.
Speicherkomplexität: der zweite Preis
Speicher folgt denselben Regeln wie Laufzeit. Gemessen wird in der Regel der zusätzliche Platz, den ein Verfahren neben der Eingabe braucht. Eine Summe über ein Array benötigt O(1) Zusatzspeicher, eine sortierte Kopie O(n), eine Abstandstabelle zwischen allen Paaren von n Orten O(n²). Bei 10.000 Orten sind das bereits 100 Millionen Einträge.
Ein oft übersehener Speicherverbraucher ist die Rekursion. Jeder Funktionsaufruf, der noch nicht beendet ist, belegt einen Eintrag auf dem Aufrufstapel. Eine Rekursion mit Tiefe n braucht deshalb O(n) Speicher, auch wenn im Code keine einzige Liste angelegt wird. Wird die Tiefe zu groß, bricht JavaScript mit einem RangeError ab. Am Beispiel der Fibonacci-Zahlen lässt sich der Tausch von Zeit und Speicher gut zeigen:
// Zeit exponentiell: dieselben Werte werden immer wieder neu berechnet
function fibNaiv(n) {
return n < 2 ? n : fibNaiv(n - 1) + fibNaiv(n - 2);
}
// Zeit O(n), Speicher O(n): Zwischenergebnisse landen in einer Map
function fibMemo(n, cache = new Map()) {
if (n < 2) return n;
if (cache.has(n)) return cache.get(n);
const ergebnis = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
cache.set(n, ergebnis);
return ergebnis;
}
// Zeit O(n), Speicher O(1): nur die letzten beiden Werte zählen
function fibIterativ(n) {
let [a, b] = [0, 1];
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
console.log(fibNaiv(30), fibMemo(30), fibIterativ(30)); // 832040 832040 832040
console.log(fibMemo(50), fibIterativ(50)); // 12586269025 12586269025
Die naive Fassung ruft sich für n = 30 schon rund 2,7 Millionen Mal selbst auf, für n = 50 wäre sie praktisch unbrauchbar. Das Zwischenspeichern von Ergebnissen, die Memoisierung, macht daraus ein lineares Verfahren, bezahlt mit einer Map. Die iterative Fassung kommt ganz ohne Zusatzspeicher aus. In der Praxis ist die Abwägung selten so eindeutig. Ein Cache, der ohne Obergrenze wächst, wird in einem langlebigen Serverprozess schnell zum Speicherleck.
Schlimmster Fall, Durchschnitt und amortisierte Kosten
Die Angabe „push() ist O(1)“ stimmt nur in einer bestimmten Lesart. Ein dynamisches Array hält intern einen Speicherblock mit Reserve vor. Ist er voll, legt die Engine einen größeren an und kopiert alle Elemente um. Dieser einzelne Aufruf kostet O(n). Weil der Block dabei jeweils um einen Faktor wächst, passiert das so selten, dass die Kosten verteilt auf alle Aufrufe konstant bleiben. Diese Sicht heißt amortisiert.
Bei Hashtabellen wie Map und Set ist es der durchschnittliche Fall, der O(1) ergibt. Im ungünstigsten Fall landen viele Schlüssel im selben Bereich der Tabelle, dann degeneriert das Nachschlagen. Mit den Hashfunktionen moderner Engines kommt das im Alltag praktisch nicht vor. Bei Quicksort ist der Unterschied größer: Im Mittel liegt das Verfahren bei O(n log n), im schlimmsten Fall bei O(n²). Für die eingebaute Sortierung spielt das keine Rolle, denn V8 verwendet seit Jahren TimSort, das auch im schlimmsten Fall bei O(n log n) bleibt.
Für die Praxis heißt das: Bei Diensten, die auf jede einzelne Anfrage schnell antworten müssen, zählt der schlimmste Fall. Bei Stapelverarbeitung über Millionen Datensätze genügt meist die amortisierte oder durchschnittliche Betrachtung.
Messen statt raten: Big O und Benchmarks zusammen
Big O sagt voraus, wie Code skaliert. Ob er bei realen Datenmengen schnell genug ist, zeigt nur eine Messung. Beide Werkzeuge ergänzen sich: Eine Messreihe mit wachsendem n bestätigt oder widerlegt die Abschätzung aus dem Code. Das folgende Beispiel misst die beiden Duplikatprüfungen von oben.
function messe(name, fn) {
const start = performance.now();
fn();
console.log(`${name}: ${(performance.now() - start).toFixed(1)} ms`);
}
for (const n of [5_000, 10_000, 20_000]) {
const daten = Array.from({ length: n }, (_, i) => i); // keine Duplikate: schlimmster Fall
messe(`naiv, n = ${n}`, () => hatDuplikateNaiv(daten));
messe(`Set, n = ${n}`, () => hatDuplikate(daten));
}
Die absoluten Millisekunden hängen von Rechner und Engine ab. Aufschlussreich ist das Verhältnis: Verdoppelt sich n, sollte sich die Zeit der naiven Variante ungefähr vervierfachen, die der Set-Variante ungefähr verdoppeln. Einzelne Durchläufe schwanken allerdings stark, weil der JIT-Compiler, also der Teil der Engine, der häufig ausgeführten Code zur Laufzeit optimiert, erst nach einigen Wiederholungen greift. Für belastbare Zahlen sollten Sie mehrere Durchläufe machen oder ein Benchmark-Werkzeug wie bench aus Vitest oder die Bibliothek Tinybench nutzen, die Aufwärmrunden und Wiederholungen selbst übernehmen.
Außerdem entscheidet Big O selten allein über die Performance einer Webanwendung. Netzwerk, Datenbankabfragen, Bundle-Größe und Rendering wiegen oft schwerer als ein einzelner Algorithmus. Wie Sie vorgehen, um im Browser die eigentlichen Engpässe zu finden, beschreibt unser Beitrag zur Optimierung der JavaScript-Performance.
Big O im Vorstellungsgespräch und im Code-Review
In technischen Bewerbungsgesprächen gehört die Komplexitätsanalyse weiterhin zum Standard, oft in Form von Programmieraufgaben auf Plattformen wie LeetCode oder HackerRank. Erwartet wird selten die perfekte Lösung auf Anhieb. Bewertet wird vor allem der Weg: zuerst eine einfache, korrekte Lösung, dann eine begründete Aussage zu ihrer Komplexität und schließlich die Frage, ob eine andere Datenstruktur sie verbessert. Wer etwa erklärt, warum ein Set die Duplikatprüfung linear macht und was das an Speicher kostet, zeigt genau das Verständnis, nach dem gefragt wird.
Im Arbeitsalltag ist das Code-Review der wichtigere Ort. Hier lohnt ein Blick auf drei Muster: Suchmethoden innerhalb von Schleifen oder Callbacks, shift() oder unshift() auf langen Arrays sowie Abfragen an Datenbank oder API innerhalb einer Schleife. Alle drei sehen im Code unscheinbar aus und fallen erst mit wachsenden Datenmengen auf.
Auch KI-Assistenten beim Programmieren ändern daran wenig. Sie schlagen häufig funktionierenden Code vor, der bei kleinen Testdaten unauffällig ist. Ob er bei Produktionsdaten trägt, muss weiterhin jemand beurteilen, der die Komplexität lesen kann.
Was das für Ihr Team bedeutet
Die Big-O-Notation ist kein akademischer Selbstzweck, aber auch kein Grund, jeden Code auf die theoretisch beste Klasse zu trimmen. Für die meisten Teams lohnt sich ein pragmatischer Umgang: die gängigen Klassen sicher erkennen, die Kosten der eingesetzten Bibliotheksfunktionen kennen und bei Code, der mit wachsenden Datenmengen arbeitet, die Komplexität im Review ansprechen. Überschätzt wird dagegen die Feinoptimierung kleiner Listen. Bei 50 Einträgen schlägt lesbarer Code fast immer die cleverere Variante.
Wo Datenmengen absehbar wachsen, etwa bei Importen, Berichten oder Suchfunktionen, gehört eine kurze Komplexitätsbetrachtung in den Entwurf. Kombiniert mit Messungen auf realistischen Datenmengen verhindert sie die Sorte Performanceproblem, die erst nach Monaten im Betrieb auffällt und dann teuer wird. Wenn langsame Webanwendungen bereits ein Thema sind, finden Sie auf unserer Seite zur Web-Performance-Beratung unsere Angebote für Analyse, Coaching und Seminare.
Häufige Fragen zur Big-O-Notation
Warum misst man nicht einfach die Laufzeit?
Messungen gelten nur für einen Rechner, eine Engine und eine Datenmenge. Big O beschreibt dagegen das Wachstum unabhängig davon und erlaubt eine Vorhersage für Datenmengen, die es heute noch nicht gibt. Sinnvoll ist beides: die Abschätzung im Entwurf, die Messung zur Bestätigung.
Ist O(n log n) deutlich schlechter als O(n)?
In der Praxis kaum. Der Faktor log n beträgt bei einer Million Elementen etwa 20 und wächst sehr langsam. Deshalb gilt Sortieren als günstig, solange es nicht in einer Schleife wiederholt wird.
Was bedeutet O(1) bei einer Map genau?
Es bedeutet, dass ein Zugriff im Mittel gleich lange dauert, egal ob die Map hundert oder eine Million Einträge enthält. Ein einzelner Zugriff kann trotzdem teurer sein als der Zugriff auf ein Array-Element per Index, weil zuerst der Hashwert des Schlüssels berechnet wird.
Spielt Speicherkomplexität bei heutiger Hardware noch eine Rolle?
Ja, vor allem in Umgebungen mit festen Grenzen. Serverless-Funktionen und Container laufen mit begrenztem Arbeitsspeicher, Browser auf Smartphones ebenso. In der Cloud schlägt sich Speicherbedarf zudem direkt in den Kosten nieder.
Kategorien