Landau-Symbole

Landau-Symbole werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie insbesondere in der Komplexitätstheorie verwendet, um verschiedene Probleme und Algorithmen danach zu vergleichen, wie "schwierig" oder aufwendig sie zu berechnen sind.

Geschichte

Der Großbuchstabe "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
n!=O(2πn (ne)n)n! = \text{O} \braceNT{ \sqrt{2 \pi n} \, \braceNT{\dfrac{n}{e}}^{n}} für n→∞n\to \infty.
Der Faktor 2π\sqrt{2\pi} 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
ex=1+x+x2/2+O(x3)e^x=1+x+x^2/2+\text{O}(x^3)\qquad für x→0x\to 0
dass der Absolutbetrag des Approximationsfehler kleiner als eine Konstante mal x3x^3 für xx hinreichend nahe bei Null.
Das kleine o wird verwendet, um zu sagen, dass ein Ausdruck vernachlässigbar klein gegenüber dem angegebenen Ausdruck ist. Für differenzierbare Funktionen gilt beispielsweise
f(x+h)=f(x)+hf′(x)+o(h)f(x+h)=f(x)+hf'(x)+\text{o}(h)\qquad für h→0h\to 0,
der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen 0.
 
 

Seit die Mathematiker über die Relativitätstheorie hergefallen sind, verstehe ich sie selbst nicht mehr.

Albert Einstein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Landau-Symbole aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Reelle Funktionen