O-Notation

Die O-Notation oder anders genannt auch Landau Symbole werden in der Informatik verwendet, um das asymptotische Verhalten von Funktionen zu beschreiben: Das heißt, die O-Notation gibt abhängig von der Eingabegröße an, wie viele Schritte oder Rechenoperationen von der jeweiligen Funktion benötigt werden.

Je nachdem, wie sich der Aufwand abhängig von der Eingabegröße ändert, kann man jede Funktion in der Informatik einer der folgenden Klassen zuordnen:

O(1)	Die Funktion überschreitet einen konstanten Wert nicht. Die Rechenzeit ist also unabhängig von der verwendeten Eingabegröße, wie zum Beispiel beim Nachschlagen eines Elementes in einem beliebig großen Array.
O(log x)	Wenn sich das Argument verdoppelt, wächst die Funktion um einen konstanten Betrag. Zum Beispiel bei einer binären Suche in einem bereits sortierten Feld.
O(√x)	Die Funktion wächst wie die Wurzelfunktion und damit auf ungefähr das doppelte, wenn sich das Argument vervierfacht.
O(x)	Das Wachstum ist linear. Wenn sich das Argument verdoppelt, verdoppelt sich auch die Funktion. Zum Beispiel bei der linearen Suche in einem unsortierten Feld.
O(xlogx)	Das Wachstum ist super-linear, wie zum Beispiel bei besseren Suchalgorithmen wie Mergesort.
O(x²)	Das Wachstum ist quadratisch. Wemm sich das Argument verdoppelt, wächst die Funktion um das vierfache, wie zum Beispiel bei einfachen Algoithmen zum Sortieren von Zahlen.
O(2^x)	Die Funktion wächst exponentiell und wächst damit bei einer Erhöhung des Arguments um 1 auf das doppelte.
O(x!)	Das Wachstum ist faktoriell. Die Funktion wächst um das x+1-fache, wenn sich das Argument um 1 erhöht.

Die O-Notation gibt damit quasi eine obere Schranke an, wie viele Operationen maximal nötig sind, wenn man die Funktion verwendet. Gewünscht ist in der Regel eine möglichst kurze Rechenzeit, also idealerweise O(1) oder O(log x), auch wenn dies in der Praxis in den meisten Anwendungsgebieten nicht möglich ist.

Anwendung und Beispiele

Bei der Programmierung eines Projekts sollte man sich immer Gedanken über die O-Notationsklassen der verwendeten Funktionen machen um den entsprechenden Flaschenhals der Anwendung finden zu können.

Wichtig ist dies zum Beispiel in dem folgenden Anwendungsfall: Wenn wir zwei Projekt haben, deren Flaschenhälse bei O(x²) und bei O(2^x) liegen, wird uns in einer Testumgebung mit 5 Nutzern kein sonderlicher Unterschied auffallen. Es wären damit 25 oder 32 Operationen notwendig, was durch einen Computer leicht zu bewältigen ist. Wenn sich nun aber 50 Nutzer anmelden kommen wir schon auf 2.500 bzw 1.125.899.906.842.624 Rechenoperationen. Nicht auszudenken wie schnell das System bei 10.000 Nutzern am Boden liegen würde. Die folgende Tabelle kann dies noch zusätzlich verdeutlichen:

Eingabegröße	1	10	100	1.000
0(log x)	1	2	5	7
0(x)	1	10	100	1.000
O(x²)	1	100	10.000	1.000.000
O(2^x)	1	1024	1,3*10^30	1,1*10^301

Exemplarisch zeigt die Tabelle vier verschiedene O-Notationen mit vier unterschiedlichen Eingabegrößen zwischen 1 und 1.000. Man kann deutlich erkennen, dass bei einer Eingabegröße von 1 die jeweilige Klasse der Funktion noch keine Rolle spielt. Interessant wird es dann aber bei einer zunehmend größer werdenden Eingabegröße. Schon bei einer Größe von 10 und 100 zeigen sich sehr deutliche Effekte. Man möge sich nicht vorstellen wollen, wie lange man am Geldautomaten warten müsste, wenn das Suchen seiner Kontodaten O(2^x) folgen würde. Dementsprechend wichtig ist die Verwendung von guten Algorithmen!