Landau-Symbole

Kernidee und Grundnotation

Landau-Symbole, auch O-Notation oder englisch big O notation, beschreiben in Mathematik und Informatik das asymptotische Verhalten von Funktionen und Folgen. Asymptotisch bedeutet: Man betrachtet, wie sich eine Größe verhält, wenn sich die Variable einem Grenzwert nähert, zum Beispiel x → ∞ oder x → 0. Dabei werden konstante Faktoren meist nicht berücksichtigt.

Die wichtigsten Symbole vergleichen das Wachstum zweier Funktionen f und g: f ∈ o(g) bedeutet, dass f langsamer wächst als g und gegenüber g vernachlässigbar ist. f ∈ O(g) bedeutet, dass f höchstens genauso schnell wächst wie g; O(g) ist also eine asymptotische obere Schranke. f ∈ Θ(g) bedeutet, dass f genauso schnell wächst wie g; Θ(g) ist eine asymptotisch scharfe Schranke. f ∈ ω(g) bedeutet, dass f schneller wächst als g.

Beim Symbol Ω gibt es zwei verschiedene Bedeutungen. In der analytischen Zahlentheorie bedeutet f = Ω(g), dass f nicht in o(g) liegt, also nicht asymptotisch vernachlässigbar gegenüber g ist. In der Komplexitätstheorie bedeutet f ∈ Ω(g), dass f mindestens genauso schnell wächst wie g, also g ∈ O(f). Diese Doppelverwendung kann zu Verwechslungen führen.

Formale Definitionen

Die Funktionen f und g können Folgen reeller Zahlen sein, dann gilt x ∈ ℕ und der Grenzwert ist a = ∞. Sie können auch reellwertige Funktionen der reellen Zahlen sein, dann gilt x ∈ ℝ und a ∈ ℝ ∪ {−∞,+∞}. Allgemeiner können sie reellwertige Funktionen auf topologischen Räumen (X,𝔗) sein; ein wichtiger Spezialfall ist X = ℝⁿ.

Quantoren und Mengenbeziehungen

Für metrische Räume (X;d), besonders X = ℝ und X = ℕ, lassen sich die Definitionen auch mit Quantoren formulieren. Für x → ∞ bedeutet f ∈ O(g): Es gibt Konstanten C > 0 und x₀ > 0, sodass für alle x > x₀ gilt: |f(x)| ≤ C · |g(x)|. Anschaulich: Ab einem hinreichend großen x bleibt f höchstens ein konstanter Faktor von g.

Für f ∈ o(g) gilt bei x → ∞: Für jedes C > 0 gibt es ein x₀ > 0, sodass für alle x > x₀ gilt: |f(x)| < C · |g(x)|. Für f ∈ Θ(g) gibt es c > 0, C > 0 und x₀ > 0, sodass für alle x > x₀ gilt: c · |g(x)| ≤ |f(x)| ≤ C · |g(x)|. Für f ∈ ω(g) gilt: Für jedes c > 0 gibt es ein x₀ > 0, sodass für alle x > x₀ gilt: c · |g(x)| < |f(x)|.

Für jede Funktion f bezeichnen Ω(f), O(f), Θ(f), o(f) und ω(f) Mengen von Funktionen. Es gelten die Beziehungen Θ(f) ⊆ O(f), Θ(f) ⊆ Ω(f), Θ(f) = O(f) ∩ Ω(f), ω(f) ⊆ Ω(f), o(f) ⊆ O(f) und ∅ = ω(f) ∩ o(f).

Anwendung in der Informatik

In der Informatik werden Landau-Symbole zur Analyse von Algorithmen verwendet. Sie geben an, wie viele Elementarschritte oder Speichereinheiten ein Algorithmus abhängig von der Problemgröße benötigt. Man spricht von Zeitkomplexität und Platzkomplexität. Die Komplexität kann vom Maschinenmodell abhängen; meist nimmt man ein normales Modell an, zum Beispiel eines, das zur Turingmaschine äquivalent ist.

In der Komplexitätstheorie helfen Landau-Symbole, Probleme nach ihrer Schwierigkeit zu klassifizieren. Als „leicht“ gelten Probleme, für die es einen Algorithmus gibt, dessen Laufzeit durch ein Polynom beschränkt werden kann. Als „schwer“ gelten Probleme, für die kein Algorithmus gefunden wurde, der weniger schnell als exponentiell wächst. Man nennt Probleme entsprechend polynomiell oder nicht polynomiell lösbar.

Typische O-Klassen für Laufzeiten sind O(1) für beschränkten Aufwand, etwa das Feststellen, ob eine Binärzahl gerade ist; O(log n) für logarithmisches Wachstum, etwa binäre Suche; O(n) für lineares Wachstum, etwa lineare Suche in einem unsortierten Feld; O(n log n) für vergleichbasierte Sortieralgorithmen wie Mergesort und Heapsort; O(n²) für quadratisches Wachstum, etwa Selectionsort; O(nᵐ) für polynomielles Wachstum; O(2ⁿ) für exponentielles Wachstum, etwa SAT mit erschöpfender Suche; und O(n!) für faktorielles Wachstum, etwa das Problem des Handlungsreisenden mit erschöpfender Suche.

Anwendung bei Grenzwerten

In der Analysis beschreibt die Landau-Notation das Verhalten bei Annäherung an einen endlichen oder unendlichen Grenzwert. Das große O gibt eine maximale Größenordnung an. Nach der Stirlingformel gilt für n → ∞:

n! = √(2πn) · (n/e)ⁿ · (1 + O(1/n)).

Daraus folgt auch n! = O(√n · (n/e)ⁿ) für n → ∞. Der Faktor √(2π) ist nur eine Konstante und wird für die Größenordnung vernachlässigt.

Landau-Symbole können außerdem Fehlerterme von Approximationen beschreiben. Die Aussage eˣ = 1 + x + x²/2 + O(x³) für x → 0 bedeutet, dass der Absolutbetrag des Approximationsfehlers kleiner ist als eine Konstante mal x³, wenn x nahe genug bei 0 liegt. Das kleine o beschreibt einen Fehler, der gegenüber dem angegebenen Ausdruck vernachlässigbar ist: Für differenzierbare Funktionen gilt f(x+h) = f(x) + h f'(x) + o(h) für h → 0. Der Fehler der Tangentenapproximation geht also schneller als linear gegen 0.

Omega und Notationsfallen

Das Ω-Symbol hat zwei verbreitete, aber inkonsistente Definitionen. Hardy und Littlewood führten 1914 f(x) = Ω(g(x)) für x → ∞ mit der Bedeutung limsupₓ→∞ |f(x)/g(x)| > 0 ein. Damit ist f(x) = Ω(g(x)) die Negation von f(x) = o(g(x)). 1916 führten sie außerdem Ω_R und Ω_L ein, später Ω_+ und Ω_− genannt. In der analytischen Zahlentheorie werden Ω, Ω_+, Ω_− und Ω_± weiterhin verwendet; dort schreibt man gewöhnlich f = Ω(g) und nicht f ∈ Ω(g).

Knuth veröffentlichte 1976 eine andere Verwendung: f(x) = Ω(g(x)) ⇔ g(x) = O(f(x)). Diese stärkere Definition passt zu Anwendungen in der Informatik, kann aber wegen der älteren zahlentheoretischen Bedeutung Missverständnisse erzeugen.

Eine wichtige Notationsfalle ist das Gleichheitszeichen. f(x) = O(g(x)) ist keine echte Gleichung, sondern eine symbolische Schreibweise. Formal korrekt ist f(x) ∈ O(g(x)), denn O(g(x)) ist die Menge aller Funktionen, die höchstens so schnell wachsen wie g(x). Eine zweite Falle ist der oft weggelassene Grenzwert: 1/x ∈ o(1/√x) gilt für x → ∞, aber nicht für den einseitigen Grenzwert x ↓ 0.