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 (immer ohne Berücksichtigung von Konstanten)
${\displaystyle f=o(g)}$ oder ${\displaystyle f\in {\begin{smallmatrix}\!{\mathcal {O}}\!\end{smallmatrix}}(g)}$	${\displaystyle f}$ wächst langsamer als ${\displaystyle g}$
${\displaystyle f=O(g)}$ oder ${\displaystyle f\in {\mathcal {O}}(g)}$	${\displaystyle f}$ wächst höchstens genauso schnell wie ${\displaystyle g}$
${\displaystyle f\in \Theta (g)}$	${\displaystyle f}$ wächst genauso schnell wie ${\displaystyle g}$
${\displaystyle f=\Omega (g)}$	${\displaystyle f}$ wächst nicht immer langsamer als ${\displaystyle g}$ (Zahlentheorie)
${\displaystyle f\in \Omega (g)}$	${\displaystyle f}$ wächst mindestens genauso schnell wie ${\displaystyle g}$ (Komplexitätstheorie)
${\displaystyle f\in \omega (g)}$	${\displaystyle f}$ wächst schneller als ${\displaystyle g}$

Geschichte des O-Symbols

Erstmals drückte der deutsche Zahlentheoretiker Paul Bachmann 1894 „durch das Zeichen ${\displaystyle O(n)}$ eine Größe aus […], deren Ordnung in Bezug auf ${\displaystyle n}$ die Ordnung von ${\displaystyle n}$ nicht überschreitet […].“ Der ebenfalls deutsche Zahlentheoretiker Edmund Landau, durch den die ${\displaystyle O}$- und ${\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 ${\displaystyle o}$-Bezeichnung für „von kleiner Ordnung“ ein.

Sonderfall: Omega-Symbol

Definition

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

• Folgen reeller Zahlen, dann ist ${\displaystyle x\in \mathbb {N} }$ und der Grenzwert ${\displaystyle a=\infty }$, oder
• reellwertige Funktionen der reellen Zahlen, dann ist ${\displaystyle x\in \mathbb {R} }$ und der Grenzwert aus den erweiterten reellen Zahlen: ${\displaystyle a\in \mathbb {R} \cup \lbrace -\infty ,+\infty \rbrace }$, oder
• reellwertige Funktionen beliebiger topologischer Räume ${\displaystyle (X,{\mathfrak {T}})}$, dann ist ${\displaystyle x\in X}$ und auch der Grenzwert ${\displaystyle a\in X}$. Wichtigster Spezialfall ist dabei ${\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
${\displaystyle f\in o(g)}$	asymptotisch gegenüber ${\displaystyle g}$ vernachlässigbar	${\displaystyle \lim _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|=0}$
${\displaystyle f\in {\mathcal {O}}(g)}$	asymptotische obere Schranke	${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }$
${\displaystyle f=\Omega (g)}$	(Zahlentheorie) asymptotische untere Schranke, ${\displaystyle f}$ ist nicht in ${\displaystyle o(g)}$	${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|>0}$
${\displaystyle f\in \Omega (g)}$	(Komplexitätstheorie) asymptotische untere Schranke, ${\displaystyle g\in {\mathcal {O}}(f)}$	${\displaystyle \liminf _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|>0}$
${\displaystyle f\in \Theta (g)}$	asymptotisch scharfe Schranke, sowohl ${\displaystyle f\in {\mathcal {O}}(g)}$ als auch ${\displaystyle f\in \Omega (g)}$	${\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 }$
${\displaystyle f\in \omega (g)}$	asymptotisch dominant, ${\displaystyle g\in o(f)}$	${\displaystyle \lim _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|=\infty }$

In der Praxis existieren meist die Grenzwerte ${\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 ${\displaystyle (X;d)}$, insbesondere also für die Fälle ${\displaystyle X=\mathbb {R} }$ und ${\displaystyle X=\mathbb {N} }$, folgende Definitionen mit Quantoren verwendet werden:

Notation	${\displaystyle x\to a<\infty }$
${\displaystyle f\in o(g)}$	${\displaystyle \forall \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace$ :|f(x)|<C\cdot |g(x)|}
${\displaystyle f\in {\mathcal {O}}(g)}$	${\displaystyle \exists \ C>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace$ :|f(x)|\leq C\cdot |g(x)|}
${\displaystyle f=\Omega (g)}$	(Zahlentheorie) ${\displaystyle \exists \ c>0\ \forall \ \varepsilon >0\ \exists \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)|}$
${\displaystyle f\in \Omega (g)}$	(Komplexitätstheorie) ${\displaystyle \exists \ c>0\ \exists \ \varepsilon >0\ \forall \ x\in \lbrace x:d(x,a)<\varepsilon \rbrace :c\cdot |g(x)|\leq |f(x)|}$
${\displaystyle f\in \Theta (g)}$	${\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)|}$
${\displaystyle f\in \omega (g)}$	${\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	${\displaystyle x\to \infty }$
${\displaystyle f\in o(g)}$	${\displaystyle \forall \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|<C\cdot |g(x)|}$
${\displaystyle f\in {\mathcal {O}}(g)}$	${\displaystyle \exists \ C>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:|f(x)|\leq C\cdot |g(x)|}$
${\displaystyle f=\Omega (g)}$	(Zahlentheorie) ${\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)
${\displaystyle f\in \Omega (g)}$	(Komplexitätstheorie) ${\displaystyle \exists \ c>0\ \exists \ x_{0}>0\ \forall \ x>x_{0}:c\cdot |g(x)|\leq |f(x)|}$
${\displaystyle f\in \Theta (g)}$	${\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)|}$
${\displaystyle f\in \omega (g)}$	${\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 ${\displaystyle x\to -\infty }$ sowie für einseitige Grenzwerte geben.

Folgerung

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

${\displaystyle \Omega (f),{\mathcal {O}}(f),\Theta (f),o(f),\omega (f)}$

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

${\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}}}$

Beispiele und Notation

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

Die Beispiele in der Tabelle enthalten allesamt monoton wachsende Vergleichsfunktionen ${\displaystyle g}$, bei denen es auf ihr Verhalten bei ${\displaystyle n\to \infty }$ ankommt. (Als Name des Arguments wird gerne ${\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
${\displaystyle f\in {\mathcal {O}}(1)}$	${\displaystyle f}$ ist beschränkt.	${\displaystyle f}$ überschreitet einen konstanten Wert nicht (ist unabhängig vom Wert des Arguments ${\displaystyle n}$).	Feststellen, ob eine Binärzahl gerade ist Nachschlagen des ${\displaystyle n}$-ten Elementes in einem Feld in einer Registermaschine
${\displaystyle f\in {\mathcal {O}}(\log \log n)}$	${\displaystyle f}$ wächst doppel-logarithmisch.	Bei Basis 2 erhöht sich ${\displaystyle f}$ um 1, wenn ${\displaystyle n}$ quadriert wird.	Interpolationssuche im sortierten Feld mit ${\displaystyle n}$ gleichförmig verteilten Einträgen
${\displaystyle f\in {\mathcal {O}}(\log n)}$	${\displaystyle f}$ wächst logarithmisch.	${\displaystyle f}$ wächst ungefähr um einen konstanten Betrag, wenn sich ${\displaystyle n}$ verdoppelt. Die Basis des Logarithmus ist dabei egal.	Binäre Suche im sortierten Feld mit ${\displaystyle n}$ Einträgen
${\displaystyle f\in {\mathcal {O}}({\sqrt {n}})}$	${\displaystyle f}$ wächst wie die Wurzelfunktion.	${\displaystyle f}$ wächst ungefähr auf das Doppelte, wenn sich ${\displaystyle n}$ vervierfacht.	Anzahl der Divisionen des naiven Primzahltests (Teilen durch jede ganze Zahl ${\displaystyle \leq {\sqrt {n}}}$)
${\displaystyle f\in {\mathcal {O}}(n)}$	${\displaystyle f}$ wächst linear.	${\displaystyle f}$ wächst ungefähr auf das Doppelte, wenn sich ${\displaystyle n}$ verdoppelt.	Suche im unsortierten Feld mit ${\displaystyle n}$ Einträgen (Bsp. Lineare Suche)
${\displaystyle f\in {\mathcal {O}}(n\log n)}$	${\displaystyle f}$ hat super-lineares Wachstum.		Vergleichbasierte Algorithmen zum Sortieren von ${\displaystyle n}$ Zahlen Mergesort, Heapsort
${\displaystyle f\in {\mathcal {O}}(n^{2})}$	${\displaystyle f}$ wächst quadratisch.	${\displaystyle f}$ wächst ungefähr auf das Vierfache, wenn sich ${\displaystyle n}$ verdoppelt.	Einfache Algorithmen zum Sortieren von ${\displaystyle n}$ Zahlen Selectionsort
${\displaystyle f\in {\mathcal {O}}(n^{m})}$	${\displaystyle f}$ wächst polynomiell.	${\displaystyle f}$ wächst ungefähr auf das ${\displaystyle 2^{m}}$-Fache, wenn sich ${\displaystyle n}$ verdoppelt.	„Einfache“ Algorithmen
${\displaystyle f\in {\mathcal {O}}(2^{n})}$	${\displaystyle f}$ wächst exponentiell.	${\displaystyle f}$ wächst ungefähr auf das Doppelte, wenn sich ${\displaystyle n}$ um 1 erhöht.	Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels erschöpfender Suche
${\displaystyle f\in {\mathcal {O}}(n!)}$	${\displaystyle f}$ wächst faktoriell.	${\displaystyle f}$ wächst ungefähr auf das ${\displaystyle (n+1)}$-Fache, wenn sich ${\displaystyle n}$ um 1 erhöht.	Problem des Handlungsreisenden (mit erschöpfender Suche)
${\displaystyle f\in {\mathcal {O}}(A(n))}$	${\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 ${\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

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

und

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

Der Faktor ${\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

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

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

Das kleine ${\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

${\displaystyle f(x+h)=f(x)+hf'(x)+o(h)\qquad }$ für ${\displaystyle h\to 0}$,

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

Notationsfallen

Anwendung in der Komplexitätstheorie

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 (Limes)
• Konvergenzgeschwindigkeit

Weblinks

• O-Notation auf linux-related.de

Einzelnachweise

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. 1 2 Donald E. Knuth: Big Omicron and big Omega and big Theta. In: SIGACT News, Apr.–June 1976, S. 18–24 (Online (Memento vom 30. November 2021 im Internet Archive) [PDF; 348 kB]).
7. 1 2 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”.