Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 16. Juli 2020 

Landau-Symbole


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Landau-Symbole beschreiben Mengen von Funktionen die ähnliches Wachstumsverhalten haben. Sie werden insbesondere in der Komplexitätstheorie verwendet. Die hier beschriebene heute verwendete wurde von Donald E. Knuth definiert.

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 0 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 0 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 2 ) 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.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Landau-Symbole.html">Landau-Symbole </a>