imported>UKoch (oder Speicherplatzbedarf!) |
37.4.224.68 (Diskussion) |
||
Zeile 1: | Zeile 1: | ||
'''Landau-Symbole''' werden in der [[Mathematik]] und in der [[Informatik]] verwendet, um das [[Asymptotische Analyse|asymptotische Verhalten]] von [[Funktion (Mathematik)|Funktionen]] und [[Folge (Mathematik)|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 | '''Landau-Symbole''' (auch '''O-Notation''', {{enS|big O notation}}) werden in der [[Mathematik]] und in der [[Informatik]] verwendet, um das [[Asymptotische Analyse|asymptotische Verhalten]] von [[Funktion (Mathematik)|Funktionen]] und [[Folge (Mathematik)|Folgen]] zu beschreiben. In der Informatik werden sie bei der Analyse von [[Algorithmus|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.'' | ||
{| class="wikitable float-right" | {| class="wikitable float-right" | ||
Zeile 6: | Zeile 6: | ||
! Anschauliche Bedeutung | ! Anschauliche Bedeutung | ||
|- | |- | ||
|<math>f | |<math>f = o(g)</math> | ||
oder | oder | ||
<math>f | <math>f \in \begin{smallmatrix}\!\mathcal{O}\!\end{smallmatrix}(g)</math> | ||
|<math>f</math> wächst langsamer als <math>g</math> | |<math>f</math> wächst langsamer als <math>g</math> | ||
|- | |- | ||
|<math>f | |<math>f = O(g)</math> | ||
oder | oder | ||
<math>f | <math>f \in \mathcal{O}(g)</math> | ||
|<math>f</math> wächst nicht wesentlich schneller als <math>g</math> | |<math>f</math> wächst nicht wesentlich schneller als <math>g</math> | ||
|- | |- | ||
Zeile 33: | Zeile 33: | ||
|} | |} | ||
== Geschichte des O-Symbols == | == Geschichte des ''O''-Symbols == | ||
Erstmals drückte der deutsche Zahlentheoretiker [[Paul Bachmann (Mathematiker)|Paul Bachmann]] 1894 „durch das Zeichen <math>O(n)</math> eine Größe aus […], deren Ordnung in Bezug auf <math>n</math> die Ordnung von <math>n</math> nicht überschreitet […].“<ref>Seite 401 f. des 1894 erschienenen zweiten Teils ''Die analytische Zahlentheorie'' ({{archive.org|dieanalytischeza00bachuoft/page/400}}) seines Werkes ''Zahlentheorie''.</ref> Der ebenfalls deutsche Zahlentheoretiker [[Edmund Landau]], durch den die <math>O</math>- und <math>o</math>-Symbolik bekannt wurde und mit dessen Namen sie insbesondere im deutschen Sprachraum heute verbunden ist, übernahm Bachmanns Bezeichnung und führte zudem die <math>o</math>-Bezeichnung für „von kleiner Ordnung“ ein.<ref>Seite 31 sowie Seite 61 des 1909 erschienenen ersten Bands seines Werkes ''Handbuch der Lehre von der Verteilung der Primzahlen'' ({{archive.org|handbuchderlehre01landuoft/page/60}}).</ref><ref>{{Webarchiv|wayback=20071019010502|url=http://members.aol.com/jeff570/nth.html|text=Earliest Uses of Symbols of Number Theory, 22. September 2006:}} 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).”</ref> | |||
== Sonderfall: Omega-Symbol == | == Sonderfall: Omega-Symbol == | ||
Zeile 50: | Zeile 50: | ||
=== Die Hardy-Littlewoodsche Definition === | === Die Hardy-Littlewoodsche Definition === | ||
Im Jahr 1914 führten [[Godfrey Harold | Im Jahr 1914 führten [[Godfrey Harold Hardy]] und [[John Edensor Littlewood]] das Symbol <math>\Omega</math> mit der Bedeutung | ||
:<math>f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0</math> | :<math>f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0</math> | ||
ein.<ref> | ein.<ref>G. H. Hardy, J. E. Littlewood: ''Some problems of Diophantine approximation. Part II. The trigonometrical series associated with the elliptic ϑ-functions.'' In: ''[[Acta Mathematica|Acta Math.]]'' Band 37, 1914, S. 193–239, hier S. 225, {{doi|10.1007/BF02401834}}.</ref> Also ist <math>f(x)=\Omega(g(x))</math> die Negation von <math>f(x)=o(g(x))</math>. | ||
Im Jahr | Im Jahr 1916 führten dieselben Verfasser zwei neue Symbole <math>\Omega_R</math> und <math>\Omega_L</math> mit den Bedeutungen | ||
:<math>f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0</math>; | :<math>f(x)=\Omega_R(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0</math>; | ||
Zeile 62: | Zeile 62: | ||
:<math>f(x)=\Omega_L(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\liminf_{x \to \infty} \frac{f(x)}{g(x)}< 0</math> | :<math>f(x)=\Omega_L(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\liminf_{x \to \infty} \frac{f(x)}{g(x)}< 0</math> | ||
ein.<ref> | ein.<ref>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}}.</ref> Also ist <math>f(x)=\Omega_R(g(x))</math> die Negation von <math>f(x)<o(g(x))</math> und <math>f(x)=\Omega_L(g(x))</math> die Negation von <math>f(x)>o(g(x))</math>. | ||
Im Gegensatz zu einer späteren Aussage von [[Donald | Im Gegensatz zu einer späteren Aussage von [[Donald E. Knuth]]<ref name="knuth">Donald E. Knuth: ''Big Omicron and big Omega and big Theta.'' In: ''SIGACT News'', Apr.–June 1976, S. 18–24 ([http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf Online] [PDF; 348 kB]).</ref> verwendete Landau diese drei Symbole im Jahre 1924 mit den gleichen Bedeutungen.<ref name="landau">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 ([http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN252457811_1924&PHYSID=PHYS_0146 Göttinger Digitalisierungszentrum]).</ref> | ||
Diese Hardy-Littlewood-Symbole sind Prototypen, sie werden nie genau so verwendet. <math>\Omega_R</math> ist zu <math>\Omega_+</math> und <math>\Omega_L</math> zu <math>\Omega_-</math> geworden. | Diese Hardy-Littlewood-Symbole sind Prototypen, sie werden nie genau so verwendet. <math>\Omega_R</math> ist zu <math>\Omega_+</math> und <math>\Omega_L</math> zu <math>\Omega_-</math> geworden. | ||
Zeile 94: | Zeile 94: | ||
==== Zahlentheoretische Notation ==== | ==== Zahlentheoretische Notation ==== | ||
Die strenge Notation <math>f \in \Omega(g)</math> wird in der Zahlentheorie nie benutzt und man schreibt weniger streng immer <math>f =\Omega(g)</math>. Dies bedeutet hier „<math>f</math> ist | Die strenge Notation <math>f \in \Omega(g)</math> wird in der Zahlentheorie nie benutzt und man schreibt weniger streng immer <math>f =\Omega(g)</math>. Dies bedeutet hier „<math>f</math> ist ein Omega von <math>g</math>“. | ||
=== Die Knuthsche Definition === | === Die Knuthsche Definition === | ||
Im Jahr 1976 veröffentlichte [[Donald Knuth| | Im Jahr 1976 veröffentlichte [[Donald E. Knuth|Donald E. Knuth]] einen Artikel,<ref name="knuth" /> dessen Hauptziel es ist, eine andere Verwendung des <math>\Omega</math>-Symbols zu rechtfertigen. Er bemüht sich, seine Leser zu überzeugen, dass, abgesehen von einigen älteren Werken (wie dem 1951 erschienenen Buch von [[Edward Charles Titchmarsh|Edward C. Titchmarsh]]<ref name="titchmarsh">Edward C. Titchmarsh: ''The Theory of the Riemann Zeta-Function.'' Clarendon Press, Oxford 1951.</ref>), die Hardy-Littlewoodsche Definition fast nie benutzt wird. Er schreibt, dass er bei [[Edmund Landau|Landau]] keine Anwendung finden konnte und dass [[George Pólya]], der bei Landau studierte, die Einschätzung bestätigte, dass Landau das <math>\Omega</math>-Symbol wohl nicht verwendet hat (tatsächlich findet sich eine Nutzung in einer Abhandlung von 1924<ref name="landau" />). 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 <math>\Omega</math>, um diese stärkere Anforderung zu beschreiben: „Unfortunately, Hardy and Littlewood didn’t define <math>\Omega(f(n))</math> as I wanted to.“ | ||
Unter der Gefahr von Missverständnissen und Verwirrung definiert er auch | Unter der Gefahr von Missverständnissen und Verwirrung definiert er auch | ||
:<math>f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))</math>.<ref>Mit dem Kommentar: “Although I have changed Hardy and | :<math>f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))</math>.<ref>Mit dem Kommentar: “Although I have changed Hardy and Littlewood’s definition of <math>\Omega</math>, 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”.</ref> | ||
== Definition == | == Definition == | ||
In der folgenden Tabelle bezeichnen <math>f</math> und <math>g</math> entweder | In der folgenden Tabelle bezeichnen <math>f</math> und <math>g</math> entweder | ||
*[[Folge (Mathematik)|Folgen]] reeller Zahlen, dann ist <math>x\in\N</math> und der Grenzwert <math>a=\infty</math>, oder | * [[Folge (Mathematik)|Folgen]] reeller Zahlen, dann ist <math>x\in\N</math> und der Grenzwert <math>a=\infty</math>, oder | ||
* reellwertige Funktionen der reellen Zahlen, dann ist <math>x\in\R</math> und der Grenzwert aus den erweiterten reellen Zahlen: <math>a\in\R\cup\lbrace-\infty,+\infty\rbrace</math>, oder | * reellwertige Funktionen der reellen Zahlen, dann ist <math>x\in\R</math> und der Grenzwert aus den erweiterten reellen Zahlen: <math>a\in\R\cup\lbrace-\infty,+\infty\rbrace</math>, oder | ||
* reellwertige Funktionen beliebiger [[topologischer Raum|topologischer Räume]] <math>(X,\mathfrak{T})</math>, dann ist <math>x\in X</math> und auch der Grenzwert <math>a\in X</math>. Wichtigster Spezialfall ist dabei <math>X=\R^n</math>. | * reellwertige Funktionen beliebiger [[topologischer Raum|topologischer Räume]] <math>(X,\mathfrak{T})</math>, dann ist <math>x\in X</math> und auch der Grenzwert <math>a\in X</math>. Wichtigster Spezialfall ist dabei <math>X=\R^n</math>. | ||
Zeile 118: | Zeile 118: | ||
! Mathematische Definition | ! Mathematische Definition | ||
|- | |- | ||
|<math>f \in | |<math>f \in o(g)</math> | ||
|asymptotisch gegenüber <math>g</math> vernachlässigbar | |asymptotisch gegenüber <math>g</math> vernachlässigbar | ||
|<math>\lim_{x \to a} \left|\frac{f(x)}{g(x)}\right| = 0</math> | |<math>\lim_{x \to a} \left|\frac{f(x)}{g(x)}\right| = 0</math> | ||
Zeile 125: | Zeile 125: | ||
|asymptotische obere Schranke | |asymptotische obere Schranke | ||
|<math>\limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty</math> | |<math>\limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right| < \infty</math> | ||
|- | |- | ||
|<math>f = \Omega(g)</math> | |<math>f = \Omega(g)</math> | ||
Zeile 137: | Zeile 133: | ||
|(Komplexitätstheorie) asymptotische untere Schranke, <math>g\in\mathcal{O}(f)</math> | |(Komplexitätstheorie) asymptotische untere Schranke, <math>g\in\mathcal{O}(f)</math> | ||
|<math>\liminf_{x \to a} \left|\frac{f(x)}{g(x)}\right| >0</math> | |<math>\liminf_{x \to a} \left|\frac{f(x)}{g(x)}\right| >0</math> | ||
|- | |||
|<math>f \in \Theta(g)</math> | |||
|asymptotisch scharfe Schranke, sowohl <math>f\in\mathcal{O}(g)</math> als auch <math>f \in \Omega(g)</math> | |||
|<math>0 < \liminf_{x \to a} \left|\frac{f(x)}{g(x)}\right| \le \limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right|< \infty</math> | |||
|- | |- | ||
|<math>f \in \omega(g)</math> | |<math>f \in \omega(g)</math> | ||
|asymptotisch dominant, <math>g\in | |asymptotisch dominant, <math>g\in o(f)</math> | ||
|<math>\lim_{x \to a} \left|\frac{f(x)}{g(x)}\right| = \infty</math> | |<math>\lim_{x \to a} \left|\frac{f(x)}{g(x)}\right| = \infty</math> | ||
|} | |} | ||
Zeile 151: | Zeile 151: | ||
! <math>x\to a<\infty</math> | ! <math>x\to a<\infty</math> | ||
|- | |- | ||
|<math>f \in | |<math>f \in o(g)</math> | ||
|<math>\forall\ C > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: |f(x)| | |<math>\forall\ C > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: |f(x)| < C\cdot|g(x)|</math> | ||
|- | |- | ||
|<math>f \in \mathcal{O}(g)</math> | |<math>f \in \mathcal{O}(g)</math> | ||
|<math>\exists\ C > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: |f(x)| \le C\cdot|g(x)|</math> | |<math>\exists\ C > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: |f(x)| \le C\cdot|g(x)|</math> | ||
|- | |- | ||
|<math>f = \Omega(g)</math> | |<math>f = \Omega(g)</math> | ||
Zeile 165: | Zeile 162: | ||
|<math>f \in \Omega(g)</math> | |<math>f \in \Omega(g)</math> | ||
|(Komplexitätstheorie) <math>\exists\ c > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: c\cdot|g(x)| \le |f(x)|</math> | |(Komplexitätstheorie) <math>\exists\ c > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: c\cdot|g(x)| \le |f(x)|</math> | ||
|- | |||
|<math>f \in \Theta(g)</math> | |||
|<math>\exists\ c > 0\ \exists\ C > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: c\cdot|g(x)| \le |f(x)| \le C\cdot|g(x)|</math> | |||
|- | |- | ||
|<math>f \in \omega(g)</math> | |<math>f \in \omega(g)</math> | ||
Zeile 175: | Zeile 175: | ||
! <math>x\to\infty</math> | ! <math>x\to\infty</math> | ||
|- | |- | ||
|<math>f \in | |<math>f \in o(g)</math> | ||
|<math>\forall\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |f(x)| | |<math>\forall\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |f(x)| < C\cdot|g(x)|</math> | ||
|- | |- | ||
|<math>f \in \mathcal{O}(g)</math> | |<math>f \in \mathcal{O}(g)</math> | ||
|<math>\exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |f(x)| \le C\cdot|g(x)|</math> | |<math>\exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |f(x)| \le C\cdot|g(x)|</math> | ||
|- | |- | ||
|<math>f = \Omega(g)</math> | |<math>f = \Omega(g)</math> | ||
Zeile 189: | Zeile 186: | ||
|<math>f \in \Omega(g)</math> | |<math>f \in \Omega(g)</math> | ||
|(Komplexitätstheorie) <math>\exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|g(x)|\le|f(x)|</math> | |(Komplexitätstheorie) <math>\exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|g(x)|\le|f(x)|</math> | ||
|- | |||
|<math>f \in \Theta(g)</math> | |||
|<math>\exists\ c > 0\ \exists\ C > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|g(x)|\le|f(x)| \le C\cdot|g(x)|</math> | |||
|- | |- | ||
|<math>f \in \omega(g)</math> | |<math>f \in \omega(g)</math> | ||
|<math>\forall\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|g(x)| | |<math>\forall\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot|g(x)| < |f(x)|</math> | ||
|} | |} | ||
Zeile 199: | Zeile 199: | ||
Für jede Funktion <math>f</math> werden durch | Für jede Funktion <math>f</math> werden durch | ||
:<math>\Omega(f), \mathcal{O}(f), \Theta(f), | :<math>\Omega(f), \mathcal{O}(f), \Theta(f), o(f), \omega(f)</math> | ||
jeweils Mengen von Funktionen beschrieben. Es gelten folgende Beziehungen zwischen diesen: | jeweils Mengen von Funktionen beschrieben. Es gelten folgende Beziehungen zwischen diesen: | ||
Zeile 208: | Zeile 208: | ||
\Theta (f)&= \mathcal{O}(f) \cap \Omega (f) \\ | \Theta (f)&= \mathcal{O}(f) \cap \Omega (f) \\ | ||
\omega (f)&\subseteq \Omega (f) \\ | \omega (f)&\subseteq \Omega (f) \\ | ||
o(f)&\subseteq\mathcal{O}(f) \\ | |||
\O \,&=\, \omega (f) \cap | \O \,&=\, \omega (f) \cap o(f) | ||
\end{align}</math> | \end{align}</math> | ||
== Beispiele und Notation == | == Beispiele und Notation == | ||
Bei der Verwendung der Landau-Symbole wird die darin verwendete Funktion häufig verkürzt angegeben. Statt zum Beispiel <math>\mathcal{O}(g) \text{ mit }g\colon \mathbb{R}\to\mathbb{R}, | Bei der Verwendung der Landau-Symbole wird die darin verwendete Funktion häufig verkürzt angegeben. Statt zum Beispiel <math>\mathcal{O}(g) \text{ mit }g\colon \mathbb{R}\to\mathbb{R},n\mapsto n^3</math> schreibt man häufig verkürzend <math>\mathcal{O}(n^3).</math> Dies wird auch in den folgenden Beispielen so gehandhabt. | ||
Die Beispiele in der Tabelle enthalten allesamt [[monoton wachsend]]e Vergleichsfunktionen <math>g </math>, bei denen es auf ihr Verhalten bei <math>n \to \infty </math> ankommt. (Als Name des Arguments wird gerne <math>n </math> 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. | |||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
Zeile 225: | Zeile 226: | ||
|<math>f \in \mathcal{O}(1)</math> | |<math>f \in \mathcal{O}(1)</math> | ||
|<math>f</math> ist beschränkt. | |<math>f</math> ist beschränkt. | ||
|<math>f</math> überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments). | |<math>f</math> überschreitet einen konstanten Wert nicht (ist unabhängig vom Wert des Arguments <math>n</math>). | ||
|Nachschlagen des <math> | |Feststellen, ob eine Binärzahl gerade ist<br />Nachschlagen des <math>n</math>-ten Elementes in einem [[Feld (Datentyp)|Feld]] in einer [[Registermaschine]] | ||
|- | |- | ||
|<math>f \in \mathcal{O}(\log | |<math>f \in \mathcal{O}(\log \log n)</math> | ||
|<math>f</math> wächst doppel-logarithmisch. | |||
|Bei Basis 2 erhöht sich <math>f</math> um 1, wenn <math>n</math> quadriert wird. | |||
|[[Interpolationssuche]] im sortierten Feld mit <math>n</math> gleichförmig verteilten Einträgen | |||
|- | |||
|<math>f \in \mathcal{O}(\log n)</math> | |||
|<math>f</math> wächst [[Logarithmus|logarithmisch]]. | |<math>f</math> wächst [[Logarithmus|logarithmisch]]. | ||
|<math>f</math> wächst ungefähr um einen konstanten Betrag, wenn sich | |<math>f</math> wächst ungefähr um einen konstanten Betrag, wenn sich <math>n</math> verdoppelt.<br />Die Basis des Logarithmus ist dabei egal. | ||
|[[Binäre Suche]] im sortierten Feld mit <math>n</math> Einträgen | |||
Die Basis des Logarithmus ist dabei egal. | |||
|[[Binäre Suche]] im sortierten Feld mit <math> | |||
|- | |- | ||
|<math>f \in \mathcal{O}(\sqrt{ | |<math>f \in \mathcal{O}(\sqrt{n})</math> | ||
|<math>f</math> wächst wie die [[Wurzelfunktion]]. | |<math>f</math> wächst wie die [[Wurzelfunktion]]. | ||
|<math>f</math> wächst ungefähr auf das Doppelte, wenn sich | |<math>f</math> wächst ungefähr auf das Doppelte, wenn sich <math>n</math> vervierfacht. | ||
| | |Anzahl der Divisionen des naiven [[Primzahltest]]s (Teilen durch jede ganze Zahl <math>\leq \sqrt{n}</math>) | ||
|- | |- | ||
|<math>f \in \mathcal{O}( | |<math>f \in \mathcal{O}(n)</math> | ||
|<math>f</math> wächst [[Lineare Funktion|linear]]. | |<math>f</math> wächst [[Lineare Funktion|linear]]. | ||
|<math>f</math> wächst ungefähr auf das Doppelte, wenn sich | |<math>f</math> wächst ungefähr auf das Doppelte, wenn sich <math>n</math> verdoppelt. | ||
|Suche im unsortierten Feld mit <math> | |Suche im unsortierten Feld mit <math>n</math> Einträgen (Bsp. [[Lineare Suche]]) | ||
|- | |- | ||
|<math>f \in \mathcal{O}( | |<math>f \in \mathcal{O}(n \log n)</math> | ||
|<math>f</math> hat super-lineares Wachstum | |<math>f</math> hat super-lineares Wachstum. | ||
| | | | ||
| | |Vergleichbasierte Algorithmen zum Sortieren von <math>n</math> Zahlen | ||
[[Mergesort]], [[Heapsort]] | [[Mergesort]], [[Heapsort]] | ||
|- | |- | ||
|<math>f \in \mathcal{O}( | |<math>f \in \mathcal{O}(n^2)</math> | ||
|<math>f</math> wächst [[Quadratische Funktion|quadratisch]]. | |<math>f</math> wächst [[Quadratische Funktion|quadratisch]]. | ||
|<math>f</math> wächst ungefähr auf das Vierfache, wenn sich | |<math>f</math> wächst ungefähr auf das Vierfache, wenn sich <math>n</math> verdoppelt. | ||
|Einfache Algorithmen zum Sortieren von <math> | |Einfache Algorithmen zum Sortieren von <math>n</math> Zahlen | ||
[[Selectionsort]] | [[Selectionsort]] | ||
|- | |- | ||
|<math>f \in \mathcal{O}( | |<math>f \in \mathcal{O}(n^m)</math> | ||
|<math>f</math> wächst polynomiell. | |<math>f</math> wächst polynomiell. | ||
|<math>f</math> wächst ungefähr auf das <math>2^ | |<math>f</math> wächst ungefähr auf das <math>2^m</math>-Fache, wenn sich <math>n</math> verdoppelt. | ||
|„Einfache“ Algorithmen | |„Einfache“ Algorithmen | ||
|- | |- | ||
|<math>f \in \mathcal{O}(2^ | |<math>f \in \mathcal{O}(2^n)</math> | ||
|<math>f</math> wächst [[Exponentialfunktion|exponentiell]]. | |<math>f</math> wächst [[Exponentialfunktion|exponentiell]]. | ||
|<math>f</math> wächst ungefähr auf das Doppelte, wenn sich | |<math>f</math> wächst ungefähr auf das Doppelte, wenn sich <math>n</math> um 1 erhöht. | ||
|[[Erfüllbarkeitsproblem der Aussagenlogik]] (SAT) mittels [[ | |[[Erfüllbarkeitsproblem der Aussagenlogik]] (SAT) mittels [[Brute-Force-Methode|erschöpfender Suche]] | ||
|- | |- | ||
|<math>f \in \mathcal{O}( | |<math>f \in \mathcal{O}(n!)</math> | ||
|<math>f</math> wächst [[Fakultät (Mathematik)|faktoriell]]. | |<math>f</math> wächst [[Fakultät (Mathematik)|faktoriell]]. | ||
|<math>f</math> wächst ungefähr auf das <math>( | |<math>f</math> wächst ungefähr auf das <math>(n+1)</math>-Fache, wenn sich <math>n</math> um 1 erhöht. | ||
| [[Problem des Handlungsreisenden]] (mit [[ | | [[Problem des Handlungsreisenden]] (mit erschöpfender Suche) | ||
|- | |||
|<math>f \in A(n)</math> | |||
|<math>f</math> wächst wie die [[Ackermannfunktion#Modifizierte Ackermannfunktion|modifizierte Ackermannfunktion]]. | |||
| | |||
| Problem ist [[Berechenbarkeit|berechenbar]], aber nicht notwendig [[Primitiv-rekursive Funktion|primitiv-rekursiv]] | |||
|} | |} | ||
Die Landau-Notation wird verwendet, um das asymptotische Verhalten bei Annäherung an einen endlichen oder unendlichen Grenzwert zu beschreiben. | Die Landau-Notation wird verwendet, um das asymptotische Verhalten bei Annäherung an einen endlichen oder unendlichen Grenzwert zu beschreiben. | ||
Das große <math>\mathcal{O}</math> wird verwendet, um eine maximale Größenordnung anzugeben. So gilt beispielsweise nach der [[ | Das große <math>\mathcal{O}</math> wird verwendet, um eine maximale Größenordnung anzugeben. So gilt beispielsweise nach der [[Stirlingformel]] für das asymptotische Verhalten der [[Fakultät (Mathematik)|Fakultät]] | ||
:<math>n! = \sqrt{2 \pi n}~{\left(\frac{n}{e} \right)}^n \left(1 + \mathcal{O} \left(\frac{1}{n} \right) \right)</math> für <math>n\to \infty</math> | :<math>n! = \sqrt{2 \pi n}~{\left(\frac{n}{e} \right)}^n \left(1 + \mathcal{O} \left(\frac{1}{n} \right) \right)</math> für <math>n\to \infty</math> | ||
und | und | ||
Zeile 284: | Zeile 293: | ||
dass der Absolutbetrag des Approximationsfehlers kleiner als eine Konstante mal <math>x^3</math> für <math>x</math> hinreichend nahe bei Null ist. | dass der Absolutbetrag des Approximationsfehlers kleiner als eine Konstante mal <math>x^3</math> für <math>x</math> hinreichend nahe bei Null ist. | ||
Das kleine <math> | Das kleine <math>o</math> wird verwendet, um zu sagen, dass ein Ausdruck vernachlässigbar klein gegenüber dem angegebenen Ausdruck ist. Für [[Differentialrechnung|differenzierbare]] Funktionen gilt beispielsweise | ||
:<math>f(x+h)=f(x)+hf'(x)+ | :<math>f(x+h)=f(x)+hf'(x)+o(h)\qquad</math> für <math>h\to 0</math>, | ||
der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen <math>0</math>. | der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen <math>0</math>. | ||
== Notationsfallen == | == Notationsfallen == | ||
=== Symbolisches Gleichheitszeichen === | === 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 [[Transitive Relation|Transitivität]] oder der [[Symmetrische Relation|Symmetrie]] anwendbar | 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 [[Transitive Relation|Transitivität]] oder der [[Symmetrische Relation|Symmetrie]] anwendbar sind: Eine Aussage wie <math>f(x)=\mathcal{O}(g(x))</math> ist keine Gleichung und keine Seite ist durch die andere bestimmt. Aus <math>f_1(x)=\mathcal{O}(g(x))</math> und <math>f_2(x)=\mathcal{O}(g(x))</math> folgt nicht, dass <math>f_1</math> und <math>f_2</math> gleich sind. Genauso wenig kann man aus <math>f(x)=\mathcal{O}(g_1(x))</math> und <math>f(x)=\mathcal{O}(g_2(x))</math> schließen, dass <math>\mathcal{O}(g_1(x))</math> und <math>\mathcal{O}(g_2(x))</math> dieselbe Klasse sind oder die eine in der anderen enthalten ist. | ||
Tatsächlich handelt es sich bei <math>\mathcal{O}(g(x))</math> um eine Menge, welche alle diejenigen Funktionen enthält, welche höchstens so schnell wachsen wie <math>g(x)</math>. Die Schreibweise <math>f(x) \in \mathcal{O}(g(x))</math> ist also formal korrekt. | Tatsächlich handelt es sich bei <math>\mathcal{O}(g(x))</math> um eine Menge, welche alle diejenigen Funktionen enthält, welche höchstens so schnell wachsen wie <math>g(x)</math>. Die Schreibweise <math>f(x) \in \mathcal{O}(g(x))</math> ist also formal korrekt. | ||
Zeile 300: | Zeile 310: | ||
=== Vergessener Grenzwert === | === 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 <math> | |||
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 | |||
:<math>\tfrac{1}{x}\in o\left(\tfrac{1}{\sqrt{x}}\right)</math> | |||
für <math>x\!\uparrow \!\infty</math>, nicht aber für den [[Grenzwert (Funktion)#rechtsseitiger Grenzwert|einseitigen Grenzwert]] <math>x\!\downarrow \!0 </math> mit | |||
:<math>\tfrac{1}{x} \in \mathcal O\left(\tfrac{1}{\sqrt{x}}\right)(x\!\downarrow \!0)~.</math> | |||
Jedoch wird normalerweise der zu betrachtende Grenzwert aus dem Zusammenhang klar und Mehrdeutigkeiten treten nur selten auf. | |||
== Anwendung in der Komplexitätstheorie == | == Anwendung in der Komplexitätstheorie == | ||
{{Siehe auch|Komplexitätstheorie#Landau-Notation|titel1 = Komplexitätstheorie – Landau-Notation}} | |||
{{ | |||
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. | 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. | ||
== Siehe auch == | |||
* [[Grenzwert (Folge)|Grenzwert]] (Limes) | * [[Grenzwert (Folge)|Grenzwert]] (Limes) | ||
* [[Konvergenzgeschwindigkeit]] | * [[Konvergenzgeschwindigkeit]] | ||
== | == Weblinks == | ||
* [http://www.linux-related.de/index.html?/coding/o-notation.htm O-Notation auf linux-related.de] | * [http://www.linux-related.de/index.html?/coding/o-notation.htm O-Notation auf linux-related.de] | ||
== Einzelnachweise == | |||
<references /> | |||
[[Kategorie:Analytische Zahlentheorie]] | [[Kategorie:Analytische Zahlentheorie]] |
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 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) $
oder $ f\in {\begin{smallmatrix}\!{\mathcal {O}}\!\end{smallmatrix}}(g) $ |
$ f $ wächst langsamer als $ g $ |
$ f=O(g) $
oder $ f\in {\mathcal {O}}(g) $ |
$ f $ wächst nicht wesentlich schneller als $ g $ |
$ f\in \Theta (g) $ | $ f $ wächst genauso schnell wie $ g $ |
$ f=\Omega (g) $ | $ f $ wächst nicht immer langsamer als $ g $ (Zahlentheorie) |
$ f\in \Omega (g) $ | $ f $ wächst nicht wesentlich langsamer als $ g $ (Komplexitätstheorie) |
$ f\in \omega (g) $ | $ f $ wächst schneller als $ g $ |
Erstmals drückte der deutsche Zahlentheoretiker Paul Bachmann 1894 „durch das Zeichen $ O(n) $ eine Größe aus […], deren Ordnung in Bezug auf $ n $ die Ordnung von $ n $ nicht überschreitet […].“[1] Der ebenfalls deutsche Zahlentheoretiker Edmund Landau, durch den die $ O $- und $ 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 $-Bezeichnung für „von kleiner Ordnung“ ein.[2][3]
Es gibt in der Mathematik zwei sehr häufige und inkonsistente Definitionen für
wobei $ a $ eine reelle Zahl, $ \infty $ oder $ -\infty $ ist, wo die reellen Funktionen $ f $ und $ g $ auf einer Umgebung von $ a $ definiert sind und $ 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.
Im Jahr 1914 führten Godfrey Harold Hardy und John Edensor Littlewood das Symbol $ \Omega $ mit der Bedeutung
ein.[4] Also ist $ f(x)=\Omega (g(x)) $ die Negation von $ f(x)=o(g(x)) $.
Im Jahr 1916 führten dieselben Verfasser zwei neue Symbole $ \Omega _{R} $ und $ \Omega _{L} $ mit den Bedeutungen
ein.[5] Also ist $ f(x)=\Omega _{R}(g(x)) $ die Negation von $ f(x)<o(g(x)) $ und $ f(x)=\Omega _{L}(g(x)) $ die Negation von $ f(x)>o(g(x)) $.
Im Gegensatz zu einer späteren 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. $ \Omega _{R} $ ist zu $ \Omega _{+} $ und $ \Omega _{L} $ zu $ \Omega _{-} $ geworden.
Diese drei Symbole $ \Omega ,\Omega _{+},\Omega _{-} $ sowie $ f(x)=\Omega _{\pm }(g(x)) $ (dies bedeutet, dass die beiden Eigenschaften $ f(x)=\Omega _{+}(g(x)) $ und $ f(x)=\Omega _{-}(g(x)) $ erfüllt sind) werden heute noch systematisch in der analytischen Zahlentheorie verwendet.
Wir haben
und speziell
Wir haben
und speziell
aber
Die strenge Notation $ f\in \Omega (g) $ wird in der Zahlentheorie nie benutzt und man schreibt weniger streng immer $ f=\Omega (g) $. Dies bedeutet hier „$ f $ ist ein Omega von $ g $“.
Im Jahr 1976 veröffentlichte Donald E. Knuth einen Artikel,[6] dessen Hauptziel es ist, eine andere Verwendung des $ \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[8]), 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 $ \Omega $-Symbol wohl nicht verwendet hat (tatsächlich 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 $ \Omega $, um diese stärkere Anforderung zu beschreiben: „Unfortunately, Hardy and Littlewood didn’t define $ \Omega (f(n)) $ as I wanted to.“
Unter der Gefahr von Missverständnissen und Verwirrung definiert er auch
In der folgenden Tabelle bezeichnen $ f $ und $ g $ entweder
Formal lassen sich die Landau-Symbole dann mittels Limes superior und Limes inferior folgendermaßen definieren:
Notation | Definition | Mathematische Definition |
---|---|---|
$ f\in o(g) $ | asymptotisch gegenüber $ g $ vernachlässigbar | $ \lim _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|=0 $ |
$ f\in {\mathcal {O}}(g) $ | asymptotische obere Schranke | $ \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty $ |
$ f=\Omega (g) $ | (Zahlentheorie) asymptotische untere Schranke, $ f $ ist nicht in $ o(g) $ | $ \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|>0 $ |
$ f\in \Omega (g) $ | (Komplexitätstheorie) asymptotische untere Schranke, $ g\in {\mathcal {O}}(f) $ | $ \liminf _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|>0 $ |
$ f\in \Theta (g) $ | asymptotisch scharfe Schranke, sowohl $ f\in {\mathcal {O}}(g) $ als auch $ f\in \Omega (g) $ | $ 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\in \omega (g) $ | asymptotisch dominant, $ g\in o(f) $ | $ \lim _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|=\infty $ |
In der Praxis existieren meist die Grenzwerte $ \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) $, insbesondere also für die Fälle $ X=\mathbb {R} $ und $ X=\mathbb {N} $, folgende Definitionen mit Quantoren verwendet werden:
Notation | $ x\to a<\infty $ |
---|---|
$ f\in o(g) $ | $ \forall \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :|f(x)|<C\cdot |g(x)| $ |
$ f\in {\mathcal {O}}(g) $ | $ \exists \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :|f(x)|\leq C\cdot |g(x)| $ |
$ f=\Omega (g) $ | (Zahlentheorie) $ \exists \ c>0\ \forall \ \varepsilon >0\ \exists \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)| $ |
$ f\in \Omega (g) $ | (Komplexitätstheorie) $ \exists \ c>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)| $ |
$ f\in \Theta (g) $ | $ \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\in \omega (g) $ | $ \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\to \infty $ |
---|---|
$ f\in o(g) $ | $ \forall \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|<C\cdot |g(x)| $ |
$ f\in {\mathcal {O}}(g) $ | $ \exists \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|\leq C\cdot |g(x)| $ |
$ f=\Omega (g) $ | (Zahlentheorie) $ \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\in \Omega (g) $ | (Komplexitätstheorie) $ \exists \ c>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:c\cdot |g(x)|\leq |f(x)| $ |
$ f\in \Theta (g) $ | $ \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\in \omega (g) $ | $ \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\to -\infty $ sowie für einseitige Grenzwerte geben.
Für jede Funktion $ f $ werden durch
jeweils Mengen von Funktionen beschrieben. Es gelten folgende Beziehungen zwischen diesen:
Bei der Verwendung der Landau-Symbole wird die darin verwendete Funktion häufig verkürzt angegeben. Statt zum Beispiel $ {\mathcal {O}}(g){\text{ mit }}g\colon \mathbb {R} \to \mathbb {R} ,n\mapsto n^{3} $ schreibt man häufig verkürzend $ {\mathcal {O}}(n^{3}). $ Dies wird auch in den folgenden Beispielen so gehandhabt.
Die Beispiele in der Tabelle enthalten allesamt monoton wachsende Vergleichsfunktionen $ g $, bei denen es auf ihr Verhalten bei $ n\to \infty $ ankommt. (Als Name des Arguments wird gerne $ 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\in {\mathcal {O}}(1) $ | $ f $ ist beschränkt. | $ f $ überschreitet einen konstanten Wert nicht (ist unabhängig vom Wert des Arguments $ n $). | Feststellen, ob eine Binärzahl gerade ist Nachschlagen des $ n $-ten Elementes in einem Feld in einer Registermaschine |
$ f\in {\mathcal {O}}(\log \log n) $ | $ f $ wächst doppel-logarithmisch. | Bei Basis 2 erhöht sich $ f $ um 1, wenn $ n $ quadriert wird. | Interpolationssuche im sortierten Feld mit $ n $ gleichförmig verteilten Einträgen |
$ f\in {\mathcal {O}}(\log n) $ | $ f $ wächst logarithmisch. | $ f $ wächst ungefähr um einen konstanten Betrag, wenn sich $ n $ verdoppelt. Die Basis des Logarithmus ist dabei egal. |
Binäre Suche im sortierten Feld mit $ n $ Einträgen |
$ f\in {\mathcal {O}}({\sqrt {n}}) $ | $ f $ wächst wie die Wurzelfunktion. | $ f $ wächst ungefähr auf das Doppelte, wenn sich $ n $ vervierfacht. | Anzahl der Divisionen des naiven Primzahltests (Teilen durch jede ganze Zahl $ \leq {\sqrt {n}} $) |
$ f\in {\mathcal {O}}(n) $ | $ f $ wächst linear. | $ f $ wächst ungefähr auf das Doppelte, wenn sich $ n $ verdoppelt. | Suche im unsortierten Feld mit $ n $ Einträgen (Bsp. Lineare Suche) |
$ f\in {\mathcal {O}}(n\log n) $ | $ f $ hat super-lineares Wachstum. | Vergleichbasierte Algorithmen zum Sortieren von $ n $ Zahlen
Mergesort, Heapsort | |
$ f\in {\mathcal {O}}(n^{2}) $ | $ f $ wächst quadratisch. | $ f $ wächst ungefähr auf das Vierfache, wenn sich $ n $ verdoppelt. | Einfache Algorithmen zum Sortieren von $ n $ Zahlen
Selectionsort |
$ f\in {\mathcal {O}}(n^{m}) $ | $ f $ wächst polynomiell. | $ f $ wächst ungefähr auf das $ 2^{m} $-Fache, wenn sich $ n $ verdoppelt. | „Einfache“ Algorithmen |
$ f\in {\mathcal {O}}(2^{n}) $ | $ f $ wächst exponentiell. | $ f $ wächst ungefähr auf das Doppelte, wenn sich $ n $ um 1 erhöht. | Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels erschöpfender Suche |
$ f\in {\mathcal {O}}(n!) $ | $ f $ wächst faktoriell. | $ f $ wächst ungefähr auf das $ (n+1) $-Fache, wenn sich $ n $ um 1 erhöht. | Problem des Handlungsreisenden (mit erschöpfender Suche) |
$ f\in A(n) $ | $ 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 $ {\mathcal {O}} $ wird verwendet, um eine maximale Größenordnung anzugeben. So gilt beispielsweise nach der Stirlingformel für das asymptotische Verhalten der Fakultät
und
Der Faktor $ {\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
dass der Absolutbetrag des Approximationsfehlers kleiner als eine Konstante mal $ x^{3} $ für $ x $ hinreichend nahe bei Null ist.
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
der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen $ 0 $.
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)={\mathcal {O}}(g(x)) $ ist keine Gleichung und keine Seite ist durch die andere bestimmt. Aus $ f_{1}(x)={\mathcal {O}}(g(x)) $ und $ f_{2}(x)={\mathcal {O}}(g(x)) $ folgt nicht, dass $ f_{1} $ und $ f_{2} $ gleich sind. Genauso wenig kann man aus $ f(x)={\mathcal {O}}(g_{1}(x)) $ und $ f(x)={\mathcal {O}}(g_{2}(x)) $ schließen, dass $ {\mathcal {O}}(g_{1}(x)) $ und $ {\mathcal {O}}(g_{2}(x)) $ dieselbe Klasse sind oder die eine in der anderen enthalten ist.
Tatsächlich handelt es sich bei $ {\mathcal {O}}(g(x)) $ um eine Menge, welche alle diejenigen Funktionen enthält, welche höchstens so schnell wachsen wie $ g(x) $. Die Schreibweise $ f(x)\in {\mathcal {O}}(g(x)) $ ist also formal korrekt.
Die Notation mit dem Gleichheitszeichen wie in $ f={\mathcal {O}}(g) $ wird trotzdem in der Praxis ausgiebig genutzt. Beispielsweise soll der Ausdruck $ f(n)=h(n)+\Theta (g(n)) $ besagen, dass es Konstanten $ c_{1} $ und $ c_{2} $ gibt, sodass
für hinreichend große $ n $ gilt.
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 $ x\!\uparrow \!\infty $, nicht aber für den einseitigen Grenzwert $ x\!\downarrow \!0 $ mit
Jedoch wird normalerweise der zu betrachtende Grenzwert aus dem Zusammenhang klar und Mehrdeutigkeiten treten nur selten auf.
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.