Mathe Genie Lexikon Landau-Symbole Erklärung Bedeutung und Formel

Landau-Symbole

Dieser Artikel enthält mathematische Symbole. Diese werden in der Tabelle mit mathematischen Symbolen erläutert.

Die Landau-Symbole beschreiben Mengen von Funktionen, die ähnliches Wachstumsverhalten haben. Sie werden insbesondere in der Komplexitätstheorie verwendet. Die hier beschriebene heute verwendete Form wurde von Donald E. Knuth definiert.

Es 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 \ge n_0: g(n) \le 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 \ge n_0: g(n) < 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 asymptotische Laufzeit angeben, mit O entsprechend eine obere Schranke. Bei O(f) wird die Form von f (z.B. f(n)=n²) auch als die Aufwandsklasse oder Aufwandsmaß bezeichnet (also z.B. quadratisch). Bei dieser Notation werden, wie die Definitionen der Landau-Symbole ja auch 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.

Weblinks:

O-Notation auf linux-related.de (http://www.linux-related.de/coding/o-notation.htm)

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

Dieser Artikel ( Landau-Symbole ) stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence.