Landau-Symbole

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

Seien f,g: N → R, also Funktionen, die die natürlichen Zahlen auf die reellen Zahlen abbilden.

g ∈ O(f) ⇔ ∃ c>0 ∃ n₀>0 ∀ n≥n₀: g(n) ≤ c*f(n)

g wächst ab einem festen n₀ bis auf einen konstanten Faktor c höchstens so stark wie f.

g ∈ o(f) ⇔ ∀ c>0 ∃ n₀>0 ∀ n≥n₀: g(n) ≤ c*f(n)

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 ∈ Ω(f) ⇔ f ∈ O(g)

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

g ∈ ω(f) ⇔ f ∈ o(g)

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

g ∈ Θ(f) ⇔ f ∈ O(g) ∧ g ∈ 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.

Siehe auch: Grenzwert (Mathematik), limes