Landau-Symbole

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

Inhaltsverzeichnis

1 Geschichte

2 Beispiele

3 Formale Definition

3.1 Definition mit Quantoren

4 Notationsfallen

4.1 Symbolisches Gleichheitszeichen
4.2 Vergessener Grenzwert

5 Anwendung in der Komplexitätstheorie

6 Weblinks

Geschichte

Der Großbuchstaben "O" (damals eigentlich ein großes Omikron) als Symbol für "Ordnung von" wurde erstmals vom deutschen Zahlentheoretiker Paul Bachmann in seinem 1892 erschienen Buch Analytische Zahlentheorie verwendet. Bekanntgemacht wurde diese Notation durch den ebenfalls deutschen Zahlentheoretiker Edmund Landau, mit dessen Namen sie insbesondere im deutschen Sprachraum heute in Verbindung gebracht wird.

Beispiele

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

$n! = \hbox{O}\!\left( \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}\right)$ für $n\to \infty$ .

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

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

dass der Absolutbetrag des Approximationsfehler kleiner als eine Konstante mal $x 3$ für $x$ hinreichend nahe bei Null.

Das kleine o wird verwendet, um zu sagen, dass ein Ausdruck vernachlässigbar klein gegenüber dem angegebene Ausdruck ist. Für differenzierbare Funktionen gilt beispielsweise

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

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

Formale Definition

Groß O und klein o sind die am häufigsten verwendeten Landau-Symbole; darüber hinaus gibt es noch Ω, ω und Θ.

In der folgenden Tabelle bezeichnen $f$ und $g$ entweder

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

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

Notation	Definition	Mathematische Definition
$f(x) \in \hbox{O}(g(x))$	asymptotische obere Schranke	$0 \le \limsup_{x \to a} \left\|\frac{f(x)}{g(x)}\right\| < \infty$
$f(x) \in \hbox{o}(g(x))$	asymptotisch vernachlässigbar	$0 = \lim_{x \to a} \left\|\frac{f(x)}{g(x)}\right\|$
$f(x) \in \Omega(g(x))$	asymptotische untere Schranke, $g(x)\in\hbox{O}(f(x))$	$0 < \liminf_{x \to a} \left\|\frac{f(x)}{g(x)}\right\| \le \infty$
$f(x) \in \omega(g(x))$	asymptotisch dominant, $g(x)\in\hbox{o}(f(x))$	$\lim_{x \to a} \left\|\frac{f(x)}{g(x)}\right\| = \infty$
$f(x) \in \Theta(g(x))$	asymptotisch scharfe Schranke, sowohl $f(x)\in\hbox{O}(g(x))$ als auch $g(x)\in\hbox{O}(f(x))$	$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$

Definition mit Quantoren

Äquivalent zur Definition mit Limessymbolen können für einen metrischen Raum $X$ , insbesondere also für die Fälle $X=\R$ und $X=\N$ folgende Definitionen mit Quantoren verwendet werden:

Notation	$x\to a<\infty$	$x\to\infty$
$f(x) \in \hbox{O}(g(x))$	$\exists\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| \le c\cdot \|g(x)\|$	$\exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| \le c\cdot \|g(x)\|$
$f(x) \in \hbox{o}(g(x))$	$\forall\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| < c\cdot \|g(x)\|$	$\forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| < c\cdot \|g(x)\|$
$f(x) \in \Omega(g(x))$	$\exists\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| \ge c\cdot \|g(x)\|$	$\exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| \ge c\cdot \|g(x)\|$
$f(x) \in \omega(g(x))$	$\forall\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| > c\cdot \|g(x)\|$	$\forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| > c\cdot \|g(x)\|$
$f(x) \in \Theta(g(x))$	$\exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $c_0\cdot \|g(x)\|\le\|f(x)\| \le c_1\cdot \|g(x)\|$	$\exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ x_0\ \forall\ x > x_0:$ $c_0\cdot \|g(x)\|\le\|f(x)\| \le c_1\cdot \|g(x)\|$

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

Notationsfallen

Symbolisches Gleichheitszeichen

Üblicherweise 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 wäre: In einer Aussage wie $f (x) = O (g (x))$ ist keine Seite der "Gleichung" durch die andere bestimmt. Aus $f 1 (x) = O (g (x))$ und $f 2 (x) = O (g (x))$ folgt nicht, dass $f 1$ und $f 2$ gleich sind, genausowenig kann man aus $f (x) = O (g 1 (x))$ und $f (x) = O (g 2 (x))$ schließen, dass $O (g 1 (x))$ und $O (g 2 (x))$ dieselbe Klasse sind oder die eine in der anderen enthalten ist.

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

Anwendung in der Komplexitätstheorie

In der Komplexitätstheorie werden die Landau-Symbole vor allem angewendet, um den (minimalen oder maximalen) Bedarf an Speicher (Platzkomplexität) und Zeit (Zeitkomplexität) bezüglich eines bestimmten Maschinenmodells zu beschreiben.

Normalerweise ist es sehr aufwändig oder ganz unmöglich, für ein Problem L eine Funktion $f_L: w \rightarrow 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 |$ zu beschränken. Es ist aber meist ebenfalls zu aufwändig, eine Funktion $f_L: n \rightarrow f_L(n), n = |w|$ anzugeben.

Daher hat man die Landau-Notation entwickelt, die sich auf das asymptotische Verhalten der Funktion 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$ (großer lateinischer Buchstabe O), mit dem man obere Schranken angeben kann; untere Schranken zu finden ist im allgemeinen viel schwieriger. Dabei meint $f(n) \in O(g(n))$ - oft auch $f (n) = O (g (n))$ -, dass eine Konstante $c$ und ein $n_0 \in N$ existieren, so dass für alle $n > n 0$ gilt: $f(n) \le c\cdot g(n)$ . In anderen Worten: Für genügend große Eingabelängen ist der Rechenaufwand $f (n)$ nicht wesentlich größer - d.h. höchstens um einen konstanten Faktor $c$ - als $g (n)$ .

Dabei ist die Funktion $f$ nicht immer bekannt: Die Landau-Notation ist gerade dazu da, den Rechenaufwand (Platzbedarf) abzuschätzen, wenn es zu aufwendig ist, die genaue Funktion anzugeben. Umgekehrt ist es sinnlos, eine Landau-Abschätzung durchzuführen, wenn man eine genaue Funktion $f$ bereits gefunden hat - es sei denn, weil die Abschätzung naturgemäß vereinfachend ist, da beispielsweise Konstanten wegfallen.

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 $Ω$ eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit $O$ entsprechend eine obere Schranke. Bei $O (f)$ wird die Form von $f$ (z.B. $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 können sie nicht direkt mit der Laufzeit des Algorithmus in Verbindung gebracht werden.

Siehe auch: Komplexitätstheorie, Grenzwert (Limes), Paul Bachmann, Edmund Landau

Notation	$x\to a<\infty$	$x\to\infty$
$f(x) \in \hbox{O}(g(x))$	$\exists\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| \le c\cdot \|g(x)\|$	$\exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| \le c\cdot \|g(x)\|$
$f(x) \in \hbox{o}(g(x))$	$\forall\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| < c\cdot \|g(x)\|$	$\forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| < c\cdot \|g(x)\|$
$f(x) \in \Omega(g(x))$	$\exists\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| \ge c\cdot \|g(x)\|$	$\exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| \ge c\cdot \|g(x)\|$
$f(x) \in \omega(g(x))$	$\forall\ c > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $\|f(x)\| > c\cdot \|g(x)\|$	$\forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: \|f(x)\| > c\cdot \|g(x)\|$
$f(x) \in \Theta(g(x))$	$\exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ \epsilon > 0 \ \forall\ x \in \lbrace x: \\|x-a\\|<\epsilon\rbrace :$ $c_0\cdot \|g(x)\|\le\|f(x)\| \le c_1\cdot \|g(x)\|$	$\exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ x_0\ \forall\ x > x_0:$ $c_0\cdot \|g(x)\|\le\|f(x)\| \le c_1\cdot \|g(x)\|$