Landau-Symbole - Definition und Bedeutung

Sie haben im Ilexikon erfolgreich nach der Definition, der Bedeutung oder Informationen zum Begriff 'Landau-Symbole' gesucht. Hier finden Sie eine Beschreibung, Erklärung, Definition, die Bedeutung sowie viele aktuelle Infos zum Begriff 'Landau-Symbole' und damit verwandten Themen.

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 speziell 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 zum Beispiel die asymptotische Laufzeit angeben, mit O entsprechend eine obere Schranke. Bei O(f) wird die Form von f (z.B. f(n)=n²) ebenso als die Aufwandsklasse oder Aufwandsmaß bezeichnet (also z.B. quadratisch). Bei dieser Notation werden, wie die Definitionen der Landau-Symbole ja ebenso 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 ebenso: Grenzwert (Limes), Peter Bachmann, Edmund Landau

Infos zu Ilexikon.com

Wir hoffen dass Sie alle gewünschten Informationen zum Begriff 'Landau-Symbole' gefunden haben. Alle Informationen zur Definition des Begriffs Landau-Symbole und zur Bedeutung des Wortes Landau-Symbole werden Ihnen kostenlos bereitgestellt. Unser Traffic und unsere Programmierarbeit finanziert sich ausschließlich durch Werbeeinnahmen. Wir danken für Ihren Besuch und hoffen dass Sie unser Portal zusätzlichempfehlen.

Weiteres zu dem Artikel

Sie möchten die Besucher Ihrer Internet-Seite auf weiterführende Definitionen und Informationen zum
Thema "Landau-Symbole" aufmerksam machen? Dann platzieren Sie doch einfach folgenden Link auf Ihre Homepage:

<a href="http://www.ilexikon.com/O-Notation.html" title="Definition und Informationen zu dem Thema Landau-Symbole">Landau-Symbole</a>