Eine visuelle Einführung in die Big-O-Notation

• Big-O-Notation beschreibt die Wachstumsform der Funktionsleistung in Abhängigkeit von Änderungen der Eingabegröße
• Der Artikel erklärt exemplarisch die Big-O-Fälle konstant, logarithmisch, linear und quadratisch zusammen mit Beispielen
• Je nach Datenstruktur und Algorithmus unterscheidet sich die Zeitkomplexität, was sich etwa beim Sortieren und Suchen in Arrays zeigt
• Für echte Verbesserungen der Code-Performance sind die Wahl der passenden Datenstruktur und das Entfernen unnötiger Operationen in Schleifen entscheidend
• Big O zeigt immer die Beziehung zwischen Eingabe und Laufzeit in maximal vereinfachter Form; bei Performance-Optimierungen ist direktes Messen des Codes wichtig

---

Überblick über die Big-O-Notation

• Die Big-O-Notation ist eine Methode, um statt der Zeitmessung die Wachstumsform der Laufzeit in Abhängigkeit von der Eingabegröße (n) zu beschreiben
• Sie klassifiziert Laufzeiten nach der Eingabegröße; typischerweise werden konstant (O(1)), logarithmisch (O(log n)), linear (O(n)) und quadratisch (O(n²)) analysiert
• Dieser Artikel erklärt die Konzepte anhand visueller Beispiele und echter Codebeispiele so, dass auch Einsteiger sie verstehen können

Iteration und lineare Algorithmen

• Die Funktion sum(n) ist ein Beispiel für eine Schleifenstruktur, die von 1 bis n aufsummiert; je größer n wird, desto proportional steigt auch die Laufzeit
• Tatsächlich benötigt sum(1e9) etwa 1 Sekunde, sum(2e9) etwa 2 Sekunden; die wall-clock time wächst also nach einem O(n)-Muster
• Zeitkomplexität ist die Beziehung zwischen der Eingabe einer Funktion und ihrer Laufzeit und wird mit der Big-O-Notation ausgedrückt (O(n) — proportional zu n)
• Nutzt man statt einer Schleife die mathematische Formel sum(n) = (n*(n+1))/2, bleibt die Laufzeit konstant und unabhängig von n
• Solche Funktionen haben eine konstante Zeitkomplexität O(1); typisch ist, dass die Laufzeit nicht mit der Eingabegröße wächst

Syntax der Big-O-Notation

• Das O in Big O stammt von „Order“ und bezeichnet nur die Wachstumsform selbst
• Es wird nicht die absolute Laufzeit angegeben, sondern nur das Muster des Wachstums im Verhältnis zur Eingabe in kompakter Form
• Selbst bei einer O(n)-Funktion schreibt man nicht kompliziert „O(2n)“ oder „O(n+1)“, sondern wählt nur den einfachsten dominanten Term

Laufzeitverkürzung durch die Struktur der Eingabe

• Wie das Formel-Beispiel bei sum(n) zeigt, kann sich die Zeitkomplexität durch Verbesserung des Algorithmus von O(n) auf O(1) ändern
• Allerdings ist eine konstante Zeitkomplexität nicht automatisch immer schneller; die tatsächliche Gesamtlaufzeit hängt auch von der jeweiligen Operation ab
• Ein O(n)-Algorithmus kann bei bestimmten Eingaben schneller sein als O(1), doch bei wachsender Eingabegröße wird O(1) langfristig immer überlegen

Sortieren und quadratische Algorithmen: Beispiel Bubble Sort

• Bubble Sort ist ein grundlegendes Beispiel für Sortierung durch wiederholtes Vertauschen benachbarter Werte
• Ist das Array bereits sortiert, genügt ein Durchlauf (O(n)); in umgekehrter Reihenfolge sind wiederholt n Durchläufe nötig → im Worst Case insgesamt n² Operationen
• O(n²)-Algorithmen verursachen mit wachsender Eingabe eine stark quadratisch ansteigende Laufzeit
• In der Praxis bezieht sich Big O immer auf den Worst Case (auch wenn je nach Situation zusätzlich Durchschnitts- oder Best Case angegeben werden)
• Je nach Anfangszustand des Arrays kann die Zahl der Durchläufe sinken, doch wegen der Betrachtung des Worst Case wird Bubble Sort als quadratische Zeitkomplexität eingeordnet

Suchen und logarithmische Algorithmen: Beispiel Binäre Suche

• Binäre Suche schätzt den Mittelwert eines sortierten Bereichs und halbiert in jedem Schritt den verbleibenden Kandidatenraum
• Um zum Beispiel eine bestimmte Zahl zwischen 1 und 100 zu erraten, braucht man höchstens 7 Versuche; zwischen 1 und 1 Milliarde sind es weniger als 31
• Da sich die Kandidatenliste in jedem Schritt halbiert, beträgt die Laufzeit O(log n) (logarithmische Zeitkomplexität)
• Logarithmische Algorithmen wachsen bei größerem n nur sehr langsam und sind damit deutlich effizienter als lineare oder quadratische Verfahren
• Beim Vergleich der Graphen werden die Wachstumsunterschiede zwischen log n, n und n² besonders deutlich

Praktische Anwendung: Tipps zur Verbesserung der Zeitkomplexität

Element in einer Liste finden

• Grundsätzlich ist eine Funktion zum Suchen eines Werts in einem Array O(n)
• Wenn häufig gesucht wird, lässt sich die Komplexität mit einer Datenstruktur wie Set auf O(1) verbessern
• Allerdings kostet bereits die Umwandlung mit new Set(array) selbst O(n) und lohnt sich daher nur bei häufigen Abfragen
• Beispiel: items.has("banana") bietet konstante Zeitkomplexität

Schleifen mit Index sinnvoll schreiben

• Code wie unten, der innerhalb einer Schleife .indexOf verwendet, ist häufig die Ursache für Performance-Probleme

  function buildList(items) {
    const output = [];
    for (const item of items) {
      const index = items.indexOf(item);
      output.push(`Item ${index + 1}: ${item}`);
    }
    return output.join("\n");
  }
  

• Da .indexOf innerhalb der Schleife eine O(n)-Operation ist, ergibt sich insgesamt ein O(n^2)-Muster

• Mit indexbasierter Iteration oder forEach((item, index) => ...) lässt sich das auf O(n) verbessern

  function buildList(items) {
    const output = [];
    for (let i = 0; i < items.length; i++) {
      output.push(`Item ${i + 1}: ${items[i]}`);
    }
    return output.join("\n");
  }
  

Memoization nutzen

• Bei Strukturen wie der Fakultät, in denen bei wiederholten Aufrufen dieselben Werte mehrfach berechnet werden, lässt sich die Performance durch Caching der Ergebnisse (mit Map) verbessern

• Zugriffe auf Map sind O(1) und minimieren unnötige Neuberechnungen

• Caching verbessert vor allem die durchschnittliche Laufzeit; auch wenn sich die Worst-Case-Zeitkomplexität nicht ändert, kann die tatsächliche Performance deutlich steigen

  const cache = new Map();
  function factorial(n) {
    if (cache.has(n)) {
      return cache.get(n);
    }
    if (n === 0) {
      return 1;
    }
    const result = n * factorial(n - 1);
    cache.set(n, result);
    return result;
  }
  

Performance-Bewertung und Fazit

• Bei der Verbesserung der Code-Performance sollte man neben der theoretischen Zeitkomplexität immer auch durch direkte Tests prüfen, ob tatsächlich eine Verbesserung vorliegt
• Big O drückt die Beziehung und das Wachstumsmuster zwischen Eingabe und Laufzeit in ihrer wesentlichsten vereinfachten Form aus
• Mit der Wahl guter Algorithmen und der Optimierung von Datenstrukturen lässt sich die Effizienz von Code stark steigern

Kurzfassung

• Die Big-O-Notation beschreibt die Beziehung zwischen Funktionseingabe und Laufzeit
• Wichtige Leistungsklassen: O(1) (konstant), O(log n) (logarithmisch), O(n) (linear), O(n^2) (quadratisch)
• Für effizienten Code sind geeignete Algorithmen und optimierte Schleifen entscheidend
• Die tatsächliche Performance sollte immer direkt gemessen und überprüft werden
• Mit Vergleichsgraphen der Wachstumsformen lassen sich Eigenschaften der Zeitkomplexität auf einen Blick erkennen