Zeitkomplexität

Unter der Zeitkomplexität (Platzkomplexität) eines Problems L versteht man die Dauer (den Platzbedarf) einer Rechnung in Abhängigkeit von der Eingabe w. Es ist also i.A. eine Funktion

wobei gL(w) die Anzahl der Rechenschritte (der belegten Speicherzellen) bezeichnet, die benötigt werden, um die Eingabe w für das Problem L zu bearbeiten.

Normalerweise ist es sehr aufwändig oder ganz unmöglich, eine Funktion anzugeben, die allgemein jeder beliebigen Eingabe für ein Problem die zugehörige Anzahl der Rechenschritte (der Speicherzellen) zuordnet. Daher begnügt man sich in der Regel damit, statt jede Eingabe einzeln zu erfassen, sich lediglich mit der Eingabelänge n = |w| zu befassen. Es ist aber meist sogar zu komplex, eine Funktion

anzugeben.

Daher hat man die Landau-Notation entwickelt, die sich auf das asymptotische Verhalten der Funktion fL beschränkt. Man betrachtet also, in welchen Schranken sich der Rechenaufwand (der Platzbedarf) hält, wenn man die Eingabe vergrößert. Das wichtigste Landau-Symbol ist 'O', mit dem man obere Schranken angeben kann (untere Schranken zu finden ist im allgemeinen viel schwieriger). Dabei meint

- oft auch

Anm.: die Funktion f ist nicht immer bekannt! Die Landau-Notation ist ja gerade dazu da, den Rechenaufwand (Platzbedarf) abzuschätzen, wenn es zu aufwändig ist, die genaue Funktion anzugeben. Umgekehrt ist es sinnlos, eine Landau-Abschätzung durchzuführen, wenn man eine genaue Funktion f bereits gefunden hat - es sei denn, weil die abschätztung naturgemäß vereinfachend ist, da bspw. Konstanten wegfallen.