Landau-Symbole
| Inhaltsverzeichnis |
|
2 Beispiele 3 Formale Definition 4 Notationsfallen 5 Anwendung in der Komplexitätstheorie 6 Weblinks |
Geschichte
Der Großbuchstaben "O" (damals eigentlich ein großes Omikron) als Symbol für "Ordnung von" wurde erstmals vom deutschen Zahlentheoretiker Paul Bachmann in seinem 1892 erschienen Buch Analytische Zahlentheorie verwendet. Bekanntgemacht wurde diese Notation durch den ebenfalls deutschen Zahlentheoretiker Edmund Landau, mit dessen Namen sie insbesondere im deutschen Sprachraum heute in Verbindung gebracht wird.Beispiele
Die Landau-Notation wird verwendet, um das asymptotische Verhalten bei Annäherung an einen endlichen oder unendlichen Grenzwert zu beschreiben. Das große O wird verwendet, um eine maximale Größenordnung anzugeben. So gilt beispielsweise nach der Stirling-Formel für das asymptotische Verhalten der Fakultät
für 
.
ist dabei nur eine Konstante und kann für die Abschätzung der Größenordnung vernachlässigt werden.Die Landau-Notation kann auch benutzt werden, um den Fehlerterm einer Approximation zu beschreiben. Beispielsweise besagt
für 
für x Das kleine o wird verwendet, um zu sagen, dass ein Ausdruck vernachlässigbar klein gegenüber dem angegebene Ausdruck ist. Für differenzierbare Funktionen gilt beispielsweise
für 
,
Formale Definition
Groß O und klein o sind die am häufigsten verwendeten Landau-Symbole; darüber hinaus gibt es noch Ω, ω und Θ.
In der folgenden Tabelle bezeichnen f
- Folgen reeller Zahlen, dann ist
und der Grenzwert 
, oder
- reellwertige Funktionen der reellen Zahlen, dann ist
und der Grenzwert aus den erweiterten reellen Zahlen: 
, oder
- reellwertige Funktionen beliebiger topologischer Räume
, dann ist 
und auch der Grenzwert 
. Wichtigster Spezialfall ist dabei 
.
| Notation | Definition | Mathematische Definition |
|---|---|---|
| asymptotische obere Schranke | 
|
| asymptotisch vernachlässigbar | 
|
| asymptotische untere Schranke, 
| 
|
| asymptotisch dominant, 
| 
|
| asymptotisch scharfe Schranke, sowohl als auch
| 
|
Definition mit Quantoren
Äquivalent zur Definition mit Limessymbolen können für einen metrischen Raum X
und 
folgende Definitionen mit Quantoren verwendet werden:
| Notation | 
| 
|
|---|---|---|
|
|  
| 
|
|
|  
| 
|
|
| 
| 
|
|
| 
| 
|
|
|  
| 
|
Analoge Definitionen lassen sich auch für den Fall 
sowie für einseitige Grenzwerte geben.
Notationsfallen
Symbolisches Gleichheitszeichen
Üblicherweise wird in der Mathematik bei der Landau-Notation das Gleichheitszeichen verwendet. Es handelt sich dabei aber um eine rein symbolische Schreibweise und nicht um eine Gleichheitsaussage, auf die beispielsweise die Gesetze der Transitivität oder der Symmetrie anwendbar wäre: In einer Aussage wie 
ist keine Seite der "Gleichung" durch die andere bestimmt. Aus 
und 
folgt nicht, dass 
und 
gleich sind, genausowenig kann man aus 
und 
schließen, dass 
und 
dieselbe Klasse sind oder die eine in der anderen enthalten ist.
Vergessener Grenzwert
Eine weitere Falle besteht darin, dass oft nicht angegeben wird, auf welchen Grenzwert sich das Landausymbol bezieht. Der Grenzwert ist aber wesentlich; so ist beispielsweise
für , nicht aber für den einseitigen Grenzwert 
. Normalerweise wird der betrachtete Grenzwert aber aus dem Zusammenhang klar, sodass hier Mehrdeutigkeiten nur selten auftreten.Anwendung in der Komplexitätstheorie
In der Komplexitätstheorie werden die Landau-Symbole vor allem angewendet, um den (minimalen oder maximalen) Bedarf an Speicher (Platzkomplexität) und Zeit (Zeitkomplexität) bezüglich eines bestimmten Maschinenmodells zu beschreiben.
Normalerweise ist es sehr aufwändig oder ganz unmöglich, für ein Problem L eine Funktion 
anzugeben, die allgemein jeder beliebigen Eingabe für ein Problem die zugehörige Anzahl der Rechenschritte (bzw. der Speicherzellen) zuordnet. Daher begnügt man sich in der Regel damit, statt jede Eingabe einzeln zu erfassen, sich lediglich auf die Eingabelänge n = | w | 
anzugeben.
Daher hat man die Landau-Notation entwickelt, die sich auf das asymptotische Verhalten der Funktion fL beschränkt. Man betrachtet also, in welchen Schranken sich der Rechenaufwand (der Bedarf an Speicher und Rechenzeit) hält, wenn man die Eingabe vergrößert. Das wichtigste Landau-Symbol ist O 
- oft auch 
-, dass eine Konstante c 
existieren, so dass für alle 
gilt: 
. In anderen Worten: Für genügend große Eingabelängen ist der Rechenaufwand 
nicht wesentlich größer - d.h. höchstens um einen konstanten Faktor c 
.
Dabei ist die Funktion f
Die Landau-Symbole erlauben es dadurch, Probleme und Algorithmen nach ihrer Komplexität in Komplexitätsklassen zusammenzufassen.
In der Komplexitätstheorie lassen sich die verschiedenen Probleme und Algorithmen dann folgendermaßen vergleichen: Man kann für Problemstellungen mit 
eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit O 
wird die Form von f 
) auch als die Komplexitätsklasse oder Aufwandsmaß bezeichnet (also z.B. quadratisch). Bei dieser Notation werden, wie die Definitionen der Landau-Symbole 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: Komplexitätstheorie, Grenzwert (Limes), Paul Bachmann, Edmund Landau
Weblinks
- O-Notation auf linux-related.de
- Klein, aber o - Artikel aus der Fachschaftszeitschrift i-mail des Fachbereichs Mathematik/Informatik Halle, Sommersemester 2002
