Landau-Symbole

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

<math>g \in O(f) \Leftrightarrow \exists\ c>0\ n_0>0\ \forall\ n \ge n_0: g(n) \le \cdot f(n)</math>

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

<math>g \in o(f) \Leftrightarrow \forall\ c>0\ n_0>0\ \forall\ n \ge n_0: g(n) < \cdot f(n)</math>

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

<math>g \in \Omega(f) \Leftrightarrow f \in

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

<math>g \in \omega(f) \Leftrightarrow f \in

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

<math>g \in \Theta(f) \Leftrightarrow f \in \wedge g \in O(f)</math>

f und g wachsen gleich schnell.

In der Komplexitätstheorie lassen sich so Probleme und Algorithmen vergleichen. So kann man Problemstellungen mit Ω eine untere Schranke für die asymptotische Laufzeit angeben mit O entsprechend eine obere Bei O(f) wird die Form von f f=n ² ) auch als die Aufwandsklasse oder Aufwandsmaß bezeichnet (also z.B. quadratisch). dieser Notation werden wie die Definitionen der ja auch zeigen konstante Faktoren vernachlässigt. Dies gerechtfertigt da die Konstanten zu großen Teilen 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 mit der Laufzeit des Algorithmus in Verbindung werden.

Siehe auch: Grenzwert (Limes) Peter Bachmann Edmund Landau

Bücher zum Thema Landau-Symbole

Dieser Artikel von Wikipedia unterliegt der GNU FDL.