Big-O-Notation, erklärt mit echtem Code

#algorithms#computer-science#javascript

Die Big-O-Notation wird mit abstrakten Beispielen gelehrt – Arrays von Ganzzahlen sortieren, balancierte Bäume durchsuchen – und dann stillschweigend fallen gelassen, sobald man echte Features ausliefert. Das ist ein Fehler: Dieselben Überlegungen erklären, warum eine „einfache" verschachtelte Schleife über deine Produktionsdaten einen Server lahmlegen kann, sobald diese Daten über ein paar tausend Zeilen hinauswachsen. Hier ist Big O verankert in Code, den du tatsächlich schreiben würdest.

Was Big O tatsächlich misst

Big O beschreibt, wie die Laufzeit (oder der Speicherverbrauch) eines Algorithmus mit der Eingabegröße wächst – nicht die exakte Zeit, die von deiner CPU abhängt, sondern die Form der Wachstumskurve. „O(n)" bedeutet „ungefähr proportional zur Eingabegröße." „O(n²)" bedeutet „ungefähr proportional zum Quadrat der Eingabegröße." Die konstanten Faktoren und exakten Befehlsanzahlen werden bewusst weggeworfen; entscheidend ist, was passiert, wenn n groß wird.

Das ist wichtig, weil konstante Faktoren im großen Maßstab keine Rolle mehr spielen und nur die Wachstumsrate übrig bleibt. Ein O(n²)-Algorithmus, der bei n = 100 schneller ist als ein O(n)-Algorithmus, verliert immer, sobald n groß genug ist – es ist keine Frage des Ob, nur des Wo der Kreuzungspunkt liegt.

O(1): konstante Zeit

Einen Wert per Schlüssel in einer Map oder einem Objekt nachzuschlagen, wird nicht langsamer, wenn die Map wächst – den Schlüssel zu hashen und zu seinem Bucket zu springen dauert dieselbe Anzahl Schritte, ob es 10 Einträge sind oder 10 Millionen.

function getUserById(usersById, id) {
  return usersById.get(id); // O(1), regardless of map size
}

O(n): lineare Zeit

Die Arbeit wächst direkt proportional zur Eingabegröße. Ein einzelner Durchlauf über ein Array – einen Wert suchen, summieren, jedes Element transformieren – ist der klassische Fall:

function findFirstAdmin(users) {
  for (const user of users) {
    if (user.role === 'admin') return user; // worst case: checks every user once
  }
  return null;
}

Verdoppelt man das Array, verdoppelt sich die Arbeit im schlechtesten Fall. Das ist linear, und für die meisten alltäglichen Operationen völlig in Ordnung.

O(n²): quadratische Zeit – die, die Produktion leise umbringt

Hier leben echte Bugs. Eine Schleife in eine Schleife über dieselben Daten zu schachteln, multipliziert die Arbeit:

// find duplicate emails - O(n²): for every user, scan every other user
function findDuplicateEmails(users) {
  const duplicates = [];
  for (let i = 0; i < users.length; i++) {
    for (let j = i + 1; j < users.length; j++) {
      if (users[i].email === users[j].email) {
        duplicates.push(users[i].email);
      }
    }
  }
  return duplicates;
}

Bei 100 Nutzern sind das ~5.000 Vergleiche – sofort fertig. Bei 100.000 Nutzern sind es ~5 Milliarden – genau die Sorte Ding, die in einer Demo mit Testdaten problemlos läuft und in ein Timeout läuft, sobald sie auf echtes Produktionsvolumen trifft. Genau dieses Muster – eine innere Schleife oder ein innerer .find()-/.includes()-Aufruf über Daten, die mit der äußeren Schleife wachsen – ist der häufigste versehentlich quadratische Bug in Anwendungscode.

Die Lösung ist fast immer, Speicher gegen Zeit zu tauschen: Einmal eine Lookup-Struktur aufbauen (O(n)), dann in einer einzigen Schleife O(1)-Lookups machen (insgesamt O(n)), statt O(n)-Lookups in einer Schleife (insgesamt O(n²)).

// same result, O(n): one pass to build a Set, one pass to check membership
function findDuplicateEmails(users) {
  const seen = new Set();
  const duplicates = new Set();
  for (const user of users) {
    if (seen.has(user.email)) {
      duplicates.add(user.email);
    }
    seen.add(user.email);
  }
  return [...duplicates];
}

Dasselbe Ergebnis, und es bleibt schnell, wenn die Eingabe wächst – das ist der Tausch, den eine Map/ein Set fast immer darstellt: etwas Speicher bezahlen, um einen O(n)-Lookup in einen O(1)-Lookup zu verwandeln.

O(log n): logarithmische Zeit

Die Arbeit wächst deutlich langsamer als die Eingabegröße – jeder Schritt eliminiert einen großen Teil dessen, was noch zu durchsuchen ist. Die binäre Suche in einem sortierten Array ist das Paradebeispiel: in die Mitte schauen, die Hälfte verwerfen, wiederholen.

function binarySearch(sortedArr, target) {
  let low = 0;
  let high = sortedArr.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Ein sortiertes Array mit 1.000.000 Einträgen zu durchsuchen erfordert höchstens ~20 Vergleiche, nicht 1.000.000 – das ist der praktische Unterschied zwischen O(log n) und O(n). Deshalb machen Datenbankindizes (typischerweise B-Bäume) Abfragen auf großen Tabellen schnell: Sie verwandeln einen O(n)-Tabellenscan in einen O(log n)-Baumdurchlauf.

O(n log n): die Komplexität der Sortierfamilie

Die meisten effizienten vergleichsbasierten Sortieralgorithmen (Merge Sort, der Durchschnittsfall von Quicksort und das, was Array.prototype.sort in modernen JS-Engines intern verwendet) laufen in O(n log n) – besser als O(n²) und die theoretische Untergrenze für vergleichsbasiertes Sortieren. Wenn du dabei bist, eine selbstgeschriebene Sortierung mit O(n²) zu bauen (wie naives Bubble Sort), nimm einfach das eingebaute sort – es ist schneller und bereits korrekt.

Komplexität aus dem eigenen Code ablesen

Ein paar grobe Faustregeln, die die meisten Alltagsfälle abdecken:

Eine einzelne Schleife über n Elemente: O(n).
Eine Schleife in einer anderen Schleife, beide über ungefähr dasselbe n: O(n²).
Den Suchraum in jeder Iteration halbieren (binäre Suche, Abstieg in einem balancierten Baum): O(log n).
Array-Methoden wie .includes(), .indexOf() und .find() sind jeweils für sich O(n) – sie innerhalb einer Schleife aufzurufen, ist genau das Muster der verschachtelten Schleife oben, nur anders geschrieben. Das ist die häufigste Stelle, an der sich quadratisches Verhalten offen versteckt.

// looks like one loop, is actually O(n²): .includes() scans the array each call
function withoutDuplicates(items) {
  const result = [];
  for (const item of items) {
    if (!result.includes(item)) result.push(item); // O(n) call, inside an O(n) loop
  }
  return result;
}

// O(n): Set.has() is O(1), so the loop stays linear
function withoutDuplicatesFast(items) {
  return [...new Set(items)];
}

Fazit

Bei Big O geht es nicht darum, Millisekunden aus Code zu kitzeln, der schon gut läuft – es geht darum zu wissen, welche Muster stillschweigend aufhören zu skalieren. Worauf es sich lohnt, den Blick zu trainieren, ist eine Operation mit O(n) oder schlechter (.includes(), .find(), eine weitere Schleife) innerhalb einer Schleife über dieselbe wachsende Sammlung. Dieses eine Muster erklärt die meisten der „in der Entwicklung lief es, in Produktion fiel es um"-Bugs, denen du tatsächlich begegnen wirst.