Anwendung in der Komplexitätstheorie

In der Komplexitätstheorie werden die Landau-Symbole vor allem angewendet, um den (minimalen oder maximalen) Bedarf an Speicher (Platzkomplexität) und Zeit (Zeitkomplexität) bezüglich eines bestimmten Maschinenmodells zu beschreiben.

Normalerweise ist es sehr aufwändig oder ganz unmöglich, für ein Problem L eine Funktion $f_L: w \rightarrow f_L(w)$ anzugeben, die allgemein jeder beliebigen Eingabe für ein Problem die zugehörige Anzahl der Rechenschritte (bzw. der Speicherzellen) zuordnet. Daher begnügt man sich in der Regel damit, statt jede Eingabe einzeln zu erfassen, sich lediglich auf die Eingabelänge $n = |w|$ zu beschränken. Es ist aber meist ebenfalls zu aufwändig, eine Funktion $f_L: n \rightarrow f_L(n), n = |w|$ anzugeben.

Daher hat man die Landau-Notation entwickelt, die sich auf das asymptotische Verhalten der Funktion $f_{L}$ beschränkt. Man betrachtet also, in welchen Schranken sich der Rechenaufwand (der Bedarf an Speicher und Rechenzeit) hält, wenn man die Eingabe vergrößert. Das wichtigste Landau-Symbol ist $\mathrm{O}$ (großer lateinischer Buchstabe O), mit dem man obere Schranken angeben kann; untere Schranken zu finden ist im allgemeinen viel schwieriger. Dabei meint $f(n) \in \mathrm{O}(g(n))$ – oft auch $f(n)=\mathrm{O}(g(n))$ –, dass eine Konstante $c$ und ein $n_0 \in N$ existieren, so dass für alle $n > n_0$ gilt: $f(n) \le c\cdot g(n)$. In anderen Worten: Für genügend große Eingabelängen ist der Rechenaufwand $f(n)$ nicht wesentlich größer – d.h. höchstens um einen konstanten Faktor $c$ – als $g(n)$.

Dabei ist die Funktion $f$ nicht immer bekannt: Die Landau-Notation ist 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ätzung naturgemäß vereinfachend ist, da beispielsweise Konstanten wegfallen.

Die Landau-Symbole erlauben es dadurch, Probleme und Algorithmen nach ihrer Komplexität in Komplexitätsklassen zusammenzufassen.

In der Komplexitätstheorie lassen sich die verschiedenen Probleme und Algorithmen dann folgendermaßen vergleichen: Man kann für Problemstellungen mit $\Omega$ eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit $\mathrm{O}$ entsprechend eine obere Schranke. Bei $\mathrm{O}(f)$ wird die Form von $f$ (z.B. $f(n)=n^2$) auch als die Komplexitätsklasse oder Aufwandsmaß bezeichnet (also z.B. quadratisch). Bei dieser Notation werden, wie die Definitionen der Landau-Symbole zeigen, konstante Faktoren vernachlässigt. Dies ist gerechtfertigt, da die Konstanten zu großen Teilen vom verwendeten Maschinenmodell bzw. bei implementierten Algorithmen von der Qualität des Compilers und diversen Eigenschaften der Hardware des ausführenden Computer abhängig sind. Damit können sie nicht direkt mit der Laufzeit des Algorithmus in Verbindung gebracht werden.