Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Aufwandsmaß aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

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 Algorithmen danach zu vergleichen, wie "schwierig" oder aufwendig sie zu berechnen sind.

Geschichte

Der Großbuchstabe $\backslash mathcal\{O\}$ (damals eigentlich ein großes Omikron) als Symbol für Ordnung von wurde erstmals vom deutschen Zahlentheoretiker Paul Bachmann in der 1894 erschienenen zweiten Auflage seines Buchs Analytische 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.[http://members.aol.com/jeff570/nth.html Earliest Uses of Symbols of Number Theory, 22. September 2006:] 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).?

Anschauliche Bedeutung

Groß $\backslash mathcal\{O\}$ und klein $o$ sind die am häufigsten verwendeten Landau-Symbole. Darüber hinaus gibt es noch groß Omega $\backslash Omega$, klein omega $\backslash omega$ und Theta $\backslash Theta$.

Sie vergleichen das Wachstum von zwei Funktionen, meist im Unendlichen. In der nachfolgenden Tabelle ist $f$ die Folge oder Funktion, über die eine Aussage getroffen werden soll, und $g$ der einfachste Repräsentant einer Klasse gleich schnell wachsender Funktionen, die als Vergleich dienen.

Beispiele

In den folgenden Beispielen ist $f\; =\; f(x)$ stets als Funktion von $x$ zu verstehen.

Formale Definition

In der folgenden Tabelle bezeichnen $f$ und $g$ entweder
• (Mathematik)/'>Folgen] reeller Zahlen, dann ist $x\backslash in\backslash N$ und der Grenzwert $a=\backslash infty$, oder
* reellwertige Funktionen der reellen Zahlen, dann ist $x\backslash in\backslash R$ und der Grenzwert aus den erweiterten reellen Zahlen: $a\backslash in\backslash R\backslash cup\backslash lbrace-\backslash infty,+\backslash infty\backslash rbrace$, oder
* reellwertige Funktionen beliebiger Limes superior und Limes inferior folgendermaßen definieren:

Definition mittels Quantoren

Äquivalent zur Definition mit Limessymbolen können für einen Quantoren verwendet werden:Analoge Definitionen lassen sich auch für den Fall $x\backslash to\; -\backslash infty$ sowie für einseitige_Grenzwerte geben.

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!\; =\; \backslash sqrt\{2\; \backslash pi\; n\}~\{\backslash left(\backslash frac\{n\}\{e\}\; \backslash right)\}^n\; \backslash left(1\; +\; \backslash Theta\; \backslash left(\backslash frac\{1\}\{n\}\; \backslash right)\; \backslash right)$ für $n\backslash to\; \backslash infty$
und
: $n!\; =\; \backslash mathcal\{O\}\; \backslash left(\backslash sqrt\{n\}\; \backslash sdot\; \backslash left(\backslash frac\{n\}\{e\}\; \backslash right)^n\; \backslash right)$ für $n\backslash to\; \backslash infty$.
Der Faktor $\backslash sqrt\{2\backslash 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+\backslash mathcal\{O\}(x^3)\backslash qquad$ für $x\backslash to\; 0$
dass der Absolutbetrag des Approximationsfehlers 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 angegebenen Ausdruck ist. Für differenzierbare Funktionen gilt beispielsweise
:$f(x+h)=f(x)+hf\text{'}(x)+\backslash hbox\{o\}(h)\backslash qquad$ für $h\backslash to\; 0$,
der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen 0.

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)=\backslash mathcal\{O\}(g(x))$ ist keine Seite der ?Gleichung? durch die andere bestimmt. Aus $f\_1(x)=\backslash mathcal\{O\}(g(x))$ und $f\_2(x)=\backslash mathcal\{O\}(g(x))$ folgt nicht, dass $f\_1$ und $f\_2$ gleich sind. Genauso wenig kann man aus $f(x)=\backslash mathcal\{O\}(g\_1(x))$ und $f(x)=\backslash mathcal\{O\}(g\_2(x))$ schließen, dass $\backslash mathcal\{O\}(g\_1(x))$ und $\backslash mathcal\{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 $\backslash frac\{1\}\{x\}\backslash in\backslash hbox\{o\}\backslash left(\backslash frac\{1\}\{\backslash sqrt\{x\}\}\backslash right)$ für $x\backslash to\backslash infty$, nicht aber für den einseitigen Grenzwert $x\backslash downarrow\; 0$. Normalerweise wird der betrachtete Grenzwert aber aus dem Zusammenhang klar, sodass hier Mehrdeutigkeiten nur selten auftreten.

Was beschreiben Ω, Ο und Θ?

Wie man aus der Definition erkennen kann, beschreiben $\backslash Omega$, $\backslash mathcal\{O\}$ und $\backslash Theta$ Mengen von Funktionen. Folgende Beziehungen zwischen diesen Funktionenmengen lassen sich aus der Definition ableiten:

:$\backslash Theta\; (f)\; =\; \backslash mathcal\{O\}(f)\; \backslash cap\; \backslash Theta(f)$
:$\backslash Theta\; (f)\; =\; \backslash mathcal\{O\}(f)\; \backslash cap\; \backslash Omega\; (f)$
:$\backslash Theta\; (f)\; \backslash subset\; \backslash mathcal\{O\}(f)\; \backslash cup\; \backslash Omega\; (f)$
:$\backslash O\backslash ;\backslash ;\backslash quad\; =\; \backslash omega\; (f)\; \backslash cap\; \backslash hbox\{o\}(f)$

Dennoch nutzt man die laxere Notation mit dem Gleichheitszeichen wie in $f=\backslash mathcal\{O\}(g)$ in der Praxis ausgiebig. Beispielsweise soll der Ausdruck $f(n)=h(n)+\backslash Theta(g(n))$ besagen, dass es Konstanten $c\_1,\; c\_2$ mit
:$h(n)+c\_1\backslash cdot\; g(n)\backslash ,\backslash leq\backslash ,\; f(n)\backslash ,\backslash leq\backslash ,\; h(n)+c\_2\backslash cdot\; g(n)$
gibt.

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\; \backslash 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\; =\; /\text{'}>w|$ zu beschränken. Es ist aber meist ebenfalls zu aufwändig, eine Funktion $f\_L:\; n\; \backslash rightarrow\; f\_L(n),\; n\; =\; |w|$ anzugeben.

Daher hat man die Landau-Notation entwickelt, die sich auf das obere Schranken angeben kann; untere Schranken sind im allgemeinen viel schwieriger zu finden. Dabei meint $f\; \backslash in\; \backslash mathcal\{O\}(g)$ (oft auch $f(n)=\backslash mathcal\{O\}(g(n))$), dass eine Konstante $c$ und ein $n\_0\; \backslash in\; \backslash Bbb\; N$ existieren, so dass für alle $n\; >\; n\_0$ gilt: $f(n)\; \backslash le\; c\backslash cdot\; g(n)$. In anderen Worten: Für alle 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 aufwändig 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 $\backslash Omega$ eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit $\backslash mathcal\{O\}$ entsprechend eine obere Schranke. Bei $\backslash mathcal\{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: Grenzwert (Limes)

Quellen

Weblinks

• O-Notation auf linux-related.de
• Klein, aber o ? Artikel aus der Fachschaftszeitschrift i-mail des Fachbereichs Mathematik/Informatik Halle, Sommersemester 2002 (PDF-Datei)

       VIDEO-NEWS UND ANGEBOTE