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

(samwho.dev)

2 Punkte von GN⁺ 2025-08-26 | 1 Kommentare | Auf WhatsApp teilen

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

1 Kommentare

GN⁺ 2025-08-26

Hacker-News-Kommentare

Dieser Artikel und auch die HN-Kommentare setzen die Tradition fort, Big O Notation zu erklären und dabei über ihren praktischen Nutzen und technische Details zu streiten. Als lesenswerte Beispiele gibt es diesen Erklärartikel und diesen Text über das Verhalten von Experten
- Wenn man sich die Kommentare zum letzten Artikel ansieht, fiel ein Nutzer namens Pyon durch einen giftigen und unflexiblen Ton auf. Neds Erwiderung ist aber auch nicht besonders gelungen. Er erklärt die technischen Details nicht genau, sondern redet nur wiederholt um „bestimmte Details“ herum. Schade ist sowohl, dass nicht klar wird, warum seine Kritik bloß Haarspalterei gewesen sein soll, als auch, warum sogar der eigentliche Inhalt so zurückgewiesen wird. Ned zeigt zwar grundsätzlich die richtige Haltung zu Kommunikation und Empathie im Internet. Von einem Lehrenden hätte ich mir aber gewünscht, dass er zumindest einmal einordnet, warum der technische Einwand zu kleinteilig oder bloße Korinthenkackerei war. Ned sagt selbst nur, dass er es „jahrzehntelang nicht gewusst“ habe, und das wirkt nicht ganz ausreichend. Als ich den ursprünglichen Kommentar-Thread noch einmal angesehen habe, hat Ned dort tatsächlich ziemlich diplomatisch und ernsthaft diskutiert. Umso mehr frage ich mich, warum diese Analyse im Blogpost fehlt. Ich selbst weiß ehrlich gesagt auch nicht genau, worin die technischen Details bestehen, aber eine knappe Zusammenfassung hätte ich mir einmal gewünscht
- Ich bin eher auf der Seite kritischer Experten. Wenn ich in Blogs Versuche sehe, komplexe Themen zu erklären, bin ich fast immer enttäuscht, weil meistens Nichtfachleute erklären und dabei an Genauigkeit verlieren. Das führt dazu, dass 1) ungenaue Inhalte quer durchs Internet kopiert werden und 2) Leser sich mit Blogniveau zufriedengeben, nicht weiterlernen und ihre Unwissenheit damit verfestigen. Zusätzlich gefiel mir auch das Seitenlayout nicht. Aus meiner Erfahrung mit ADHD und schwächerem Gedächtnis kann ich nur folgen, wenn Inhalte durch passende Strukturierung aufgebrochen werden, etwa mit Zwischenüberschriften/Fettdruck/Farbtrennung/Aufzählungen. Dieser Text wirkte auf mich einfach wie eine Textwand. Je länger es dauert, die Kernaussage zu erfassen, desto eher verliere ich die Konzentration. Die Big-O-Erklärung in der Simple Wikipedia ist deutlich direkter. Die reguläre Wikipedia-Seite dagegen bringt plötzlich Mathematik ins Spiel, und wenn man sie sich ansieht, merkt man, dass Big O in Wirklichkeit ein viel komplexeres Thema ist, sodass man am Ende fast denkt, dass Vereinfachung vielleicht eher schadet
- Der zweite Link handelt nicht von Big-O, und man muss sich so ein Verhalten nicht zum Vorbild nehmen
- Ned hat mir vor ein paar Tagen eine E-Mail geschrieben, und ich freue mich, auf angenehme Weise zu solchen Diskussionen beizutragen
- Die eigentliche Lehre aus solchen Texten ist für mich: Wenn es fehlerhafte oder missverständliche Erklärungen gibt, soll man nicht aufhören, sie zu korrigieren — sondern erkennen, dass manche „Experten“ online einfach nur einen Streit gewinnen wollen. Wenn man sich Pyons Auftreten ansieht, wirkte das ziemlich aggressiv und wie ein Internet-Troll. Man sollte daraus auf keinen Fall schließen, dass technische Details unwichtig seien und Ungenauigkeiten deshalb in Ordnung wären
O(1) basiert in der Praxis oft auf einer Hash-Funktion; das ist nicht völlig simpel, verursacht aber einen konstanten Rechenaufwand. Bei sehr kleinen Datenmengen kann selbst ein im Worst Case schlechterer Algorithmus wie O(n^2) in der tatsächlichen Laufzeit trotzdem schneller sein
- Stimmt schon, aber man sollte das nicht zu laut herausstellen. In der Praxis ist es schon schwer genug, Leuten klarzumachen, dass n^2 bedeutet, dass der Computer irgendwann in die Knie geht. Außerdem kann man je nach Fall auch eine perfekte Hash-Funktion wie mod verwenden
Ich habe das Gefühl, dass Big-O heute nicht mehr die gleiche Bedeutung hat wie früher. Moderne Hardware hat Multithreading, Pipelines, NUMA, komplexes Caching und vieles mehr; manche Operationen sind in weniger als einem Taktzyklus erledigt, andere brauchen Hunderte oder Tausende. Wenn man einen Algorithmus nur über die Anzahl der Durchläufe der innersten Schleife erklären will, verzerrt das eher die Realität. Und wenn man über Big-O spricht, sollte man unbedingt auch andere Notationen wie Big-Omega erwähnen. (Nebenbei: Die Animation zum Thema Big-O fand ich auch unterhaltsam)
- Die Big-O-Theorie ist gerade entstanden, um Rechenaufwand unabhängig von solchen geräteabhängigen Faktoren zu beschreiben. In diesem Sinne ist sie ein zeitloses Werkzeug. (Ein guter Vortragender erwähnt in der Regel auch, dass eine Konstante wie C bei kleinen N sehr wohl ein entscheidender Faktor sein kann)
Wirklich interessant ist im Quantencomputing, dass manche Operationen mit der Zahl der Atome wie O(n^7) wachsen, Wissenschaftler aber trotzdem keine Angst davor haben, diese Berechnungen tatsächlich auszuführen. Denn N ist klein genug, Computer und Speicher werden laufend schneller, und die Ergebnisse sind enorm wertvoll. (Ich bin kein Informatikexperte; falls ich die O()-Notation falsch verwendet habe, bitte ich um Nachsicht)
- Man kann auch einfach sagen, dass es „proportional zu n^7 wächst“. Die meisten verstehen zwar O(n^7), aber mathematisch bezeichnet O nur eine obere Schranke, also ist das nicht ganz präzise. Wenn man es wirklich exakt ausdrücken will, wäre etwas wie Ω(n^7) richtiger
Die Visualisierung gefällt mir wirklich sehr. Selbst mit früherem Unterricht zu Algorithmen hilft mir die visuelle Darstellung immer noch enorm
Vielleicht liegt es daran, dass ich Elektrotechnik studiert habe, aber Big-O-Notation wurde für mich immer wie ein Konzept behandelt, bei dem man irgendetwas grob überspringt. Es wurde stets so dargestellt, als müsse man das ohnehin schon wissen, und ich habe kaum je eine wirklich freundliche Einführung dazu gesehen. Ich frage mich, auf welchem Niveau in Mathematik- oder Informatikstudiengängen dieses Konzept erstmals eingeführt wird
- Am systematischsten habe ich Big-O in Discrete Math im Informatikstudium gelernt
- An meiner Hochschule wurde Big-O samt verschiedener Beweismethoden in Algorithm Analysis gelehrt, einem Pflichtfach. Das war allerdings eher ein Kurs im 3. oder 4. Studienjahr, und stillschweigend wurde wohl vorausgesetzt, dass man das Grundkonzept schon im 1. Jahr irgendwie aufgeschnappt hatte
- Mathematisch bedeutet, dass eine Funktion f(x) O(g(x)) ist, dass f(x)/g(x) für eine gewisse Konstante C die Bedingung „für alle x gilt f(x)/g(x) < C“ erfüllt. In der Informatik steht f(x) oft für eine Komplexität wie die Anzahl der Operationen eines bestimmten Algorithmus
- Die Definition der Big-O-Notation lässt verschiedene Interpretationen zu. Wenn man etwa einen Algorithmus über die Anzahl der Schritte einer Turing-Maschine definiert, kann es keine logarithmischen Laufzeitalgorithmen geben, und O(log n) wird als O(1) behandelt
- Ich habe es im Pflichtfach des ersten Informatikjahres gelernt. Es ist nichts Besonderes; es beschreibt einfach, wie der Rechenaufwand wächst, wenn die Eingabedatenmenge zunimmt. Es sieht schwieriger aus, als es ist, tatsächlich ist es sehr einfach und klar
Die dynamische Visualisierung hat beim Verständnis enorm geholfen. Ich hoffe, es gibt mehr solcher Lektionen und Materialien
- Das zu hören freut mich sehr, vielen Dank
Jedes Mal, wenn ein Thread zur Big-O-Notation auftaucht, hoffe ich ein bisschen, dass jemand erklärt, wie das mit dem Anime The Big O zusammenhängt. Ich weiß bis heute nicht so recht, worum es in der Serie eigentlich geht
- (vier Dosen Bier auf ex heruntergestürzt)Also gut, hör zu. Der Anime ist im Grunde so, als würde man nacheinander Pacific Rim, Dark City und The Matrix zusammenmischen
Für mich versteht man Big-O-Notation am besten, wenn man sie mit Analogien aus dem Alltag verknüpft
Ich finde das ein wunderschönes Material. Ich habe ein Signal geschickt und hoffe, es ist gut angekommen; irgendwie hat mir das einfach einen kleinen Dopaminschub gegeben
- Ist gut angekommen. Danke