O-Notation

Einführung

Die Laufzeit eines Algorithmus meint die Art des Wachstums der Zuordnungsfunktion:

Laufzeit --> Eingabegröße (siehe Grafik)

In der Informatik interessiert dabei nicht die exakte Funktionvorschrift, sondern nur die "Größenordnung" in Form der höchsten Potenz. Die Notation hierfür nennt sich O-Notation (oder: Landau-Notation).

Das Laufzeitverhalten von Algorithmen erschließt sich über die Anzahl der Kernoperationen. Kernoperationen sind Operationen, die einen für die Laufzeit charakteristischen Arbeitsschritt beschreiben.

Beispiele