O-Notation: Komplexitätsklassen im Vergleich

Komplexitätsklassen verständlich

Die O-Notation beschreibt, wie der Aufwand eines Algorithmus mit der Eingabegröße n wächst. Sie gehört zu den Landau-Symbolen aus der Mathematik und wird in der Informatik vor allem für die Zeitkomplexität und den Speicherbedarf verwendet. Die Big-O-Notation gibt eine obere Schranke an und lässt konstante Faktoren und kleinere Terme weg: Ein Algorithmus mit 3n² + 5n + 7 Schritten liegt in O(n²). Das Werkzeug macht diese Laufzeitkomplexität greifbar, indem es für jede Klasse die Zahl der Operationen und eine grob geschätzte Dauer ausrechnet.

Die Komplexitätsklassen von O(1) über O(log n), O(√n), O(n), O(n log n), O(n²) und O(n³) bis O(2ⁿ) und O(n!) unterscheiden sich gewaltig. Bei n = 1.000.000 braucht O(log n) etwa 20 Schritte, O(n log n) rund 20 Millionen, O(n²) eine Billion. Bei angenommenen 100 Millionen einfachen Operationen pro Sekunde sind das Sekundenbruchteile gegen fast drei Stunden. O(2ⁿ) ist schon bei n = 60 jenseits jeder praktischen Rechenzeit. Die Tabelle „Was schafft jede Klasse im Zeitbudget?“ dreht die Frage um und zeigt, welches n in der vorgegebenen Zeit noch machbar ist.

Die Zeitangaben sind Größenordnungen, keine Messungen. Echte Laufzeiten hängen von Konstanten, Cache-Verhalten, Speicherzugriffen und der Programmiersprache ab; ein O(n log n)-Verfahren kann bei kleinen n langsamer sein als ein einfaches O(n²)-Verfahren. Der Logarithmus ist hier zur Basis 2 gerechnet; in der O-Notation spielt die Basis keine Rolle, weil sie nur einen konstanten Faktor ausmacht. Für große Zahlen in anderen Zahlensystemen hilft der Zahlensysteme-Rechner.