Landau-Symbole

Die Landau-Symbole beschreiben Mengen von Funktionen, die ähnliches Wachstumsverhalten haben. Sie werden insbesondere in der Komplexitätstheorie verwendet.

Seien $f,g:\mathbb {N} \rightarrow \mathbb {R} ,$ also Funktionen, die die natürlichen Zahlen auf die reellen Zahlen abbilden.

$g\in O(f)\Leftrightarrow \exists \ c>0\ \exists \ n_{0}>0\ \forall \ n\geq n_{0}:g(n)\leq c\cdot f(n)$

(gelesen "Groß-Oh"): g wächst ab einem festen n₀ bis auf einen konstanten Faktor c höchstens so stark wie f.

$g\in o(f)\Leftrightarrow \forall \ c>0\ \exists \ n_{0}>0\ \forall \ n\geq n_{0}:g(n)\leq c\cdot f(n)$

(gelesen "Klein-Oh"): Für alle konstanten Faktoren c gibt es ein n₀, ab dem g nicht größer als f wird, d.h. g wächst langsamer als f.

$g\in \Omega (f)\Leftrightarrow f\in O(g)$

g wächst mindestens so schnell wie f, da f höchstens so stark wie g wächst.

$g\in \omega (f)\Leftrightarrow f\in o(g)$

g wächst schneller als f, da f langsamer wächst als g.

$g\in \Theta (f)\Leftrightarrow f\in O(g)\wedge g\in O(f)$

f und g wachsen gleich schnell.

In der Komplexitätstheorie lassen sich so verschiedene Probleme und Algorithmen vergleichen. So kann man für Problemstellungen mit Ω eine untere Schranke für beispielsweise die Laufzeit angeben, für Algorithmen mit O entsprechend eine obere Schranke. Bei O(f) wird die Form von f (z.B. f=n²) auch als die Aufwandsklasse oder Aufwandsmaß bezeichnet (also z.B. quadratisch).

Siehe auch: Grenzwert (Limes), Peter Bachmann, Edmund Landau