fbpx
Wikipedia

Landau-Symbole

Landau-Symbole (auch O-Notation,englischbig O notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. Die Komplexitätstheorie verwendet sie, um Probleme danach zu klassifizieren, wie „schwierig“ oder aufwändig sie zu lösen sind. Zu „leichten“ Problemen existiert ein Algorithmus, dessen Laufzeit sich durch ein Polynom beschränken lässt; als „schwer“ gelten Probleme, für die man keinen Algorithmus gefunden hat, der weniger schnell als exponentiell wächst. Man nennt sie (nicht) polynomiell lösbar.

Notation Anschauliche Bedeutung
f = o ( g ) {\displaystyle f=o(g)}

oder

f O ( g ) {\displaystyle f\in {\begin{smallmatrix}\!{\mathcal {O}}\!\end{smallmatrix}}(g)}

f {\displaystyle f} wächst langsamer als g {\displaystyle g}
f = O ( g ) {\displaystyle f=O(g)}

oder

f O ( g ) {\displaystyle f\in {\mathcal {O}}(g)}

f {\displaystyle f} wächst nicht wesentlich schneller als g {\displaystyle g}
f Θ ( g ) {\displaystyle f\in \Theta (g)} f {\displaystyle f} wächst genauso schnell wie g {\displaystyle g}
f = Ω ( g ) {\displaystyle f=\Omega (g)} f {\displaystyle f} wächst nicht immer langsamer als g {\displaystyle g} (Zahlentheorie)
f Ω ( g ) {\displaystyle f\in \Omega (g)} f {\displaystyle f} wächst nicht wesentlich langsamer als g {\displaystyle g} (Komplexitätstheorie)
f ω ( g ) {\displaystyle f\in \omega (g)} f {\displaystyle f} wächst schneller als g {\displaystyle g}

Inhaltsverzeichnis

Erstmals drückte der deutsche Zahlentheoretiker Paul Bachmann 1894 „durch das Zeichen O ( n ) {\displaystyle O(n)} eine Grösse aus […], deren Ordnung in Bezug auf n {\displaystyle n} die Ordnung von n {\displaystyle n} nicht überschreitet […].“ Der ebenfalls deutsche Zahlentheoretiker Edmund Landau, durch den die O {\displaystyle O} - und o {\displaystyle o} -Symbolik bekannt wurde und mit dessen Namen sie insbesondere im deutschen Sprachraum heute verbunden ist, übernahm Bachmanns Bezeichnung und führte zudem die o {\displaystyle o} -Bezeichnung für „von kleiner Ordnung“ ein.

Zwei unvereinbare Definitionen

Es gibt in der Mathematik zwei sehr häufige und inkonsistente Definitionen für

f ( x ) = Ω ( g ( x ) ) ( x a ) , {\displaystyle f(x)=\Omega (g(x))\ (x\rightarrow a),}

wobei a {\displaystyle a} eine reelle Zahl, {\displaystyle \infty } oder {\displaystyle -\infty } ist, wo die reellen Funktionen f {\displaystyle f} und g {\displaystyle g} auf einer Umgebung von a {\displaystyle a} definiert sind und g {\displaystyle g} in dieser Umgebung positiv ist.

Die erste wird in der analytischen Zahlentheorie benutzt und die andere in der Komplexitätstheorie. Diese Situation kann zu Verwechslungen führen.

Die Hardy-Littlewoodsche Definition

Im Jahr 1914 führten Godfrey Harold Hardy und John Edensor Littlewood das Symbol Ω {\displaystyle \Omega } mit der Bedeutung

f ( x ) = Ω ( g ( x ) ) ( x ) lim sup x | f ( x ) g ( x ) | > 0 {\displaystyle f(x)=\Omega (g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0}

ein. Also ist f ( x ) = Ω ( g ( x ) ) {\displaystyle f(x)=\Omega (g(x))} die Negation von f ( x ) = o ( g ( x ) ) {\displaystyle f(x)=o(g(x))} .

Im Jahr 1916 führten dieselben Verfasser zwei neue Symbole Ω R {\displaystyle \Omega _{R}} und Ω L {\displaystyle \Omega _{L}} mit den Bedeutungen

f ( x ) = Ω R ( g ( x ) ) ( x ) lim sup x f ( x ) g ( x ) > 0 {\displaystyle f(x)=\Omega _{R}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0} ;
f ( x ) = Ω L ( g ( x ) ) ( x ) lim inf x f ( x ) g ( x ) < 0 {\displaystyle f(x)=\Omega _{L}(g(x))\ (x\rightarrow \infty )\;\Leftrightarrow \;\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0}

ein. Also ist f ( x ) = Ω R ( g ( x ) ) {\displaystyle f(x)=\Omega _{R}(g(x))} die Negation von f ( x ) < o ( g ( x ) ) {\displaystyle f(x)<o(g(x))} und f ( x ) = Ω L ( g ( x ) ) {\displaystyle f(x)=\Omega _{L}(g(x))} die Negation von f ( x ) > o ( g ( x ) ) {\displaystyle f(x)>o(g(x))} .

Im Gegensatz zu einer späteren Aussage von Donald E. Knuth verwendete Landau diese drei Symbole im Jahre 1924 mit den gleichen Bedeutungen.

Diese Hardy-Littlewood-Symbole sind Prototypen, sie werden nie genau so verwendet. Ω R {\displaystyle \Omega _{R}} ist zu Ω + {\displaystyle \Omega _{+}} und Ω L {\displaystyle \Omega _{L}} zu Ω {\displaystyle \Omega _{-}} geworden.

Diese drei Symbole Ω , Ω + , Ω {\displaystyle \Omega ,\Omega _{+},\Omega _{-}} sowie f ( x ) = Ω ± ( g ( x ) ) {\displaystyle f(x)=\Omega _{\pm }(g(x))} (dies bedeutet, dass die beiden Eigenschaften f ( x ) = Ω + ( g ( x ) ) {\displaystyle f(x)=\Omega _{+}(g(x))} und f ( x ) = Ω ( g ( x ) ) {\displaystyle f(x)=\Omega _{-}(g(x))} erfüllt sind) werden heute noch systematisch in der analytischen Zahlentheorie verwendet.

Einfache Beispiele

Wir haben

sin x = Ω ( 1 ) ( x ) {\displaystyle \sin x=\Omega (1)\ (x\rightarrow \infty )}

und speziell

sin x = Ω ± ( 1 ) ( x ) . {\displaystyle \sin x=\Omega _{\pm }(1)\ (x\rightarrow \infty ).}

Wir haben

sin x + 1 = Ω ( 1 ) ( x ) {\displaystyle \sin x+1=\Omega (1)\ (x\rightarrow \infty )}

und speziell

sin x + 1 = Ω + ( 1 ) ( x ) {\displaystyle \sin x+1=\Omega _{+}(1)\ (x\rightarrow \infty )}

aber

sin x + 1 Ω ( 1 ) ( x ) . {\displaystyle \sin x+1\not =\Omega _{-}(1)\ (x\rightarrow \infty ).}

Zahlentheoretische Notation

Die strenge Notation f Ω ( g ) {\displaystyle f\in \Omega (g)} wird in der Zahlentheorie nie benutzt und man schreibt weniger streng immer f = Ω ( g ) {\displaystyle f=\Omega (g)} . Dies bedeutet hier „ f {\displaystyle f} ist ein Omega von g {\displaystyle g} “.

Die Knuthsche Definition

Im Jahr 1976 veröffentlichte Donald E. Knuth einen Artikel, dessen Hauptziel es ist, eine andere Verwendung des Ω {\displaystyle \Omega } -Symbols zu rechtfertigen. Er bemüht sich, seine Leser zu überzeugen, dass, abgesehen von einigen älteren Werken (wie dem 1951 erschienenen Buch von Edward C. Titchmarsh), die Hardy-Littlewoodsche Definition fast nie benutzt wird. Er schreibt, dass er bei Landau keine Anwendung finden konnte und dass George Pólya, der bei Landau studierte, die Einschätzung bestätigte, dass Landau das Ω {\displaystyle \Omega } -Symbol wohl nicht verwendet hat (tatsächlich findet sich eine Nutzung in einer Abhandlung von 1924). Knuth schreibt: „For all the applications I have seen so far in computer science, a stronger requirement […] is much more appropriate.“ Er verwendet das Symbol Ω {\displaystyle \Omega } , um diese stärkere Anforderung zu beschreiben: „Unfortunately, Hardy and Littlewood didn’t define Ω ( f ( n ) ) {\displaystyle \Omega (f(n))} as I wanted to.“

Unter der Gefahr von Missverständnissen und Verwirrung definiert er auch

f ( x ) = Ω ( g ( x ) ) g ( x ) = O ( f ( x ) ) {\displaystyle f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))} .

In der folgenden Tabelle bezeichnen f {\displaystyle f} und g {\displaystyle g} entweder

  • Folgen reeller Zahlen, dann ist x N {\displaystyle x\in \mathbb {N} } und der Grenzwert a = {\displaystyle a=\infty } , oder
  • reellwertige Funktionen der reellen Zahlen, dann ist x R {\displaystyle x\in \mathbb {R} } und der Grenzwert aus den erweiterten reellen Zahlen: a R { , + } {\displaystyle a\in \mathbb {R} \cup \lbrace -\infty ,+\infty \rbrace } , oder
  • reellwertige Funktionen beliebiger topologischer Räume ( X , T ) {\displaystyle (X,{\mathfrak {T}})} , dann ist x X {\displaystyle x\in X} und auch der Grenzwert a X {\displaystyle a\in X} . Wichtigster Spezialfall ist dabei X = R n {\displaystyle X=\mathbb {R} ^{n}} .

Formal lassen sich die Landau-Symbole dann mittels Limes superior und Limes inferior folgendermaßen definieren:

Notation Definition Mathematische Definition
f o ( g ) {\displaystyle f\in o(g)} asymptotisch gegenüber g {\displaystyle g} vernachlässigbar lim x a | f ( x ) g ( x ) | = 0 {\displaystyle \lim _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|=0}
f O ( g ) {\displaystyle f\in {\mathcal {O}}(g)} asymptotische obere Schranke lim sup x a | f ( x ) g ( x ) | < {\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }
f = Ω ( g ) {\displaystyle f=\Omega (g)} (Zahlentheorie) asymptotische untere Schranke, f {\displaystyle f} ist nicht in o ( g ) {\displaystyle o(g)} lim sup x a | f ( x ) g ( x ) | > 0 {\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|>0}
f Ω ( g ) {\displaystyle f\in \Omega (g)} (Komplexitätstheorie) asymptotische untere Schranke, g O ( f ) {\displaystyle g\in {\mathcal {O}}(f)} lim inf x a | f ( x ) g ( x ) | > 0 {\displaystyle \liminf _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|>0}
f Θ ( g ) {\displaystyle f\in \Theta (g)} asymptotisch scharfe Schranke, sowohl f O ( g ) {\displaystyle f\in {\mathcal {O}}(g)} als auch f Ω ( g ) {\displaystyle f\in \Omega (g)} 0 < lim inf x a | f ( x ) g ( x ) | lim sup x a | f ( x ) g ( x ) | < {\displaystyle 0<\liminf _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|\leq \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }
f ω ( g ) {\displaystyle f\in \omega (g)} asymptotisch dominant, g o ( f ) {\displaystyle g\in o(f)} lim x a | f ( x ) g ( x ) | = {\displaystyle \lim _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|=\infty }

In der Praxis existieren meist die Grenzwerte lim f ( x ) g ( x ) {\displaystyle \lim {\tfrac {f(x)}{g(x)}}} , sodass die Abschätzung des limes superior oft durch die (einfachere) Berechnung eines Grenzwerts ersetzt werden kann.

Äquivalent zur Definition mit Limessymbolen können für einen metrischen Raum ( X ; d ) {\displaystyle (X;d)} , insbesondere also für die Fälle X = R {\displaystyle X=\mathbb {R} } und X = N {\displaystyle X=\mathbb {N} } , folgende Definitionen mit Quantoren verwendet werden:

Notation x a < {\displaystyle x\to a<\infty }
f o ( g ) {\displaystyle f\in o(g)} C > 0 ε > 0 x { x : d ( x , a ) < ε } : | f ( x ) | < C | g ( x ) | {\displaystyle \forall \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :|f(x)|<C\cdot |g(x)|}
f O ( g ) {\displaystyle f\in {\mathcal {O}}(g)} C > 0 ε > 0 x { x : d ( x , a ) < ε } : | f ( x ) | C | g ( x ) | {\displaystyle \exists \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :|f(x)|\leq C\cdot |g(x)|}
f = Ω ( g ) {\displaystyle f=\Omega (g)} (Zahlentheorie) c > 0 ε > 0 x { x : d ( x , a ) < ε } : c | g ( x ) | | f ( x ) | {\displaystyle \exists \ c>0\ \forall \ \varepsilon >0\ \exists \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)|}
f Ω ( g ) {\displaystyle f\in \Omega (g)} (Komplexitätstheorie) c > 0 ε > 0 x { x : d ( x , a ) < ε } : c | g ( x ) | | f ( x ) | {\displaystyle \exists \ c>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)|}
f Θ ( g ) {\displaystyle f\in \Theta (g)} c > 0 C > 0 ε > 0 x { x : d ( x , a ) < ε } : c | g ( x ) | | f ( x ) | C | g ( x ) | {\displaystyle \exists \ c>0\ \exists \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)|\leq C\cdot |g(x)|}
f ω ( g ) {\displaystyle f\in \omega (g)} c > 0 ε > 0 x { x : d ( x , a ) < ε } : c | g ( x ) | | f ( x ) | {\displaystyle \forall \ c>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)|}
Notation x {\displaystyle x\to \infty }
f o ( g ) {\displaystyle f\in o(g)} C > 0 x 0 > 0 x > x 0 : | f ( x ) | < C | g ( x ) | {\displaystyle \forall \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|<C\cdot |g(x)|}
f O ( g ) {\displaystyle f\in {\mathcal {O}}(g)} C > 0 x 0 > 0 x > x 0 : | f ( x ) | C | g ( x ) | {\displaystyle \exists \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|\leq C\cdot |g(x)|}
f = Ω ( g ) {\displaystyle f=\Omega (g)} (Zahlentheorie) c > 0 x 0 > 0 x > x 0 : c g ( x ) | f ( x ) | {\displaystyle \exists \ c>0\ \forall \ x_{0}>0\ \exists \ x>x_{0}:c\cdot g(x)\leq |f(x)|} (die Test-Funktion g ist immer positiv)
f Ω ( g ) {\displaystyle f\in \Omega (g)} (Komplexitätstheorie) c > 0 x 0 > 0 x > x 0 : c | g ( x ) | | f ( x ) | {\displaystyle \exists \ c>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:c\cdot |g(x)|\leq |f(x)|}
f Θ ( g ) {\displaystyle f\in \Theta (g)} c > 0 C > 0 x 0 > 0 x > x 0 : c | g ( x ) | | f ( x ) | C | g ( x ) | {\displaystyle \exists \ c>0\ \exists \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:c\cdot |g(x)|\leq |f(x)|\leq C\cdot |g(x)|}
f ω ( g ) {\displaystyle f\in \omega (g)} c > 0 x 0 > 0 x > x 0 : c | g ( x ) | < | f ( x ) | {\displaystyle \forall \ c>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:c\cdot |g(x)|<|f(x)|}

Analoge Definitionen lassen sich auch für den Fall x {\displaystyle x\to -\infty } sowie für einseitige Grenzwerte geben.

Für jede Funktion f {\displaystyle f} werden durch

Ω ( f ) , O ( f ) , Θ ( f ) , o ( f ) , ω ( f ) {\displaystyle \Omega (f),{\mathcal {O}}(f),\Theta (f),o(f),\omega (f)}

jeweils Mengen von Funktionen beschrieben. Es gelten folgende Beziehungen zwischen diesen:

Θ ( f ) O ( f ) Θ ( f ) Ω ( f ) Θ ( f ) = O ( f ) Ω ( f ) ω ( f ) Ω ( f ) o ( f ) O ( f ) = ω ( f ) o ( f ) {\displaystyle {\begin{aligned}\Theta (f)&\subseteq {\mathcal {O}}(f)\\\Theta (f)&\subseteq \Omega (f)\\\Theta (f)&={\mathcal {O}}(f)\cap \Omega (f)\\\omega (f)&\subseteq \Omega (f)\\o(f)&\subseteq {\mathcal {O}}(f)\\\emptyset \,&=\,\omega (f)\cap o(f)\end{aligned}}}

Bei der Verwendung der Landau-Symbole wird die darin verwendete Funktion häufig verkürzt angegeben. Statt zum Beispiel O ( g ) mit g : R R , n n 3 {\displaystyle {\mathcal {O}}(g){\text{ mit }}g\colon \mathbb {R} \to \mathbb {R} ,n\mapsto n^{3}} schreibt man häufig verkürzend O ( n 3 ) . {\displaystyle {\mathcal {O}}(n^{3}).} Dies wird auch in den folgenden Beispielen so gehandhabt.

Die Beispiele in der Tabelle enthalten allesamt monoton wachsende Vergleichsfunktionen g {\displaystyle g} , bei denen es auf ihr Verhalten bei n {\displaystyle n\to \infty } ankommt. (Als Name des Arguments wird gerne n {\displaystyle n} genommen – oft ohne eine Erläuterung, weil es sich sehr häufig um eine Anzahl handelt.) Sie sind in dieser Hinsicht aufsteigend geordnet, d. h. die Komplexitätsklassen sind enthalten in denen, die in Zeilen darunter stehen.

Notation Bedeutung Anschauliche Erklärung Beispiele für Laufzeiten
f O ( 1 ) {\displaystyle f\in {\mathcal {O}}(1)} f {\displaystyle f} ist beschränkt. f {\displaystyle f} überschreitet einen konstanten Wert nicht (ist unabhängig vom Wert des Arguments n {\displaystyle n} ). Feststellen, ob eine Binärzahl gerade ist
Nachschlagen des n {\displaystyle n} -ten Elementes in einem Feld in einer Registermaschine
f O ( log log n ) {\displaystyle f\in {\mathcal {O}}(\log \log n)} f {\displaystyle f} wächst doppel-logarithmisch. Bei Basis 2 erhöht sich f {\displaystyle f} um 1, wenn n {\displaystyle n} quadriert wird. Interpolationssuche im sortierten Feld mit n {\displaystyle n} gleichförmig verteilten Einträgen
f O ( log n ) {\displaystyle f\in {\mathcal {O}}(\log n)} f {\displaystyle f} wächst logarithmisch. f {\displaystyle f} wächst ungefähr um einen konstanten Betrag, wenn sich n {\displaystyle n} verdoppelt.
Die Basis des Logarithmus ist dabei egal.
Binäre Suche im sortierten Feld mit n {\displaystyle n} Einträgen
f O ( n ) {\displaystyle f\in {\mathcal {O}}({\sqrt {n}})} f {\displaystyle f} wächst wie die Wurzelfunktion. f {\displaystyle f} wächst ungefähr auf das Doppelte, wenn sich n {\displaystyle n} vervierfacht. Anzahl der Divisionen des naiven Primzahltests (Teilen durch jede ganze Zahl n {\displaystyle \leq {\sqrt {n}}} )
f O ( n ) {\displaystyle f\in {\mathcal {O}}(n)} f {\displaystyle f} wächst linear. f {\displaystyle f} wächst ungefähr auf das Doppelte, wenn sich n {\displaystyle n} verdoppelt. Suche im unsortierten Feld mit n {\displaystyle n} Einträgen (Bsp. Lineare Suche)
f O ( n log n ) {\displaystyle f\in {\mathcal {O}}(n\log n)} f {\displaystyle f} hat super-lineares Wachstum. Vergleichbasierte Algorithmen zum Sortieren von n {\displaystyle n} Zahlen

Mergesort, Heapsort

f O ( n 2 ) {\displaystyle f\in {\mathcal {O}}(n^{2})} f {\displaystyle f} wächst quadratisch. f {\displaystyle f} wächst ungefähr auf das Vierfache, wenn sich n {\displaystyle n} verdoppelt. Einfache Algorithmen zum Sortieren von n {\displaystyle n} Zahlen

Selectionsort

f O ( n m ) {\displaystyle f\in {\mathcal {O}}(n^{m})} f {\displaystyle f} wächst polynomiell. f {\displaystyle f} wächst ungefähr auf das 2 m {\displaystyle 2^{m}} -Fache, wenn sich n {\displaystyle n} verdoppelt. „Einfache“ Algorithmen
f O ( 2 n ) {\displaystyle f\in {\mathcal {O}}(2^{n})} f {\displaystyle f} wächst exponentiell. f {\displaystyle f} wächst ungefähr auf das Doppelte, wenn sich n {\displaystyle n} um 1 erhöht. Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels erschöpfender Suche
f O ( n ! ) {\displaystyle f\in {\mathcal {O}}(n!)} f {\displaystyle f} wächst faktoriell. f {\displaystyle f} wächst ungefähr auf das ( n + 1 ) {\displaystyle (n+1)} -Fache, wenn sich n {\displaystyle n} um 1 erhöht. Problem des Handlungsreisenden (mit erschöpfender Suche)
f A ( n ) {\displaystyle f\in A(n)} f {\displaystyle f} wächst wie die modifizierte Ackermannfunktion. Problem ist berechenbar, aber nicht notwendig primitiv-rekursiv

Die Landau-Notation wird verwendet, um das asymptotische Verhalten bei Annäherung an einen endlichen oder unendlichen Grenzwert zu beschreiben. Das große O {\displaystyle {\mathcal {O}}} wird verwendet, um eine maximale Größenordnung anzugeben. So gilt beispielsweise nach der Stirlingformel für das asymptotische Verhalten der Fakultät

n ! = 2 π n ( n e ) n ( 1 + O ( 1 n ) ) {\displaystyle n!={\sqrt {2\pi n}}~{\left({\frac {n}{e}}\right)}^{n}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)} für n {\displaystyle n\to \infty }

und

n ! = O ( n ( n e ) n ) {\displaystyle n!={\mathcal {O}}\left({\sqrt {n}}\cdot \left({\frac {n}{e}}\right)^{n}\right)} für n {\displaystyle n\to \infty } .

Der Faktor 2 π {\displaystyle {\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

e x = 1 + x + x 2 / 2 + O ( x 3 ) {\displaystyle e^{x}=1+x+x^{2}/2+{\mathcal {O}}(x^{3})\qquad } für x 0 {\displaystyle x\to 0} ,

dass der Absolutbetrag des Approximationsfehlers kleiner als eine Konstante mal x 3 {\displaystyle x^{3}} für x {\displaystyle x} hinreichend nahe bei Null ist.

Das kleine o {\displaystyle 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 ) + h f ( x ) + o ( h ) {\displaystyle f(x+h)=f(x)+hf'(x)+o(h)\qquad } für h 0 {\displaystyle h\to 0} ,

der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen .

Symbolisches Gleichheitszeichen

Oft 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 sind: Eine Aussage wie f ( x ) = O ( g ( x ) ) {\displaystyle f(x)={\mathcal {O}}(g(x))} ist keine Gleichung und keine Seite ist durch die andere bestimmt. Aus f 1 ( x ) = O ( g ( x ) ) {\displaystyle f_{1}(x)={\mathcal {O}}(g(x))} und f 2 ( x ) = O ( g ( x ) ) {\displaystyle f_{2}(x)={\mathcal {O}}(g(x))} folgt nicht, dass f 1 {\displaystyle f_{1}} und f 2 {\displaystyle f_{2}} gleich sind. Genauso wenig kann man aus f ( x ) = O ( g 1 ( x ) ) {\displaystyle f(x)={\mathcal {O}}(g_{1}(x))} und f ( x ) = O ( g 2 ( x ) ) {\displaystyle f(x)={\mathcal {O}}(g_{2}(x))} schließen, dass O ( g 1 ( x ) ) {\displaystyle {\mathcal {O}}(g_{1}(x))} und O ( g 2 ( x ) ) {\displaystyle {\mathcal {O}}(g_{2}(x))} dieselbe Klasse sind oder die eine in der anderen enthalten ist.

Tatsächlich handelt es sich bei O ( g ( x ) ) {\displaystyle {\mathcal {O}}(g(x))} um eine Menge, welche alle diejenigen Funktionen enthält, welche höchstens so schnell wachsen wie g ( x ) {\displaystyle g(x)} . Die Schreibweise f ( x ) O ( g ( x ) ) {\displaystyle f(x)\in {\mathcal {O}}(g(x))} ist also formal korrekt.

Die Notation mit dem Gleichheitszeichen wie in f = O ( g ) {\displaystyle f={\mathcal {O}}(g)} wird trotzdem in der Praxis ausgiebig genutzt. Beispielsweise soll der Ausdruck f ( n ) = h ( n ) + Θ ( g ( n ) ) {\displaystyle f(n)=h(n)+\Theta (g(n))} besagen, dass es Konstanten c 1 {\displaystyle c_{1}} und c 2 {\displaystyle c_{2}} gibt, sodass

h ( n ) + c 1 g ( n ) f ( n ) h ( n ) + c 2 g ( n ) {\displaystyle h(n)+c_{1}\cdot g(n)\,\leq \,f(n)\,\leq \,h(n)+c_{2}\cdot g(n)}

für hinreichend große n {\displaystyle n} gilt.

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 1 x o ( 1 x ) {\displaystyle \textstyle {\tfrac {1}{x}}\in o\left({\tfrac {1}{\sqrt {x}}}\right)} für x {\displaystyle x\to \infty } , nicht aber für den einseitigen Grenzwert x 0 {\displaystyle x\downarrow 0} . Normalerweise wird der betrachtete Grenzwert aber aus dem Zusammenhang klar, sodass hier Mehrdeutigkeiten nur selten auftreten.

In der Komplexitätstheorie werden die Landau-Symbole vor allem verwendet, um den (minimalen, mittleren oder maximalen) Zeit- oder Speicherplatzbedarf eines Algorithmus zu beschreiben. Man spricht dann von Zeitkomplexität bzw. Platzkomplexität. Die Komplexität kann vom verwendeten Maschinenmodell abhängen. In der Regel nimmt man jedoch ein „normales“ Modell an, zum Beispiel ein der Turingmaschine äquivalentes.

  1. Seite 401 f. des 1894 erschienenen zweiten Teils Die analytische Zahlentheorie (archive.org) seines Werkes Zahlentheorie.
  2. Seite 31 sowie Seite 61 des 1909 erschienenen ersten Bands seines Werkes Handbuch der Lehre von der Verteilung der Primzahlen (archive.org).
  3. Earliest Uses of Symbols of Number Theory, 22. September 2006: (Memento vom 19. Oktober 2007 im Internet Archive) According to Władysław Narkiewicz in The Development of Prime Number Theory: “The symbols O(·) and o(·) are usually called the Landau symbols. This name is only partially correct, since it seems that the first of them appeared first in the second volume of P. Bachmann’s treatise on number theory (Bachmann, 1894). In any case Landau (1909a, p. 883) states that he had seen it for the first time in Bachmann’s book. The symbol o(·) appears first in Landau (1909a).”
  4. G. H. Hardy, J. E. Littlewood: Some problems of Diophantine approximation. Part II. The trigonometrical series associated with the elliptic ϑ-functions. In: Acta Math. Band 37, 1914, S. 193–239, hier S. 225, doi:10.1007/BF02401834.
  5. G. H. Hardy, J. E. Littlewood: Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes. In: Acta Math. Band 41, 1916, S. 119–196, hier S. 138, doi:10.1007/BF02422942.
  6. Donald E. Knuth: Big Omicron and big Omega and big Theta. In: SIGACT News, Apr.–June 1976, S. 18–24 (Online [PDF; 348 kB]).
  7. Edmund Landau: Über die Anzahl der Gitterpunkte in gewissen Bereichen. (Vierte Abhandlung). In: Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse. 1924, S. 137–150; oder "Collected Works" (P.T. Bateman et al.), Thales Verlag, Bd. 8, 1987, S. 145–158; hier S. 140 (Göttinger Digitalisierungszentrum).
  8. Edward C. Titchmarsh: The Theory of the Riemann Zeta-Function. Clarendon Press, Oxford 1951.
  9. Mit dem Kommentar: “Although I have changed Hardy and Littlewood’s definition of Ω {\displaystyle \Omega } , I feel justified in doing so because their definition is by no mean in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies”.

Landau-Symbole
landau, symbole, notation, beschreibung, asymptotischen, verhaltens, funktionen, folgen, sprache, beobachten, bearbeiten, auch, notation, englisch, notation, werden, mathematik, informatik, verwendet, asymptotische, verhalten, funktionen, folgen, beschreiben, . Landau Symbole Notation zur Beschreibung des asymptotischen Verhaltens von Funktionen und Folgen Sprache Beobachten Bearbeiten Landau Symbole auch O Notation englisch big O notation werden in der Mathematik und in der Informatik verwendet um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Mass fur die Anzahl der Elementarschritte oder der Speichereinheiten in Abhangigkeit von der Grosse des gegebenen Problems an Die Komplexitatstheorie verwendet sie um Probleme danach zu klassifizieren wie schwierig oder aufwandig sie zu losen sind Zu leichten Problemen existiert ein Algorithmus dessen Laufzeit sich durch ein Polynom beschranken lasst als schwer gelten Probleme fur die man keinen Algorithmus gefunden hat der weniger schnell als exponentiell wachst Man nennt sie nicht polynomiell losbar Notation Anschauliche Bedeutungf o g displaystyle f o g oder f O g displaystyle f in begin smallmatrix mathcal O end smallmatrix g f displaystyle f wachst langsamer als g displaystyle g f O g displaystyle f O g oder f O g displaystyle f in mathcal O g f displaystyle f wachst nicht wesentlich schneller als g displaystyle g f 8 g displaystyle f in Theta g f displaystyle f wachst genauso schnell wie g displaystyle g f W g displaystyle f Omega g f displaystyle f wachst nicht immer langsamer als g displaystyle g Zahlentheorie f W g displaystyle f in Omega g f displaystyle f wachst nicht wesentlich langsamer als g displaystyle g Komplexitatstheorie f w g displaystyle f in omega g f displaystyle f wachst schneller als g displaystyle g Inhaltsverzeichnis 1 Geschichte des O Symbols 2 Sonderfall Omega Symbol 2 1 Zwei unvereinbare Definitionen 2 2 Die Hardy Littlewoodsche Definition 2 2 1 Einfache Beispiele 2 2 2 Zahlentheoretische Notation 2 3 Die Knuthsche Definition 3 Definition 4 Folgerung 5 Beispiele und Notation 6 Notationsfallen 6 1 Symbolisches Gleichheitszeichen 6 2 Vergessener Grenzwert 7 Anwendung in der Komplexitatstheorie 8 Siehe auch 9 Weblinks 10 EinzelnachweiseGeschichte des O Symbols BearbeitenErstmals druckte der deutsche Zahlentheoretiker Paul Bachmann 1894 durch das Zeichen O n displaystyle O n eine Grosse aus deren Ordnung in Bezug auf n displaystyle n die Ordnung von n displaystyle n nicht uberschreitet 1 Der ebenfalls deutsche Zahlentheoretiker Edmund Landau durch den die O displaystyle O und o displaystyle o Symbolik bekannt wurde und mit dessen Namen sie insbesondere im deutschen Sprachraum heute verbunden ist ubernahm Bachmanns Bezeichnung und fuhrte zudem die o displaystyle o Bezeichnung fur von kleiner Ordnung ein 2 3 Sonderfall Omega Symbol BearbeitenZwei unvereinbare Definitionen Bearbeiten Es gibt in der Mathematik zwei sehr haufige und inkonsistente Definitionen fur f x W g x x a displaystyle f x Omega g x x rightarrow a wobei a displaystyle a eine reelle Zahl displaystyle infty oder displaystyle infty ist wo die reellen Funktionen f displaystyle f und g displaystyle g auf einer Umgebung von a displaystyle a definiert sind und g displaystyle g in dieser Umgebung positiv ist Die erste wird in der analytischen Zahlentheorie benutzt und die andere in der Komplexitatstheorie Diese Situation kann zu Verwechslungen fuhren Die Hardy Littlewoodsche Definition Bearbeiten Im Jahr 1914 fuhrten Godfrey Harold Hardy und John Edensor Littlewood das Symbol W displaystyle Omega mit der Bedeutung f x W g x x lim sup x f x g x gt 0 displaystyle f x Omega g x x rightarrow infty Leftrightarrow limsup x to infty left frac f x g x right gt 0 ein 4 Also ist f x W g x displaystyle f x Omega g x die Negation von f x o g x displaystyle f x o g x Im Jahr 1916 fuhrten dieselben Verfasser zwei neue Symbole W R displaystyle Omega R und W L displaystyle Omega L mit den Bedeutungen f x W R g x x lim sup x f x g x gt 0 displaystyle f x Omega R g x x rightarrow infty Leftrightarrow limsup x to infty frac f x g x gt 0 f x W L g x x lim inf x f x g x lt 0 displaystyle f x Omega L g x x rightarrow infty Leftrightarrow liminf x to infty frac f x g x lt 0 ein 5 Also ist f x W R g x displaystyle f x Omega R g x die Negation von f x lt o g x displaystyle f x lt o g x und f x W L g x displaystyle f x Omega L g x die Negation von f x gt o g x displaystyle f x gt o g x Im Gegensatz zu einer spateren Aussage von Donald E Knuth 6 verwendete Landau diese drei Symbole im Jahre 1924 mit den gleichen Bedeutungen 7 Diese Hardy Littlewood Symbole sind Prototypen sie werden nie genau so verwendet W R displaystyle Omega R ist zu W displaystyle Omega und W L displaystyle Omega L zu W displaystyle Omega geworden Diese drei Symbole W W W displaystyle Omega Omega Omega sowie f x W g x displaystyle f x Omega pm g x dies bedeutet dass die beiden Eigenschaften f x W g x displaystyle f x Omega g x und f x W g x displaystyle f x Omega g x erfullt sind werden heute noch systematisch in der analytischen Zahlentheorie verwendet Einfache Beispiele Bearbeiten Wir haben sin x W 1 x displaystyle sin x Omega 1 x rightarrow infty und speziell sin x W 1 x displaystyle sin x Omega pm 1 x rightarrow infty Wir haben sin x 1 W 1 x displaystyle sin x 1 Omega 1 x rightarrow infty und speziell sin x 1 W 1 x displaystyle sin x 1 Omega 1 x rightarrow infty aber sin x 1 W 1 x displaystyle sin x 1 not Omega 1 x rightarrow infty Zahlentheoretische Notation Bearbeiten Die strenge Notation f W g displaystyle f in Omega g wird in der Zahlentheorie nie benutzt und man schreibt weniger streng immer f W g displaystyle f Omega g Dies bedeutet hier f displaystyle f ist ein Omega von g displaystyle g Die Knuthsche Definition Bearbeiten Im Jahr 1976 veroffentlichte Donald E Knuth einen Artikel 6 dessen Hauptziel es ist eine andere Verwendung des W displaystyle Omega Symbols zu rechtfertigen Er bemuht sich seine Leser zu uberzeugen dass abgesehen von einigen alteren Werken wie dem 1951 erschienenen Buch von Edward C Titchmarsh 8 die Hardy Littlewoodsche Definition fast nie benutzt wird Er schreibt dass er bei Landau keine Anwendung finden konnte und dass George Polya der bei Landau studierte die Einschatzung bestatigte dass Landau das W displaystyle Omega Symbol wohl nicht verwendet hat tatsachlich findet sich eine Nutzung in einer Abhandlung von 1924 7 Knuth schreibt For all the applications I have seen so far in computer science a stronger requirement is much more appropriate Er verwendet das Symbol W displaystyle Omega um diese starkere Anforderung zu beschreiben Unfortunately Hardy and Littlewood didn t define W f n displaystyle Omega f n as I wanted to Unter der Gefahr von Missverstandnissen und Verwirrung definiert er auch f x W g x g x O f x displaystyle f x Omega g x Leftrightarrow g x O f x 9 Definition BearbeitenIn der folgenden Tabelle bezeichnen f displaystyle f und g displaystyle g entweder Folgen reeller Zahlen dann ist x N displaystyle x in mathbb N und der Grenzwert a displaystyle a infty oder reellwertige Funktionen der reellen Zahlen dann ist x R displaystyle x in mathbb R und der Grenzwert aus den erweiterten reellen Zahlen a R displaystyle a in mathbb R cup lbrace infty infty rbrace oder reellwertige Funktionen beliebiger topologischer Raume X T displaystyle X mathfrak T dann ist x X displaystyle x in X und auch der Grenzwert a X displaystyle a in X Wichtigster Spezialfall ist dabei X R n displaystyle X mathbb R n Formal lassen sich die Landau Symbole dann mittels Limes superior und Limes inferior folgendermassen definieren Notation Definition Mathematische Definitionf o g displaystyle f in o g asymptotisch gegenuber g displaystyle g vernachlassigbar lim x a f x g x 0 displaystyle lim x to a left frac f x g x right 0 f O g displaystyle f in mathcal O g asymptotische obere Schranke lim sup x a f x g x lt displaystyle limsup x to a left frac f x g x right lt infty f W g displaystyle f Omega g Zahlentheorie asymptotische untere Schranke f displaystyle f ist nicht in o g displaystyle o g lim sup x a f x g x gt 0 displaystyle limsup x to a left frac f x g x right gt 0 f W g displaystyle f in Omega g Komplexitatstheorie asymptotische untere Schranke g O f displaystyle g in mathcal O f lim inf x a f x g x gt 0 displaystyle liminf x to a left frac f x g x right gt 0 f 8 g displaystyle f in Theta g asymptotisch scharfe Schranke sowohl f O g displaystyle f in mathcal O g als auch f W g displaystyle f in Omega g 0 lt lim inf x a f x g x lim sup x a f x g x lt displaystyle 0 lt liminf x to a left frac f x g x right leq limsup x to a left frac f x g x right lt infty f w g displaystyle f in omega g asymptotisch dominant g o f displaystyle g in o f lim x a f x g x displaystyle lim x to a left frac f x g x right infty In der Praxis existieren meist die Grenzwerte lim f x g x displaystyle lim tfrac f x g x sodass die Abschatzung des limes superior oft durch die einfachere Berechnung eines Grenzwerts ersetzt werden kann Aquivalent zur Definition mit Limessymbolen konnen fur einen metrischen Raum X d displaystyle X d insbesondere also fur die Falle X R displaystyle X mathbb R und X N displaystyle X mathbb N folgende Definitionen mit Quantoren verwendet werden Notation x a lt displaystyle x to a lt infty f o g displaystyle f in o g C gt 0 e gt 0 x x d x a lt e f x lt C g x displaystyle forall C gt 0 exists varepsilon gt 0 forall x in lbrace x d x a lt varepsilon rbrace f x lt C cdot g x f O g displaystyle f in mathcal O g C gt 0 e gt 0 x x d x a lt e f x C g x displaystyle exists C gt 0 exists varepsilon gt 0 forall x in lbrace x d x a lt varepsilon rbrace f x leq C cdot g x f W g displaystyle f Omega g Zahlentheorie c gt 0 e gt 0 x x d x a lt e c g x f x displaystyle exists c gt 0 forall varepsilon gt 0 exists x in lbrace x d x a lt varepsilon rbrace c cdot g x leq f x f W g displaystyle f in Omega g Komplexitatstheorie c gt 0 e gt 0 x x d x a lt e c g x f x displaystyle exists c gt 0 exists varepsilon gt 0 forall x in lbrace x d x a lt varepsilon rbrace c cdot g x leq f x f 8 g displaystyle f in Theta g c gt 0 C gt 0 e gt 0 x x d x a lt e c g x f x C g x displaystyle exists c gt 0 exists C gt 0 exists varepsilon gt 0 forall x in lbrace x d x a lt varepsilon rbrace c cdot g x leq f x leq C cdot g x f w g displaystyle f in omega g c gt 0 e gt 0 x x d x a lt e c g x f x displaystyle forall c gt 0 exists varepsilon gt 0 forall x in lbrace x d x a lt varepsilon rbrace c cdot g x leq f x Notation x displaystyle x to infty f o g displaystyle f in o g C gt 0 x 0 gt 0 x gt x 0 f x lt C g x displaystyle forall C gt 0 exists x 0 gt 0 forall x gt x 0 f x lt C cdot g x f O g displaystyle f in mathcal O g C gt 0 x 0 gt 0 x gt x 0 f x C g x displaystyle exists C gt 0 exists x 0 gt 0 forall x gt x 0 f x leq C cdot g x f W g displaystyle f Omega g Zahlentheorie c gt 0 x 0 gt 0 x gt x 0 c g x f x displaystyle exists c gt 0 forall x 0 gt 0 exists x gt x 0 c cdot g x leq f x die Test Funktion g ist immer positiv f W g displaystyle f in Omega g Komplexitatstheorie c gt 0 x 0 gt 0 x gt x 0 c g x f x displaystyle exists c gt 0 exists x 0 gt 0 forall x gt x 0 c cdot g x leq f x f 8 g displaystyle f in Theta g c gt 0 C gt 0 x 0 gt 0 x gt x 0 c g x f x C g x displaystyle exists c gt 0 exists C gt 0 exists x 0 gt 0 forall x gt x 0 c cdot g x leq f x leq C cdot g x f w g displaystyle f in omega g c gt 0 x 0 gt 0 x gt x 0 c g x lt f x displaystyle forall c gt 0 exists x 0 gt 0 forall x gt x 0 c cdot g x lt f x Analoge Definitionen lassen sich auch fur den Fall x displaystyle x to infty sowie fur einseitige Grenzwerte geben Folgerung BearbeitenFur jede Funktion f displaystyle f werden durch W f O f 8 f o f w f displaystyle Omega f mathcal O f Theta f o f omega f jeweils Mengen von Funktionen beschrieben Es gelten folgende Beziehungen zwischen diesen 8 f O f 8 f W f 8 f O f W f w f W f o f O f w f o f displaystyle begin aligned Theta f amp subseteq mathcal O f Theta f amp subseteq Omega f Theta f amp mathcal O f cap Omega f omega f amp subseteq Omega f o f amp subseteq mathcal O f emptyset amp omega f cap o f end aligned Beispiele und Notation BearbeitenBei der Verwendung der Landau Symbole wird die darin verwendete Funktion haufig verkurzt angegeben Statt zum Beispiel O g mit g R R n n 3 displaystyle mathcal O g text mit g colon mathbb R to mathbb R n mapsto n 3 schreibt man haufig verkurzend O n 3 displaystyle mathcal O n 3 Dies wird auch in den folgenden Beispielen so gehandhabt Die Beispiele in der Tabelle enthalten allesamt monoton wachsende Vergleichsfunktionen g displaystyle g bei denen es auf ihr Verhalten bei n displaystyle n to infty ankommt Als Name des Arguments wird gerne n displaystyle n genommen oft ohne eine Erlauterung weil es sich sehr haufig um eine Anzahl handelt Sie sind in dieser Hinsicht aufsteigend geordnet d h die Komplexitatsklassen sind enthalten in denen die in Zeilen darunter stehen Notation Bedeutung Anschauliche Erklarung Beispiele fur Laufzeitenf O 1 displaystyle f in mathcal O 1 f displaystyle f ist beschrankt f displaystyle f uberschreitet einen konstanten Wert nicht ist unabhangig vom Wert des Arguments n displaystyle n Feststellen ob eine Binarzahl gerade ist Nachschlagen des n displaystyle n ten Elementes in einem Feld in einer Registermaschinef O log log n displaystyle f in mathcal O log log n f displaystyle f wachst doppel logarithmisch Bei Basis 2 erhoht sich f displaystyle f um 1 wenn n displaystyle n quadriert wird Interpolationssuche im sortierten Feld mit n displaystyle n gleichformig verteilten Eintragenf O log n displaystyle f in mathcal O log n f displaystyle f wachst logarithmisch f displaystyle f wachst ungefahr um einen konstanten Betrag wenn sich n displaystyle n verdoppelt Die Basis des Logarithmus ist dabei egal Binare Suche im sortierten Feld mit n displaystyle n Eintragenf O n displaystyle f in mathcal O sqrt n f displaystyle f wachst wie die Wurzelfunktion f displaystyle f wachst ungefahr auf das Doppelte wenn sich n displaystyle n vervierfacht Anzahl der Divisionen des naiven Primzahltests Teilen durch jede ganze Zahl n displaystyle leq sqrt n f O n displaystyle f in mathcal O n f displaystyle f wachst linear f displaystyle f wachst ungefahr auf das Doppelte wenn sich n displaystyle n verdoppelt Suche im unsortierten Feld mit n displaystyle n Eintragen Bsp Lineare Suche f O n log n displaystyle f in mathcal O n log n f displaystyle f hat super lineares Wachstum Vergleichbasierte Algorithmen zum Sortieren von n displaystyle n Zahlen Mergesort Heapsortf O n 2 displaystyle f in mathcal O n 2 f displaystyle f wachst quadratisch f displaystyle f wachst ungefahr auf das Vierfache wenn sich n displaystyle n verdoppelt Einfache Algorithmen zum Sortieren von n displaystyle n Zahlen Selectionsortf O n m displaystyle f in mathcal O n m f displaystyle f wachst polynomiell f displaystyle f wachst ungefahr auf das 2 m displaystyle 2 m Fache wenn sich n displaystyle n verdoppelt Einfache Algorithmenf O 2 n displaystyle f in mathcal O 2 n f displaystyle f wachst exponentiell f displaystyle f wachst ungefahr auf das Doppelte wenn sich n displaystyle n um 1 erhoht Erfullbarkeitsproblem der Aussagenlogik SAT mittels erschopfender Suchef O n displaystyle f in mathcal O n f displaystyle f wachst faktoriell f displaystyle f wachst ungefahr auf das n 1 displaystyle n 1 Fache wenn sich n displaystyle n um 1 erhoht Problem des Handlungsreisenden mit erschopfender Suche f A n displaystyle f in A n f displaystyle f wachst wie die modifizierte Ackermannfunktion Problem ist berechenbar aber nicht notwendig primitiv rekursiv Die Landau Notation wird verwendet um das asymptotische Verhalten bei Annaherung an einen endlichen oder unendlichen Grenzwert zu beschreiben Das grosse O displaystyle mathcal O wird verwendet um eine maximale Grossenordnung anzugeben So gilt beispielsweise nach der Stirlingformel fur das asymptotische Verhalten der Fakultat n 2 p n n e n 1 O 1 n displaystyle n sqrt 2 pi n left frac n e right n left 1 mathcal O left frac 1 n right right fur n displaystyle n to infty und n O n n e n displaystyle n mathcal O left sqrt n cdot left frac n e right n right fur n displaystyle n to infty Der Faktor 2 p displaystyle sqrt 2 pi ist dabei nur eine Konstante und kann fur die Abschatzung der Grossenordnung vernachlassigt werden Die Landau Notation kann auch benutzt werden um den Fehlerterm einer Approximation zu beschreiben Beispielsweise besagt e x 1 x x 2 2 O x 3 displaystyle e x 1 x x 2 2 mathcal O x 3 qquad fur x 0 displaystyle x to 0 dass der Absolutbetrag des Approximationsfehlers kleiner als eine Konstante mal x 3 displaystyle x 3 fur x displaystyle x hinreichend nahe bei Null ist Das kleine o displaystyle o wird verwendet um zu sagen dass ein Ausdruck vernachlassigbar klein gegenuber dem angegebenen Ausdruck ist Fur differenzierbare Funktionen gilt beispielsweise f x h f x h f x o h displaystyle f x h f x hf x o h qquad fur h 0 displaystyle h to 0 der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen Notationsfallen BearbeitenSymbolisches Gleichheitszeichen Bearbeiten Oft 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 Transitivitat oder der Symmetrie anwendbar sind Eine Aussage wie f x O g x displaystyle f x mathcal O g x ist keine Gleichung und keine Seite ist durch die andere bestimmt Aus f 1 x O g x displaystyle f 1 x mathcal O g x und f 2 x O g x displaystyle f 2 x mathcal O g x folgt nicht dass f 1 displaystyle f 1 und f 2 displaystyle f 2 gleich sind Genauso wenig kann man aus f x O g 1 x displaystyle f x mathcal O g 1 x und f x O g 2 x displaystyle f x mathcal O g 2 x schliessen dass O g 1 x displaystyle mathcal O g 1 x und O g 2 x displaystyle mathcal O g 2 x dieselbe Klasse sind oder die eine in der anderen enthalten ist Tatsachlich handelt es sich bei O g x displaystyle mathcal O g x um eine Menge welche alle diejenigen Funktionen enthalt welche hochstens so schnell wachsen wie g x displaystyle g x Die Schreibweise f x O g x displaystyle f x in mathcal O g x ist also formal korrekt Die Notation mit dem Gleichheitszeichen wie in f O g displaystyle f mathcal O g wird trotzdem in der Praxis ausgiebig genutzt Beispielsweise soll der Ausdruck f n h n 8 g n displaystyle f n h n Theta g n besagen dass es Konstanten c 1 displaystyle c 1 und c 2 displaystyle c 2 gibt sodass h n c 1 g n f n h n c 2 g n displaystyle h n c 1 cdot g n leq f n leq h n c 2 cdot g n fur hinreichend grosse n displaystyle n gilt Vergessener Grenzwert Bearbeiten 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 1 x o 1 x displaystyle textstyle tfrac 1 x in o left tfrac 1 sqrt x right fur x displaystyle x to infty nicht aber fur den einseitigen Grenzwert x 0 displaystyle x downarrow 0 Normalerweise wird der betrachtete Grenzwert aber aus dem Zusammenhang klar sodass hier Mehrdeutigkeiten nur selten auftreten Anwendung in der Komplexitatstheorie BearbeitenSiehe auch Komplexitatstheorie Landau Notation In der Komplexitatstheorie werden die Landau Symbole vor allem verwendet um den minimalen mittleren oder maximalen Zeit oder Speicherplatzbedarf eines Algorithmus zu beschreiben Man spricht dann von Zeitkomplexitat bzw Platzkomplexitat Die Komplexitat kann vom verwendeten Maschinenmodell abhangen In der Regel nimmt man jedoch ein normales Modell an zum Beispiel ein der Turingmaschine aquivalentes Siehe auch BearbeitenGrenzwert Limes KonvergenzgeschwindigkeitWeblinks BearbeitenO Notation auf linux related deEinzelnachweise Bearbeiten Seite 401 f des 1894 erschienenen zweiten Teils Die analytische Zahlentheorie archive org seines Werkes Zahlentheorie Seite 31 sowie Seite 61 des 1909 erschienenen ersten Bands seines Werkes Handbuch der Lehre von der Verteilung der Primzahlen archive org Earliest Uses of Symbols of Number Theory 22 September 2006 Memento vom 19 Oktober 2007 im Internet Archive According to Wladyslaw Narkiewicz in The Development of Prime Number Theory The symbols O and o are usually called the Landau symbols This name is only partially correct since it seems that the first of them appeared first in the second volume of P Bachmann s treatise on number theory Bachmann 1894 In any case Landau 1909a p 883 states that he had seen it for the first time in Bachmann s book The symbol o appears first in Landau 1909a G H Hardy J E Littlewood Some problems of Diophantine approximation Part II The trigonometrical series associated with the elliptic ϑ functions In Acta Math Band 37 1914 S 193 239 hier S 225 doi 10 1007 BF02401834 G H Hardy J E Littlewood Contribution to the theory of the Riemann zeta function and the theory of the distribution of primes In Acta Math Band 41 1916 S 119 196 hier S 138 doi 10 1007 BF02422942 a b Donald E Knuth Big Omicron and big Omega and big Theta In SIGACT News Apr June 1976 S 18 24 Online PDF 348 kB a b Edmund Landau Uber die Anzahl der Gitterpunkte in gewissen Bereichen Vierte Abhandlung In Nachrichten von der Gesellschaft der Wissenschaften zu Gottingen Mathematisch Physikalische Klasse 1924 S 137 150 oder Collected Works P T Bateman et al Thales Verlag Bd 8 1987 S 145 158 hier S 140 Gottinger Digitalisierungszentrum Edward C Titchmarsh The Theory of the Riemann Zeta Function Clarendon Press Oxford 1951 Mit dem Kommentar Although I have changed Hardy and Littlewood s definition of W displaystyle Omega I feel justified in doing so because their definition is by no mean in wide use and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies Abgerufen von https de wikipedia org w index php title Landau Symbole amp oldid 214049910, wikipedia, wiki, deutsches

deutschland

buch, bücher, bibliothek

artikel

lesen, herunterladen

kostenlos

kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele