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

#algorithms#computer-science#javascript

Die Big-O-Notation wird mit abstrakten Beispielen glehrt - Arrays aus Ganzzahlen sortiern, ausgeglichene Bäume durchsuchn - und dann still und leise fallen glassn, sobois Leit echte Features ausliefern. Des is a Fehler: Dieselbe Überlegung erklärt, warum a "einfache" verschachtelte Schleifn über deine Produktivdaten an Server lahmlegen kann, sobois die Daten über a poar tausend Zeiln wachsn. Do is Big O verankert in Code, den du tatsächlich schreibn würdest.

Wos Big O tatsächlich misst

Big O beschreibt, wia die Laufzeit (oda der Speicherverbrauch) von am Algorithmus wachst, wenn die Eingabegröße wachst - ned die exakte Zeit, de von deiner CPU abhängt, sondern die Form der Wachstumskurve. "O(n)" heißt "ungefähr proportional zur Eingabegröße". "O(n²)" heißt "ungefähr proportional zum Quadrat der Eingabegröße". Die konstanten Faktoren und die genaue Befehlsanzoi wern absichtlich weggworfn; wos zählt, is, wos passiert, wenn n groß wird.

Des zählt, weil konstante Faktoren im großen Maßstab nimma wichtig sand und die Wachstumsrate ois Einziges übrig bleibt. A O(n²)-Algorithmus, der bei n = 100 schneller is ois a O(n)-Algorithmus, verliert immer, sobois n groß gnua is - es is ka Frage des Ob, nur des Wo der Kreuzungspunkt liegt.

O(1): konstante Zeit

An Wert über den Key in ana Map oda in am Objekt nachzuschaun wird ned langsamer, wenn die Map wachst - den Key zu hashn und zu seinem Bucket zu springa braucht gleich vül Schritte, ob's 10 Einträge oda 10 Millionen gibt.

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

O(n): lineare Zeit

Die Orbeit wachst direkt proportional zur Eingabegröße. Ein einzelner Durchlauf über a Array - an Wert suchen, summiern, jedes Element transformiern - is der klassische Foi:

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

Das Array verdoppeln, die Worst-Case-Orbeit verdoppeln. Des is linear, und für die meisten alltäglichen Operationen völlig in Ordnung.

O(n²): quadratische Zeit - die, de die Produktion still und leise killt

Do leben die echten Bugs. A Schleifn in a Schleifn über dieselben Daten zu verschachteln multipliziert die Orbeit:

// 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 sand des ~5.000 Vergleiche - sofort. Bei 100.000 Nutzern ~5 Milliarden - die Art Sache, die in ana Demo mit Testdaten super funktioniert und dann in a Timeout rennt, sobois sie auf echtes Produktionsvolumen trifft. Genau dieses Muster - a innere Schleifn oda a innerer .find()-/.includes()-Aufruf über Daten, de mit da äußeren Schleifn wachsn - is der häufigste versehentlich quadratische Bug im Anwendungscode.

Die Lösung is fast imma, Speicher gegn Zeit zu tauschn: einmal a Lookup-Struktur baun (O(n)), dann O(1)-Lookups in oaner einzigen Schleifn machn (insgesamt O(n)), statt O(n)-Lookups in ana Schleifn (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];
}

Gleiche Ausgabe, und es bleibt schnell, wenn die Eingabe wachst - des is der Tausch, den a Map/Set fast imma darstellt: bissl Speicher zoin, um a O(n)-Lookup in a O(1)-Lookup zu verwandeln.

O(log n): logarithmische Zeit

Die Orbeit wachst viel langsamer ois die Eingabegröße - jeder Schritt eliminiert an großen Bruchteil von dem, wos no zum Durchsuchn übrig is. Binärsuche über a sortiertes Array is das Paradebeispiel: in die Mitte schaun, die Hälfte wegwerfn, wiederholn.

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;
}

A sortiertes Array mit 1.000.000 Einträgen zu durchsuchn braucht höchstens ~20 Vergleiche, ned 1.000.000 - des is der Unterschied zwischn O(log n) und O(n) in da Praxis. Des is a der Grund, warum Datenbank-Indizes (typischerweise B-Bäume) Lookups auf großen Tabellen schnell machn: Sie verwandeln an O(n)-Tabellenscan in an O(log n)-Baumdurchlauf.

O(n log n): die Komplexität der Sortier-Familie

De meisten effizienten vergleichsbasierten Sortieralgorithmen (Merge Sort, Quicksorts Durchschnittsfall, und wos Array.prototype.sort in modernen JS-Engines unter da Haubn nutzt) laufn in O(n log n) - besser ois O(n²), und es is die theoretische Untergrenze für vergleichsbasiertes Sortiern. Wennst dich dabei ertappst, a selbstgschriebenes Sortieren mit O(n²) zu bauen (wia naiven Bubble Sort), nimm einfach das eingbaute sort - es is schneller und scho korrekt.

Komplexität aus deim eigenen Code lesn

A grober Satz an Regeln deckt die meisten Alltagsfälle ab:

Eine einzelne Schleifn über n Elemente: O(n).
A Schleifn in ana ondern Schleifn, beide über ungefähr dasselbe n: O(n²).
Den Suchraum bei jeder Iteration halbiern (Binärsuche, Abstieg in an ausgeglichenen Baum): O(log n).
Array-Methoden wia .includes(), .indexOf() und .find() sand jeweils für sich O(n) - eine innerhalb ana Schleifn aufzurufn is genau das Verschachtelte-Schleifn-Muster von oben, nur anders gschriebn. Des is die häufigste Stelle, wo quadratisches Verhalten sich in aller Öffentlichkeit 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's ned drum, Millisekunden von Code runterzuhobeln, der eh scho gut läuft - es geht drum zu wissn, wöche Muster still und leise aufhörn zu skaliern. Das Konkrete, wos sich lohnt, die Augen zu trainiern, is a O(n)-oder-schlimmer-Operation (.includes(), .find(), a ondere Schleifn), de in ana Schleifn über dieselbe wachsende Collection sitzt. Dieses oane Muster erklärt die meisten "in Dev hot's funktioniert und in Produktion is's zamgfoin"-Bugs, de dir tatsächlich begegnen wern.