O-Notation

Von einem Programm interessiert am Ende weniger, wie schnell es bei einer bestimmten Eingabe fertig wird — entscheidend ist, wie seine Laufzeit mitwächst, wenn die Eingabe wächst. Diese Einsicht steckt in der O-Notation, die 1894 bei dem deutschen Mathematiker Paul Bachmann aufkam, durch Edmund Landau bekannt wurde — die Symbole heißen im Deutschen nach ihm — und in den 1970er Jahren durch Donald Knuth in die Informatik einwanderte. Bei einer Million Elementen ist ein Sortierverfahren mit O(n²) hoffnungslos langsamer als eines mit O(n log n), ganz gleich, welches von beiden bei zehn Elementen vorn liegt. Zehn Elemente sind ein Rundungsfehler; was bei anschwellenden Daten geschieht, ist Schicksal. In Zahlen: Für n = 1 000 000 kostet ein einzelner Durchlauf mit O(n) rund eine Million Schritte, eine Doppelschleife mit O(n²) rund eine Billion — der Unterschied zwischen einer Kaffeepause und einem Erdzeitalter. Der Aufwand steckt in der Form der Kurve, nicht im Vorfaktor.

Sortiert wird nach der asymptotischen Wachstumsrate: O(1) konstant, O(log n) logarithmisch, O(n) linear, O(n log n) linear-logarithmisch, O(n²) quadratisch, O(2ⁿ) exponentiell. Konstante Faktoren und Terme niedrigerer Ordnung fallen dabei mit Absicht unter den Tisch, denn gefragt ist das Verhalten bei großen Eingaben, und dort erdrückt der führende Term alles andere. Wieder auf eine Million Elemente gerechnet: Die Binärsuche mit O(log n) ist nach etwa zwanzig Schritten am Ziel, der lineare Durchlauf braucht eine Million, die quadratische Schleife eine Billion. Zwischen diesen Sprossen liegen Abstände, gegen die jede Konstante verschwindet, die ein sorgfältiger Entwickler noch herausholt. Darum schreibt man für 3n² + 7n + 200 einfach O(n²): Für große n wächst der quadratische Anteil dem linearen und der Konstanten derart davon, dass es falsche Genauigkeit wäre, sie mitzuschleppen. Für die Vorhersage, wie sich ein Verfahren unter realer Last schlägt, ist das genau die richtige Auflösung, denn Eingabegrößen schwanken im Betrieb über viele Zehnerpotenzen. Wer damit umgeht, entwickelt einen eigenen algorithmischen Geschmack: Darstellungen zu wählen, in denen sich logarithmisch statt linear suchen lässt; verschachtelte Schleifen zu meiden, weil sie quadratisch kosten; über Hashing das Nachschlagen von O(n) auf amortisiert O(1) zu drücken; und zu erkennen, wann ein Problem im Kern NP-schwer ist und exakte Lösungen deshalb nie skalieren werden — die offene Frage P gegen NP läuft darauf hinaus, ob sich für eine ganze Klasse solcher Probleme ein polynomieller Algorithmus finden lässt, den bloß noch niemand gefunden hat. Ganz umsonst sind die unterschlagenen Konstanten allerdings nicht zu haben: Cache-Verhalten, Speicherhierarchie, Sprungvorhersage und Parallelisierung verschieben die absolute Laufzeit um Größenordnungen, und ein sauberes O(n log n) kann bei kleinem n oder unter einer großen versteckten Konstante gegen rohes O(n²) verlieren. Als erster Zugriff auf die Frage, welcher Ansatz mitwächst, wenn die Daten wachsen, taugt die asymptotische Gestalt trotzdem fast immer.