Die Bibliothek · Informatik & KITafel № 029 · Folio III
ILL. № 029
CS·KI
Plate — O-Notation
·Tafel № 029

O-Notation

Der Aufwand verbirgt sich in der Form, nicht im Vorfaktor.
Als Nächstes empfohlen → Datenstrukturen · CS·KI
Facetten
  • O for 'order of' — the growth-rate shorthandnoch nicht geprüft
  • Linear O(n) vs binary O(log n) searchnoch nicht geprüft
  • Sorted-insert: the O(n) shift you forgetnoch nicht geprüft
Der Beitrag

Die O-Notation entstand 1894 beim deutschen Mathematiker Paul Bachmann, wurde von Edmund Landau popularisiert und in den 1970er Jahren von Donald Knuth in die Informatik importiert. Sie fängt eine der nützlichsten Intuitionen der Algorithmenanalyse ein: was zählt, ist nicht, wie schnell ein Programm bei einer gegebenen Eingabe läuft, sondern wie seine Laufzeit wächst, wenn die Eingabe wächst. Eine O(n²)-Sortierung ist katastrophal langsamer als eine O(n log n)-Sortierung bei einer Million Elementen, ungeachtet dessen, welche bei zehn Elementen schneller ist. Das Verhalten bei zehn Elementen ist ein Rundungsfehler; das Verhalten, wenn die Daten anschwellen, ist Schicksal. Man rechne es durch: für n = 1 000 000 braucht ein einzelner O(n)-Durchlauf rund eine Million Schritte, eine O(n²)-Doppelschleife dagegen rund eine Billion — der Unterschied zwischen einer Kaffeepause und einer Erdzeitalter-Spanne. Der Aufwand verbirgt sich in der Form der Kurve, nicht im Vorfaktor.

Die O-Notation klassifiziert Algorithmen nach ihrer asymptotischen Wachstumsrate: O(1) konstant, O(log n) logarithmisch, O(n) linear, O(n log n) linear-logarithmisch, O(n²) quadratisch, O(2ⁿ) exponentiell. Die Notation verwirft bewusst konstante Faktoren und Terme niedrigerer Ordnung — sie fragt, wie der Algorithmus skaliert, wenn die Eingaben groß werden, denn in diesem Grenzfall überwältigt der dominante Term alles Übrige. Bei derselben Eingabe von einer Million Elementen kommt eine O(log n)-Binärsuche mit etwa zwanzig Schritten aus, wo der lineare Durchlauf eine Million und die quadratische Schleife eine Billion benötigt; die Abstände zwischen den Sprossen der Leiter stellen jede Konstante in den Schatten, die ein sorgfältiger Programmierer noch abschöpfen mag. Eben deshalb schreibt man einen Term wie 3n² + 7n + 200 schlicht als O(n²) — für großes n überwächst der quadratische Anteil den linearen und die Konstante so vollständig, dass ihr Festhalten falsche Genauigkeit wäre. Genau dies braucht es, um die Leistung auf realen Lasten vorherzusagen, wo Eingabegrößen routinemäßig über viele Größenordnungen schwanken. Die Disziplin schult einen eigenen algorithmischen Geschmack: Darstellungen zu suchen, die logarithmische statt linearer Suche erlauben; verschachtelte Schleifen zu meiden, die quadratische Zeit erzeugen; wo möglich auf Hashing zurückzugreifen, um O(n)-Lookups auf amortisierte O(1) zu drücken; zu erkennen, wann ein Problem im Kern NP-schwer ist und exakte Lösungen schlicht nicht skalieren werden — die offene Frage P gegen NP ist im Grunde die Frage, ob sich in einer ganzen Klasse solcher Probleme ein polynomieller Algorithmus verbirgt, den noch niemand gefunden hat. Die von O ignorierten Konstanten sind in der Praxis nicht immer vernachlässigbar — Cache-Effekte, Speicherhierarchie, Sprungvorhersage und Parallelisierung können die absolute Leistung um Größenordnungen verschieben, und ein sauberes O(n log n)-Verfahren kann bei kleinem n oder unter einer großen versteckten Konstante einem rohen O(n²)-Verfahren unterliegen —, doch die asymptotische Gestalt bleibt fast immer der richtige Ausgangspunkt, wenn man bedenken will, welcher Ansatz tragen wird, sobald die Daten wachsen.

Warum jetztDie O-Notation wird in jedem Algorithmenkurs als Erstes gelehrt, in jedem technischen Vorstellungsgespräch als Erstes gefragt und von Programmierern, die den Muskel nicht trainieren, als Erstes vergessen. Die gegenwärtigen Skalierungsdebatten — über das Training großer Sprachmodelle, über Graphenalgorithmen in sozialen Netzwerken, über kryptographische Primitive in einer Post-Quanten-Welt, über die Energiekosten des Rechnens — laufen sämtlich mit O-Notation-Argumenten, mal explizit, mal implizit. Die reife Fassung der Disziplin kennt ihre eigenen Ränder: die Asymptotik kann bei kleinem n oder hinter einer großen Konstante in die Irre führen — weshalb ein galaktisch effizienter Algorithmus, dessen Konstante in die Millionen geht, gegen das naive Verfahren, das alle tatsächlich ausliefern, nutzlos sein kann. Auf einer realen Maschine hat der Profiler, nicht das Lehrbuch, das letzte Wort, und der erfahrene Entwickler liest erst die Wachstumsklasse und misst dann. Dennoch gehört die schlichte Übung, in Wachstumsraten zu denken, zu den dauerhaftesten geistigen Aufrüstungen, die eine Karriere in der Softwareentwicklung schenkt.