Groß-O-Notation

Groß-O-Notation

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 danach zu vergleichen, wie „schwierig“ oder aufwendig sie zu lösen sind.

Inhaltsverzeichnis

Geschichte

Der Großbuchstabe \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.[1]

Anschauliche Bedeutung

\mathcal{O} und o sind die am häufigsten verwendeten Landau-Symbole. Darüber hinaus gibt es noch Ω (Groß-Omega), ω (Klein-Omega) und Θ (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.

Notation Anschauliche Bedeutung
f \in \mathcal{O}(g) f wächst nicht wesentlich schneller als g
f \in \hbox{o}(g) f wächst langsamer als g
f \in \Omega(g) f wächst mindestens so schnell wie g
f \in \omega(g) f wächst schneller als g
f \in \Theta(g) f wächst genauso schnell wie g

Beispiele

In den folgenden Beispielen ist f stets als Funktion von x zu verstehen.

Notation Bedeutung Anschauliche Erklärung Beispiele für Laufzeiten
f \in \mathcal{O}(1) f ist beschränkt f überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments). Nachschlagen des i-ten Elementes in einem Array.
f \in \mathcal{O}(\log x) f logarithmisches Wachstum f wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt.

Merke: Die Basis des Logarithmus ist egal.

Binäre Suche im sortierten Feld mit x Einträgen
f \in \mathcal{O}(\sqrt{x}) f Wachstum wie die Wurzelfunktion f wächst ungefähr auf das Doppelte, wenn sich das Argument vervierfacht
f \in \mathcal{O}(x) f lineares Wachstum f wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt. Suche im unsortierten Feld mit x Einträgen
f \in \mathcal{O}(x \log x) f super-lineares Wachstum Fortgeschrittenere Algorithmen zum Sortieren von x Zahlen

Mergesort, Heapsort

f \in \mathcal{O}(x^2) f quadratisches Wachstum f wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt Einfache Algorithmen zum Sortieren von x Zahlen

Bubblesort

f \in \mathcal{O}(2^x) f exponentielles Wachstum f wächst ungefähr auf das Doppelte, wenn sich das Argument um eins erhöht

Man kann hier jede Basis c > 1 verwenden, z.B e oder 10.

Rekursive Variante der Fibonacci-Folge
f \in \mathcal{O}(x!) f faktorielles Wachstum f wächst ungefähr um das x-fache, wenn sich das Argument um eins von x − 1 auf x erhöht. Bogosort

Formale Definition

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

Äquivalent zur Definition mit Limessymbolen können für einen normierten 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
f \in \mathcal{O}(g) \exists\ c > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: |f(x)| \le c\cdot |g(x)|
f \in \hbox{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 \Omega(g) \exists\ c > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: |f(x)| \ge c\cdot |g(x)|
f \in \omega(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 \Theta(g) \exists\ c_0>0\ \exists\ c_1 > 0\ \exists\ \varepsilon > 0 \ \forall\ x \in \lbrace x: d(x, a)<\varepsilon\rbrace: c_0\cdot |g(x)|\le|f(x)| \le c_1\cdot |g(x)|
Notation x\to\infty
f \in \mathcal{O}(g) \exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| \le c\cdot |g(x)|
f \in \hbox{o}(g) \forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| < c\cdot |g(x)|
f \in \Omega(g) \exists\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| \ge c\cdot |g(x)|
f \in \omega(g) \forall\ c > 0\ \exists\ x_0\ \forall\ x > x_0: |f(x)| > c\cdot |g(x)|
f \in \Theta(g) \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.

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! = \sqrt{2 \pi n}~{\left(\frac{n}{e} \right)}^n \left(1 + \Theta \left(\frac{1}{n} \right) \right) für n\to \infty

und

n! = \mathcal{O} \left(\sqrt{n} \sdot \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+\mathcal{O}(x^3)\qquad für x\to 0,

dass der Absolutbetrag des Approximationsfehlers kleiner als eine Konstante mal x3 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'(x)+\hbox{o}(h)\qquad für h\to 0,

der Fehler bei Approximation durch die Tangente geht also schneller als linear gegen 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 wären: In einer Aussage wie f(x)=\mathcal{O}(g(x)) ist keine Seite der „Gleichung“ durch die andere bestimmt. Aus f_1(x)=\mathcal{O}(g(x)) und f_2(x)=\mathcal{O}(g(x)) folgt nicht, dass f1 und f2 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)) wäre also formal korrekt.

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.

Was beschreiben Ω, Ο und Θ?

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

\begin{align}
\Theta (f) \,&=\, \mathcal{O}(f) \cap \Theta(f) \\
\Theta (f) \,&=\, \mathcal{O}(f) \cap \Omega (f) \\
\Theta (f) \,&\subset\, \mathcal{O}(f) \cup \Omega (f) \\
\O \,&=\, \omega (f) \cap \hbox{o}(f) 
\end{align}

Dennoch nutzt man die laxere Notation mit dem Gleichheitszeichen wie in f=\mathcal{O}(g) in der Praxis ausgiebig. Beispielsweise soll der Ausdruck f(n) = h(n) + Θ(g(n)) besagen, dass es Konstanten c1,c2 mit

h(n)+c_1\cdot g(n)\,\leq\, f(n)\,\leq\, h(n)+c_2\cdot g(n) \quad (\forall\,n\in\mathbb{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 \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 fL 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 \mathcal{O} (großer lateinischer Buchstabe „O“), mit dem man obere Schranken angeben kann; untere Schranken sind im allgemeinen viel schwieriger zu finden. Dabei meint f \in \mathcal{O}(g) (oft auch f(n)=\mathcal{O}(g(n))), dass eine Konstante c > 0 und ein n_0 \in \Bbb N existieren, so dass für alle n > n0 gilt: f(n) \le c\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 Ω eine untere Schranke für beispielsweise die asymptotische Laufzeit angeben, mit \mathcal{O} entsprechend eine obere Schranke. Bei \mathcal{O}(f) wird die Form von f (z. B. f(n) = n2) 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

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Notation (Musik) — Als Notation bezeichnet man in der Musik das grafische Festhalten von musikalischen Parametern wie Tonhöhe, dauer und lautstärke in einer dazu entwickelten Notenschrift. Sie dient einerseits dazu, bereits bekannte Musikstücke schriftlich zu… …   Deutsch Wikipedia

  • Ungarische Notation — Bei der ungarischen Notation handelt es sich um eine von Programmierern verwendete Namenskonvention zur Wahl von Bezeichnern für Variablen, Funktionen usw. Ihren Namen verdankt die ungarische Notation dem in einem (englischen) Programmtext… …   Deutsch Wikipedia

  • Hungarian Notation — Bei der ungarischen Notation handelt es sich um eine von Programmierern verwendete Namenskonvention zur Wahl von Bezeichnern für Variablen, Funktionen usw. Der Name rührt zum einen daher, dass der Erfinder der Konvention, Charles Simonyi, ein… …   Deutsch Wikipedia

  • Min-Max-Notation — Die Min Max Notation (auch (min,max) Notation) ist eine Art, die Kardinalität einer Beziehung zwischen Entitätstypen in einem Entity Relationship Modell einzuschränken. Sie wurde eingeführt, weil die Chen Notation nur beschränkte Aussagen zu… …   Deutsch Wikipedia

  • Musikalische Notation — Als Notation bezeichnet man in der Musik das grafische Festhalten von musikalischen Parametern wie Tonhöhe, dauer und lautstärke in einer dazu entwickelten Notenschrift. Sie dient einerseits dazu, bereits bekannte Musikstücke schriftlich zu… …   Deutsch Wikipedia

  • Landau-Notation — 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… …   Deutsch Wikipedia

  • O-Notation — 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… …   Deutsch Wikipedia

  • JavaScript Object Notation — Die JavaScript Object Notation, kurz JSON (IPA: /ˈdʒeɪsʌn/), ist ein kompaktes Datenformat in für Mensch und Maschine einfach lesbarer Textform zum Zweck des Datenaustauschs zwischen Anwendungen. Jedes gültige JSON Dokument soll ein gültiges… …   Deutsch Wikipedia

  • Steinhaus-Moser-Notation — Die Steinhaus Moser Notation ist eine Darstellungsweise für sehr große Zahlen. Sie wurde 1950[1] von dem polnischen Mathematiker Hugo Steinhaus als Kreisnotation vorgeschlagen und später durch den Österreicher Leo Moser auf die Polygonnotation… …   Deutsch Wikipedia

  • Forsyth-Edwards Notation — Die Forsyth Edwards Notation (FEN) oder in der erweiterten Form (X FEN) ist eine Kurznotation, mit der jede beliebige Brettstellung im Schach niedergeschrieben werden kann. Inhaltsverzeichnis 1 Aufbau 1.1 1. Gruppe 1.2 2. Gruppe 1.3 3. Gruppe 1 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”