Landau-Symbole
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
also Funktionen, die die natürlichen Zahlen auf die reellen Zahlen abbilden.
- (gelesen "Groß-Oh"): g wächst ab einem festen n0 bis auf einen konstanten Faktor c höchstens so stark wie f.
- (gelesen "Klein-Oh"): Für alle konstanten Faktoren c gibt es ein n0, ab dem g nicht größer als f wird, d.h. g wächst langsamer als f.
- g wächst mindestens so schnell wie f, da f höchstens so stark wie g wächst.
- g wächst schneller als f, da f langsamer wächst als g.
- 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
2) 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.
Siehe auch: Grenzwert (Limes), Peter Bachmann, Edmund Landau