Ftyjtk

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 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 der Eingangsvariablen an. Die Komplexitätstheorie verwendet sie, um verschiedene Probleme danach zu vergleichen, wie „schwierig“ oder aufwendig sie zu lösen sind. Man sagt, „schwere Probleme“ wachsen exponentiell mit der Instanz oder schneller und für „leichte Probleme“ existiert ein Algorithmus, dessen Laufzeitzuwächse sich durch das Wachstum eines Polynoms beschränken lassen. Man nennt sie (nicht) polynomiell lösbar.

Notation	Anschauliche Bedeutung
f∈o(g){displaystyle fin {hbox{o}}(g)} oder f=o(g){displaystyle f={hbox{o}}(g)}	f{displaystyle f} wächst langsamer als g{displaystyle g}
f∈O(g){displaystyle fin {mathcal {O}}(g)} oder f=O(g){displaystyle f=O(g)}	f{displaystyle f} wächst nicht wesentlich schneller als g{displaystyle g}
f∈Θ(g){displaystyle fin 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 fin Omega (g)}	f{displaystyle f} wächst nicht wesentlich langsamer als g{displaystyle g} (Komplexitätstheorie)
f∈ω(g){displaystyle fin omega (g)}	f{displaystyle f} wächst schneller als g{displaystyle g}

Geschichte des O-Symbols |

O(n){displaystyle O(n)} als Symbol für „eine Grösse […], deren Ordnung in Bezug auf n{displaystyle n} die Ordnung von n{displaystyle n} nicht überschreitet“, wurde erstmals vom deutschen Zahlentheoretiker Paul Bachmann im 1894 erschienenen zweiten Teil Die analytische Zahlentheorie seines Werkes Zahlentheorie verwendet. Bekannt gemacht wurde diese Notation durch den ebenfalls deutschen Zahlentheoretiker Edmund Landau, mit dessen Namen sie insbesondere im deutschen Sprachraum heute in Verbindung gebracht wird.^[1]

Sonderfall: Omega-Symbol |

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)) (xrightarrow 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 G. H. Hardy und J. E. Littlewood das Symbol Ω{displaystyle Omega } mit der Bedeutung

f(x)=Ω(g(x)) (x→∞)⇔lim supx→∞|f(x)g(x)|>0{displaystyle f(x)=Omega (g(x)) (xrightarrow infty );Leftrightarrow ;limsup _{xto infty }left|{frac {f(x)}{g(x)}}right|>0}

ein.^[2] Also ist f(x)=Ω(g(x)){displaystyle f(x)=Omega (g(x))} die Negation von f(x)=o(g(x)){displaystyle f(x)={hbox{o}}(g(x))}.

Im Jahr 1918 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 supx→∞f(x)g(x)>0{displaystyle f(x)=Omega _{R}(g(x)) (xrightarrow infty );Leftrightarrow ;limsup _{xto infty }{frac {f(x)}{g(x)}}>0};

f(x)=ΩL(g(x)) (x→∞)⇔lim infx→∞f(x)g(x)<0{displaystyle f(x)=Omega _{L}(g(x)) (xrightarrow infty );Leftrightarrow ;liminf _{xto infty }{frac {f(x)}{g(x)}}<0}

ein.^[3] 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)<{hbox{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)>{hbox{o}}(g(x))}.

Im Gegensatz zu einer späteren Aussage von D. E. Knuth^[4] verwendete Edmund Landau diese drei Symbole im Jahre 1924 mit den gleichen Bedeutungen.^[5]

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) (xrightarrow infty )}

und speziell

sin⁡x=Ω±(1) (x→∞).{displaystyle sin x=Omega _{pm }(1) (xrightarrow infty ).}

Wir haben

sin⁡x+1=Ω(1) (x→∞){displaystyle sin x+1=Omega (1) (xrightarrow infty )}

und speziell

sin⁡x+1=Ω+(1) (x→∞){displaystyle sin x+1=Omega _{+}(1) (xrightarrow infty )}

aber

sin⁡x+1≠Ω−(1) (x→∞).{displaystyle sin x+1not =Omega _{-}(1) (xrightarrow infty ).}

Zahlentheoretische Notation |

Die strenge Notation f∈Ω(g){displaystyle fin 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 D. E. Knuth einen Artikel,^[4] dessen Hauptziel es ist, eine andere Verwendung des Ω{displaystyle Omega }-Symbols zu rechtfertigen. Er bemüht sich, seine Leser zu überzeugen, dass die Hardy-Littlewoodsche Definition fast nie benutzt wird (auch im Jahr 1976 war es für mindestens 25 Jahre falsch^[6]). Er schreibt, dass er bei Landau keine Anwendung finden konnte und dass George Pólya, der bei Landau studierte, seine, Knuths, Einschätzung bestätigte, dass Landau das Ω{displaystyle Omega }-Symbol wohl nicht verwendet hat. Knuth schreibt: „For all the applications I have seen so far in computer science, a stronger requirement […] is much more appropriate.“ Es besteht kein Zweifel, dass er recht hat, wenn er das Symbol Ω{displaystyle Omega } verwendet, 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))}.^[7]

Definition |

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

• 
  Folgen reeller Zahlen, dann ist x∈N{displaystyle xin mathbb {N} } und der Grenzwert a=∞{displaystyle a=infty }, oder


• reellwertige Funktionen der reellen Zahlen, dann ist x∈R{displaystyle xin mathbb {R} } und der Grenzwert aus den erweiterten reellen Zahlen: a∈R∪{−∞,+∞}{displaystyle ain 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 xin X} und auch der Grenzwert a∈X{displaystyle ain X}. Wichtigster Spezialfall ist dabei X=Rn{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 fin {hbox{o}}(g)}	asymptotisch gegenüber g{displaystyle g} vernachlässigbar	limx→a|f(x)g(x)|=0{displaystyle lim _{xto a}left|{frac {f(x)}{g(x)}}right|=0}
f∈O(g){displaystyle fin {mathcal {O}}(g)}	asymptotische obere Schranke	lim supx→a|f(x)g(x)|<∞{displaystyle limsup _{xto a}left|{frac {f(x)}{g(x)}}right|<infty }
f∈Θ(g){displaystyle fin Theta (g)}	asymptotisch scharfe Schranke, sowohl f∈O(g){displaystyle fin {mathcal {O}}(g)} als auch g∈O(f){displaystyle gin {mathcal {O}}(f)}	0<lim infx→a|f(x)g(x)|≤lim supx→a|f(x)g(x)|<∞{displaystyle 0<liminf _{xto a}left|{frac {f(x)}{g(x)}}right|leq limsup _{xto 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 {hbox{o}}(g)}	lim supx→a|f(x)g(x)|>0{displaystyle limsup _{xto a}left|{frac {f(x)}{g(x)}}right|>0}
f∈Ω(g){displaystyle fin Omega (g)}	(Komplexitätstheorie) asymptotische untere Schranke, g∈O(f){displaystyle gin {mathcal {O}}(f)}	lim infx→a|f(x)g(x)|>0{displaystyle liminf _{xto a}left|{frac {f(x)}{g(x)}}right|>0}
f∈ω(g){displaystyle fin omega (g)}	asymptotisch dominant, g∈o(f){displaystyle gin {hbox{o}}(f)}	limx→a|f(x)g(x)|=∞{displaystyle lim _{xto a}left|{frac {f(x)}{g(x)}}right|=infty }

In der Praxis existieren meist die Grenzwerte limf(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 xto a<infty }
f∈o(g){displaystyle fin {hbox{o}}(g)}	∀ C>0 ∃ ε>0 ∀ x∈{x:d(x,a)<ε}:|f(x)|<C⋅|g(x)|{displaystyle forall C>0 exists varepsilon >0 forall xin lbrace x:d(x,a)<varepsilon rbrace :|f(x)|<Ccdot |g(x)|}
f∈O(g){displaystyle fin {mathcal {O}}(g)}	∃ C>0 ∃ ε>0 ∀ x∈{x:d(x,a)<ε}:|f(x)|≤C⋅|g(x)|{displaystyle exists C>0 exists varepsilon >0 forall xin lbrace x:d(x,a)<varepsilon rbrace :|f(x)|leq Ccdot |g(x)|}
f∈Θ(g){displaystyle fin 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 xin lbrace x:d(x,a)<varepsilon rbrace :ccdot |g(x)|leq |f(x)|leq Ccdot |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 xin lbrace x:d(x,a)<varepsilon rbrace :ccdot |g(x)|leq |f(x)|}
f∈Ω(g){displaystyle fin 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 xin lbrace x:d(x,a)<varepsilon rbrace :ccdot |g(x)|leq |f(x)|}
f∈ω(g){displaystyle fin omega (g)}	∀ c>0 ∃ ε>0 ∀ x∈{x:d(x,a)<ε}:c⋅|g(x)|≤|f(x)|{displaystyle forall c>0 exists varepsilon >0 forall xin lbrace x:d(x,a)<varepsilon rbrace :ccdot |g(x)|leq |f(x)|}

Notation	x→∞{displaystyle xto infty }
f∈o(g){displaystyle fin {hbox{o}}(g)}	∀ C>0 ∃ x0>0 ∀ x>x0:|f(x)|<C⋅|g(x)|{displaystyle forall C>0 exists x_{0}>0 forall x>x_{0}:|f(x)|<Ccdot |g(x)|}
f∈O(g){displaystyle fin {mathcal {O}}(g)}	∃ C>0 ∃ x0>0 ∀ x>x0:|f(x)|≤C⋅|g(x)|{displaystyle exists C>0 exists x_{0}>0 forall x>x_{0}:|f(x)|leq Ccdot |g(x)|}
f∈Θ(g){displaystyle fin Theta (g)}	∃ c>0 ∃ C>0 ∃ x0>0 ∀ x>x0:c⋅|g(x)|≤|f(x)|≤C⋅|g(x)|{displaystyle exists c>0 exists C>0 exists x_{0}>0 forall x>x_{0}:ccdot |g(x)|leq |f(x)|leq Ccdot |g(x)|}
f=Ω(g){displaystyle f=Omega (g)}	(Zahlentheorie) ∃ c>0 ∀ x0>0 ∃ x>x0:c⋅g(x)≤|f(x)|{displaystyle exists c>0 forall x_{0}>0 exists x>x_{0}:ccdot g(x)leq |f(x)|} (die Test-Funktion g ist immer positiv)
f∈Ω(g){displaystyle fin Omega (g)}	(Komplexitätstheorie) ∃ c>0 ∃ x0>0 ∀ x>x0:c⋅|g(x)|≤|f(x)|{displaystyle exists c>0 exists x_{0}>0 forall x>x_{0}:ccdot |g(x)|leq |f(x)|}
f∈ω(g){displaystyle fin omega (g)}	∀ c>0 ∃ x0>0 ∀ x>x0:c⋅|g(x)|≤|f(x)|{displaystyle forall c>0 exists x_{0}>0 forall x>x_{0}:ccdot |g(x)|leq |f(x)|}

Analoge Definitionen lassen sich auch für den Fall x→−∞{displaystyle xto -infty } sowie für einseitige Grenzwerte geben.

Folgerung |

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

Ω(f),O(f),Θ(f),o(f),ω(f){displaystyle Omega (f),{mathcal {O}}(f),Theta (f),{hbox{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)\{hbox{o}}(f)&subseteq {mathcal {O}}(f)\emptyset ,&=,omega (f)cap {hbox{o}}(f)end{aligned}}}

Beispiele und Notation |

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,x↦x3{displaystyle {mathcal {O}}(g){text{ mit }}gcolon mathbb {R} to mathbb {R} ,xmapsto x^{3}} schreibt man häufig verkürzend O(x3).{displaystyle {mathcal {O}}(x^{3}).} Dies wird auch in den folgenden Beispielen so gehandhabt.

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
f∈O(1){displaystyle fin {mathcal {O}}(1)}	f{displaystyle f} ist beschränkt.	f{displaystyle f} überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments).	Nachschlagen des x{displaystyle x}-ten Elementes in einem Feld
f∈O(log⁡x){displaystyle fin {mathcal {O}}(log x)}	f{displaystyle f} wächst logarithmisch.	f{displaystyle f} wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Die Basis des Logarithmus ist dabei egal.	Binäre Suche im sortierten Feld mit x{displaystyle x} Einträgen
f∈O(x){displaystyle fin {mathcal {O}}({sqrt {x}})}	f{displaystyle f} wächst wie die Wurzelfunktion.	f{displaystyle f} wächst ungefähr auf das Doppelte, wenn sich das Argument vervierfacht.	Naiver Primzahltest mittels Teilen durch jede ganze Zahl ≤x{displaystyle leq {sqrt {x}}}
f∈O(x){displaystyle fin {mathcal {O}}(x)}	f{displaystyle f} wächst linear.	f{displaystyle f} wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt.	Suche im unsortierten Feld mit x{displaystyle x} Einträgen (Bsp. Lineare Suche)
f∈O(xlog⁡x){displaystyle fin {mathcal {O}}(xlog x)}	f{displaystyle f} hat super-lineares Wachstum		Fortgeschrittenere Algorithmen zum Sortieren von x{displaystyle x} Zahlen Mergesort, Heapsort
f∈O(x2){displaystyle fin {mathcal {O}}(x^{2})}	f{displaystyle f} wächst quadratisch.	f{displaystyle f} wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt.	Einfache Algorithmen zum Sortieren von x{displaystyle x} Zahlen Selectionsort
f∈O(xn){displaystyle fin {mathcal {O}}(x^{n})}	f{displaystyle f} wächst polynomiell.	f{displaystyle f} wächst ungefähr auf das 2n{displaystyle 2^{n}}-Fache, wenn sich das Argument verdoppelt.	„Einfache“ Algorithmen
f∈O(2x){displaystyle fin {mathcal {O}}(2^{x})}	f{displaystyle f} wächst exponentiell.	f{displaystyle f} wächst ungefähr auf das Doppelte, wenn sich das Argument um 1 erhöht.	Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels exhaustiver Suche
f∈O(x!){displaystyle fin {mathcal {O}}(x!)}	f{displaystyle f} wächst faktoriell.	f{displaystyle f} wächst ungefähr auf das (x+1){displaystyle (x+1)}-Fache, wenn sich das Argument um 1 erhöht.	Problem des Handlungsreisenden (mit exhaustiver Suche)

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 Stirling-Formel für das asymptotische Verhalten der Fakultät

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

und

n!=O(n⋅(ne)n){displaystyle n!={mathcal {O}}left({sqrt {n}}cdot left({frac {n}{e}}right)^{n}right)} für n→∞{displaystyle nto infty }.

Der Faktor 2π{displaystyle {sqrt {2pi }}} 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){displaystyle e^{x}=1+x+x^{2}/2+{mathcal {O}}(x^{3})qquad } für x→0{displaystyle xto 0},

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

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

der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen 0{displaystyle 0}.

Notationsfallen |

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 f1(x)=O(g(x)){displaystyle f_{1}(x)={mathcal {O}}(g(x))} und f2(x)=O(g(x)){displaystyle f_{2}(x)={mathcal {O}}(g(x))} folgt nicht, dass f1{displaystyle f_{1}} und f2{displaystyle f_{2}} gleich sind. Genauso wenig kann man aus f(x)=O(g1(x)){displaystyle f(x)={mathcal {O}}(g_{1}(x))} und f(x)=O(g2(x)){displaystyle f(x)={mathcal {O}}(g_{2}(x))} schließen, dass O(g1(x)){displaystyle {mathcal {O}}(g_{1}(x))} und O(g2(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 c1{displaystyle c_{1}} und c2{displaystyle c_{2}} gibt, sodass

h(n)+c1⋅g(n)≤f(n)≤h(n)+c2⋅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 1x∈o(1x){displaystyle textstyle {tfrac {1}{x}}in {hbox{o}}left({tfrac {1}{sqrt {x}}}right)} für x→∞{displaystyle xto infty }, nicht aber für den einseitigen Grenzwert x↓0{displaystyle xdownarrow 0}. Normalerweise wird der betrachtete Grenzwert aber aus dem Zusammenhang klar, sodass hier Mehrdeutigkeiten nur selten auftreten.

Anwendung in der Komplexitätstheorie |

Die Artikel Landau-Symbole#Anwendung in der Komplexitätstheorie, Komplexität (Informatik) und Komplexitätstheorie überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zusammenzuführen (→ Anleitung). Beteilige dich dazu an der betreffenden Redundanzdiskussion. Bitte entferne diesen Baustein erst nach vollständiger Abarbeitung der Redundanz und vergiss nicht, den betreffenden Eintrag auf der Redundanzdiskussionsseite mit {{Erledigt|1=~~~~}} zu markieren. Accountalive 03:47, 1. Jan. 2010 (CET)

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.

Oft ist es sehr aufwendig oder ganz unmöglich, für ein Problem L{displaystyle L} eine Funktion fL:w→fL(w){displaystyle f_{L}colon wrightarrow f_{L}(w)} 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|{displaystyle n=|w|} zu beschränken. Es ist aber meist ebenfalls zu aufwendig, eine Funktion fL:n→fL(n),n=|w|{displaystyle f_{L}colon nrightarrow f_{L}(n),n=|w|} anzugeben.

Daher hat man die Landau-Notation entwickelt, die sich auf das asymptotische Verhalten der Funktion fL{displaystyle f_{L}} 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{displaystyle {mathcal {O}}} (großer lateinischer Buchstabe „O“), mit dem man obere Schranken angeben kann; untere Schranken sind im Allgemeinen viel schwieriger zu finden. Dabei bedeutet f∈O(g){displaystyle fin {mathcal {O}}(g)} (oft auch f(n)=O(g(n)){displaystyle f(n)={mathcal {O}}(g(n))}), dass eine Konstante c>0{displaystyle c>0} und ein n0∈N{displaystyle n_{0}in {mathbb {N}}} existieren, so dass für alle n>n0{displaystyle n>n_{0}} gilt: f(n)≤c⋅g(n){displaystyle f(n)leq ccdot g(n)}. In anderen Worten: Für alle Eingabelängen ist der Rechenaufwand f(n){displaystyle f(n)} nicht wesentlich größer – d. h. höchstens um einen konstanten Faktor c{displaystyle c} – als g(n){displaystyle g(n)}.

Dabei ist die Funktion f{displaystyle f} nicht immer bekannt; als Funktion g{displaystyle g} wird hingegen meist eine Funktion gewählt, deren Wachstum gut bekannt ist (wie g(x)=x2{displaystyle g(x)=x^{2}} oder g(x)=2x{displaystyle g(x)=2^{x}}). Die Landau-Notation ist gerade dazu da, den Rechenaufwand (Platzbedarf) abzuschätzen, wenn es zu aufwendig ist, die genaue Funktion anzugeben, bzw. wenn diese zu kompliziert ist.

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 Ω{displaystyle Omega } eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit O{displaystyle {mathcal {O}}} entsprechend eine obere Schranke. Bei O(f){displaystyle {mathcal {O}}(f)} wird die Form von f{displaystyle f} (z. B. f(n)=n2{displaystyle f(n)=n^{2}}) 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 ist ihre Aussagekraft über die Komplexität des Algorithmus sehr beschränkt.

Siehe auch |

• 
  Grenzwert (Limes)


• Konvergenzgeschwindigkeit

Quellen |

1. 
   ↑ 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).”
   


2. 
   ↑ Godfrey H. Hardy, John E. Littlewood: Some problems of Diophantine approximation. Part II. The trigonometrical series associated with the elliptic ϑ-functions. In: Acta Mathematica. Bd. 37, 1914, S. 193–239, hier S. 225, doi:10.1007/BF02401834.
   


3. 
   ↑ Godfrey H. Hardy, John E. Littlewood: Contribution to the theory of the Riemann zeta-function and the theory of the distribution of primes. In: Acta Mathematica. Bd. 41, 1916, S. 119–196, doi:10.1007/BF02422942.
   


4. 
   ↑ ^ab Donald Knuth: Big Omicron and big Omega and big Theta. SIGACT News, Apr.–June 1976, 18–24 (PDF; 348 kB).
   


5. 
   ↑ 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 (Digitalisat (PDF; 437,39 kB)).
   


6. 
   ↑ Edward C. Titchmarsh: The Theory of the Riemann Zeta-Function. Clarendon Press, Oxford 1951.
   


7. 
   ↑ 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”.
   

Weblinks |

• O-Notation auf linux-related.de