In der Mathematik wird große O Notation verwendet, um das Begrenzungsverhalten einer Funktion zu beschreiben, wenn das Argument zu einem besonderen Wert oder Unendlichkeit gewöhnlich in Bezug auf einfachere Funktionen neigt. Es ist ein Mitglied einer größeren Familie von Notationen, die Notation von Landau, Bachmann-Landauer-Notation oder asymptotische Notation genannt wird. In der Informatik wird große O Notation verwendet, um Algorithmen dadurch zu klassifizieren, wie sie (d. h., in ihrer Verarbeitungszeit oder Arbeitsraumvoraussetzungen) zu Änderungen in der Eingangsgröße antworten.

Große O Notation charakterisiert Funktionen gemäß ihren Wachstumsraten: Verschiedene Funktionen mit derselben Wachstumsrate können mit derselben O Notation vertreten werden. Eine Beschreibung einer Funktion in Bezug auf die große O Notation stellt gewöhnlich nur einen oberen zur Verfügung hat zur Wachstumsrate der Funktion gebunden. Vereinigt mit der großen O Notation sind mehrere zusammenhängende Notationen, mit den Symbolen o, Ω, ω, und Θ, um andere Arten von Grenzen auf asymptotischen Wachstumsraten zu beschreiben.

Große O Notation wird auch in vielen anderen Feldern verwendet, um ähnliche Schätzungen zur Verfügung zu stellen.

Formelle Definition

Lassen Sie f (x) und g (x) zwei auf einer Teilmenge der reellen Zahlen definierte Funktionen sein. Man schreibt

:

wenn, und nur wenn es eine positive unveränderliche solche M gibt, dass für alle genug großen Werte von x, f (x) am grössten Teil der M ist, durch g (x) im absoluten Wert multipliziert hat. D. h. f (x) = O (g (x)) wenn, und nur wenn dort eine positive reelle Zahl M und eine reelle Zahl x solch dass besteht

:

In vielen Zusammenhängen geht die Annahme, dass wir uns für die Wachstumsrate als die Variable x interessieren, zur Unendlichkeit wird unfestgesetzt verlassen, und man schreibt einfacher dass f (x) = O (g (x)).

Die Notation kann auch verwendet werden, um das Verhalten von f in der Nähe von einer reellen Zahl (häufig, = 0) zu beschreiben: Wir sagen

:

wenn, und nur wenn dort positive Zahlen δ und solche M dass bestehen

:

Wenn g (x) Nichtnull für Werte von x genug in der Nähe von a ist, können beide dieser Definitionen mit der höheren Grenze vereinigt werden:

:

wenn und nur wenn

:

Beispiel

Im typischen Gebrauch wird die formelle Definition der O Notation direkt nicht verwendet; eher wird die O Notation für eine Funktion f (x) durch die folgenden Vereinfachungsregeln abgeleitet:

• Wenn f (x) eine Summe von mehreren Begriffen ist, wird derjenige mit der größten Wachstumsrate, und alles andere weggelassen behalten.
• Wenn f (x) ein Produkt von mehreren Faktoren, irgendwelche Konstanten ist (Begriffe im Produkt, die von x nicht abhängen), werden weggelassen.

Lassen Sie zum Beispiel und nehmen Sie an, dass wir diese Funktion, mit O Notation vereinfachen, seine Wachstumsrate als x Annäherungsunendlichkeit beschreiben möchten. Diese Funktion ist die Summe von drei Begriffen: 6x, 2x, und 5. Dieser drei Begriffe ist derjenige mit der höchsten Wachstumsrate derjenige mit der größten Hochzahl als eine Funktion von x, nämlich 6x. Jetzt kann man die zweite Regel anwenden: 6x ist ein Produkt 6 und x, in dem der erste Faktor von x nicht abhängt. Das Auslassen dieses Faktors läuft auf die vereinfachte Form x hinaus. So sagen wir, dass f (x) ein große oh von (x) ist oder mathematisch wir f (x) = O (x) schreiben können.

Man kann diese Berechnung mit der formellen Definition bestätigen: Lassen Sie f (x) = 6x  2x + 5 und g (x) = x. Die formelle Definition von oben, die Erklärung anwendend, dass f (x) = O (x) zu seiner Vergrößerung, gleichwertig

ist:

für etwas passende Wahl von x und M und für den ganzen x > x. Um das zu beweisen, lassen Sie x = 1 und M = 13. Dann, für den ganzen x > x:

:

&\\le 6x^4 + 2x^4 + 5x^4 \\

&\\le 13x^4 \\

&\\le 13|x^4 |\end {richten} </Mathematik> {aus}

so

:

Gebrauch

Große O Notation hat zwei Hauptgebiete der Anwendung. In der Mathematik wird es allgemein verwendet, um zu beschreiben, wie nah eine begrenzte Reihe einer gegebenen Funktion, besonders im Fall von einer gestutzten Reihe von Taylor oder asymptotischer Vergrößerung näher kommt. In der Informatik ist es in der Analyse von Algorithmen nützlich. In beiden Anwendungen die Funktion g (x) wird das Erscheinen innerhalb des O normalerweise (...) gewählt, um so einfach zu sein wie möglich, unveränderliche Faktoren und niedrigere Ordnungsbegriffe weglassend.

Es gibt zwei formell nahe, aber merklich verschieden, Gebrauch dieser Notation: unendlicher asymptotics und unendlich kleiner asymptotics. Diese Unterscheidung ist nur in der Anwendung und nicht im Prinzip jedoch — die formelle Definition für den "großen O" ist dasselbe für beide Fälle nur mit verschiedenen Grenzen für das Funktionsargument.

Unendlicher asymptotics

Große O Notation ist nützlich, wenn sie Algorithmen für die Leistungsfähigkeit analysiert. Zum Beispiel, die Zeit (oder die Zahl von Schritten) es nimmt, um ein Problem der Größe n zu vollenden, könnte gefunden werden, T (n) = 4n  2n + 2 zu sein.

Da n groß wächst, wird der N-Begriff kommen, um vorzuherrschen, so dass alle anderen Begriffe — zum Beispiel vernachlässigt werden können, wenn n = 500, der Begriff 4n 1000mal so groß ist wie 2n Begriff. Das Ignorieren der Letzteren würde unwesentliche Wirkung auf den Wert des Ausdrucks zu den meisten Zwecken haben.

Weiter werden die Koeffizienten irrelevant, wenn wir uns mit einer anderer Ordnung des Ausdrucks wie ein Ausdruck vergleichen, der einen Begriff n oder n enthält. Selbst wenn T (n) = 1,000,000n, wenn U (n) = n, die Letzteren immer den ersteren übertreffen werden, sobald n größer wächst als 1,000,000 (T (1,000,000) = 1,000,000 = U (1,000,000)). Zusätzlich hängt die Zahl von Schritten von den Details des Maschinenmodells ab, auf dem der Algorithmus läuft, aber verschiedene Typen von Maschinen ändern sich normalerweise durch nur einen unveränderlichen Faktor in der Zahl von Schritten, musste einen Algorithmus durchführen.

So gewinnt die große O Notation, was bleibt: Wir schreiben irgendeinem

:oder:

und sagen Sie, dass der Algorithmus Ordnung der n Zeitkompliziertheit hat.

Bemerken Sie, dass "=" nicht gemeint wird, um auszudrücken, "ist" in seinem normalen mathematischen Sinn gleich, aber eher "ist" ein mehr umgangssprachlicher, so ist der zweite Ausdruck technisch genau (sieh die "Gleichheitszeichen"-Diskussion unten), während das erste ein allgemeiner Missbrauch der Notation ist.

Unendlich kleiner asymptotics

Großer O kann auch verwendet werden, um den Fehlerbegriff in einer Annäherung an eine mathematische Funktion zu beschreiben. Die bedeutendsten Begriffe werden ausführlich, und dann meist geschrieben - bedeutende Begriffe werden in einem einzelnen großen O-Begriff zusammengefasst. Zum Beispiel,

:

drückt die Tatsache aus, dass der Fehler, der Unterschied, im absoluten Wert kleiner ist als einige unveränderliche Male, wenn an 0 nah genug ist.

Eigenschaften

Wenn eine Funktion f (n) als eine begrenzte Summe anderer Funktionen geschrieben werden kann, dann bestimmt das schnellste Wachsen von demjenigen die Ordnung von

f (n). Zum Beispiel

:

Insbesondere wenn eine Funktion durch ein Polynom in n begrenzt werden kann, dann weil neigt n zur Unendlichkeit, man kann Begriffe der niedrigeren Ordnung des Polynoms ignorieren.

O (n) und O (c) sind sehr verschieden. Der Letztere wächst viel viel schneller, egal wie groß der unveränderliche c ist (als lange, weil es größer ist als ein). Eine Funktion, die schneller wächst als jede Macht von n, wird Superpolynom genannt. Derjenige, der langsamer wächst als jede Exponentialfunktion der Form, wird Subexponential-genannt. Ein Algorithmus kann Zeit verlangen, die sowohl Superpolynom als auch Subexponential-ist; Beispiele davon schließen die schnellsten bekannten Algorithmen für die ganze Zahl factorization ein.

O (loggen n), ist genau dasselbe als O (Klotz (n)). Die Logarithmen unterscheiden sich nur durch einen unveränderlichen Faktor (da

) und so ignoriert die große O Notation das. Ähnlich ist der Klotz mit verschiedenen unveränderlichen Basen gleichwertig. Exponentials mit verschiedenen Basen sind andererseits nicht derselben Ordnung. Zum Beispiel, und sind nicht derselben Ordnung.

Das Ändern von Einheiten kann oder kann die Ordnung des resultierenden Algorithmus nicht betreffen. Das Ändern von Einheiten ist zum Multiplizieren der passenden Variable durch eine Konstante gleichwertig, wo auch immer es erscheint. Zum Beispiel, wenn ein Algorithmus in der Ordnung von n läuft, bedeutet das Ersetzen n durch cn die Algorithmus-Läufe in der Ordnung, und die große O Notation ignoriert die Konstante. Das kann als geschrieben werden. Wenn, jedoch, ein Algorithmus in der Ordnung dessen läuft, gibt das Ersetzen n mit cn. Das ist zu im Allgemeinen nicht gleichwertig.

Das Ändern der Variable kann die Ordnung des resultierenden Algorithmus betreffen. Zum Beispiel, wenn eine Laufzeit eines Algorithmus O (n), wenn gemessen, in Bezug auf die Nummer n von Ziffern eines Eingangs Nummer x ist, dann ist seine Laufzeit O (loggen Sie x) wenn gemessen als eine Funktion des Eingangs Nummer x selbst, weil n = Θ (loggen x).

Produkt

::

Summe

:

f_2\in O (g_2) \, \Rightarrow f_1 + f_2\in O (|g_1 | + |g_2 |) \, </math>

:: Das bezieht ein, was bedeutet, dass das ein konvexer Kegel ist.

:If f und g sind positive Funktionen,

Multiplikation durch eine Konstante

:Let k, eine Konstante sein. Dann:

: wenn k Nichtnull ist.

:

Vielfache Variablen

Großer O (und wenig o und Ω...) kann auch mit vielfachen Variablen verwendet werden.

Um großen O formell für vielfache Variablen zu definieren, denken Sie, und sind zwei Funktionen, die auf einer Teilmenge dessen definiert sind. Wir sagen

:wenn und nur wenn:

Zum Beispiel, die Behauptung

:

behauptet, dass dort Konstanten C und solche M dass bestehen

:

wo g (n, m) durch definiert wird

:

Bemerken Sie, dass diese Definition alle Koordinaten erlaubt, zur Unendlichkeit zuzunehmen. Insbesondere die Behauptung

:

(d. h.,) ist von ziemlich verschieden

:

(d. h.,).

Sachen der Notation

Gleichheitszeichen

Die Behauptung "f (x) ist O (g (x))" so definiert oben wird gewöhnlich geschrieben wie f (x) = O (g (x)). Einige denken, dass das ein Missbrauch der Notation ist, seitdem der Gebrauch des Gleichheitszeichens irreführend sein konnte, weil es eine Symmetrie andeutet, die diese Behauptung nicht hat. Wie de Bruijn sagt, O (x) = O (x) ist wahr, aber O (x) = O (x) ist nicht. Knuth beschreibt solche Behauptungen als "Einweggleichheiten" seitdem, wenn die Seiten umgekehrt werden konnten, "konnten wir lächerliche Dinge wie n = n von der Identität n = O (n) und n = O (n) ableiten."

Aus diesen Gründen würde es genauer sein, um Satz-Notation zu verwenden und f (x)  O (g (x)) zu schreiben, O (g (x)) als die Klasse aller Funktionen h (x) solch dass |h (x) |  Cg (x) | für einen unveränderlichen C denkend. Jedoch ist der Gebrauch des Gleichheitszeichens üblich. Knuth hat darauf hingewiesen, dass "Mathematiker gewöhnlich = Zeichen verwenden, wie sie das Wort verwenden, 'ist' in Englisch: Aristoteles ist ein Mann, aber ein Mann ist nicht notwendigerweise Aristoteles."

Andere arithmetische Maschinenbediener

Große O Notation kann auch in Verbindung mit anderen arithmetischen Maschinenbedienern in mehr komplizierten Gleichungen verwendet werden. Zum Beispiel, h (x) + O (f (x)) zeigt die Sammlung von Funktionen an, die das Wachstum von h (x) plus ein Teil haben, dessen Wachstum auf diesen von f (x) beschränkt wird. So,

:

drückt dasselbe als aus

:

Beispiel

Nehmen Sie an, dass ein Algorithmus entwickelt wird, um auf einer Reihe von n Elementen zu funktionieren. Seine Entwickler interessieren sich für die Entdeckung einer Funktion T (n), der ausdrücken wird, wie lange der Algorithmus in den geführten (in etwas willkürlichem Maß der Zeit) in Bezug auf die Zahl der Elemente im Eingangssatz bringen wird. Der Algorithmus arbeitet durch das erste Benennen eines Unterprogramms, um die Elemente im Satz zu sortieren und dann seine eigenen Operationen durchzuführen. Die Sorte hat eine bekannte Zeitkompliziertheit von O (n), und nachdem das Unterprogramm läuft, muss der Algorithmus eine zusätzliche Zeit nehmen, bevor es endet. So kann die gesamte Zeitkompliziertheit des Algorithmus als ausgedrückt werden

:

Das kann vielleicht durch das Ersetzen O (n) mit "etwas Funktion am leichtesten gelesen werden, die asymptotisch nicht schneller wächst als n ". Wieder ignoriert dieser Gebrauch etwas von der formellen Bedeutung" =" und "+" Symbole, aber es erlaubt wirklich, die große O Notation als eine Art günstiger Platzhalter zu verwenden.

Behauptung von Variablen

Eine andere Eigenschaft der Notation, obwohl weniger außergewöhnlich, ist, dass Funktionsargumente eventuell aus dem Zusammenhang abgeleitet werden müssen, wenn mehrere Variablen beteiligt werden. Die folgende zwei Rechte große O Notationen hat drastisch verschiedene Bedeutungen:

::

Der erste Fall stellt fest, dass f (m) polynomisches Wachstum ausstellt, während das zweite, m> 1 annehmend, feststellt, dass g (n) Exponentialwachstum ausstellt.

Um Verwirrung zu vermeiden, verwenden einige Autoren die Notation

:

anstatt des weniger ausführlichen

:

Vielfacher Gebrauch

Im mehr komplizierten Gebrauch, O kann (...) in verschiedenen Plätzen in einer Gleichung sogar mehrere Male auf jeder Seite erscheinen. Zum Beispiel, der folgende sind für wahr

:::

Die Bedeutung solcher Behauptungen ist wie folgt: Für irgendwelche Funktionen, die jeden O (...) auf der linken Seite befriedigen, gibt es einige Funktionen, die jeden O (...) rechts, solch befriedigen, dass das Ersetzen aller dieser Funktionen in die Gleichung die zwei Seiten gleich macht. Zum Beispiel, die dritte Gleichung über Mitteln: "Für jede Funktion gibt es etwas solche Funktion dass." In Bezug auf die "Satz-Notation" oben ist die Bedeutung, dass die Klasse von von der linken Seite vertretenen Funktionen eine Teilmenge der Klasse von von der richtigen Seite vertretenen Funktionen ist. In diesem Gebrauch "=" ist ein formelles Symbol, das verschieden vom üblichen Gebrauch "=" nicht eine symmetrische Beziehung ist. So zum Beispiel bezieht die falsche Angabe nicht ein.

Ordnungen von allgemeinen Funktionen

Hier ist eine Liste von Klassen von Funktionen, auf die allgemein gestoßen wird, wenn man die Laufzeit eines Algorithmus analysiert. In jedem Fall ist c eine Konstante und N-Zunahmen ohne bestimmten. Die langsamer wachsenden Funktionen werden allgemein zuerst verzeichnet.

Die Behauptung wird manchmal geschwächt zu, einfachere Formeln für die asymptotische Kompliziertheit abzuleiten.

Für irgendwelchen und, ist eine Teilmenge für irgendwelchen, so kann als ein Polynom mit einer größeren Ordnung betrachtet werden.

Zusammenhängende asymptotische Notationen

Großer O ist die meistens verwendete asymptotische Notation, um Funktionen zu vergleichen, obwohl in vielen Fällen Großer O durch Großen Theta Θ für asymptotisch dichtere Grenzen ersetzt werden kann. Hier definieren wir einige zusammenhängende Notationen in Bezug auf Großen O, bis zur Familie von Bachmann-Landauer-Notationen fortschreitend, denen Große O Notation gehört.

Wenig-o Notation

Die Beziehung wird gelesen, wie "wenig-o ist". Intuitiv bedeutet es, dass das viel schneller wächst als, oder ähnlich das Wachstum dessen nichts im Vergleich zu diesem dessen ist. Es nimmt an, dass f und g beide Funktionen einer Variable sind. Formell, f (n) = o (g (n)) als Mittel, dass für jeden positiven unveränderlichen ε dort ein unveränderlicher solcher N dass besteht

:

Bemerken Sie den Unterschied zwischen der früheren formellen Definition für die große-O Notation und der gegenwärtigen Definition wenig-o: Während der erstere für mindestens eine unveränderliche M die Letzteren wahr sein muss, muss für jeden positiven unveränderlichen ε, jedoch klein halten. Auf diese Weise wenig-o gibt Notation eine stärkere Erklärung ab als die entsprechende große-O Notation: Jede Funktion, die wenig-o g ist, ist auch von g, aber nicht jeder Funktion groß-O, die großer-O g ist, ist auch wenig-o g (zum Beispiel g selbst ist nicht, wenn es nahe  nicht identisch Null-ist).

Wenn g (x) Nichtnull ist, oder mindestens Nichtnull außer einem bestimmten Punkt wird, ist die Beziehung f (x) = o (g (x)) zu gleichwertig

:

Zum Beispiel,

Wenig-o ist Notation in der Mathematik üblich, aber in der Informatik seltener. In der Informatik ist die Variable (und Funktionswert) meistenteils eine natürliche Zahl. In der Mathematik sind die Variable und Funktionswerte häufig reelle Zahlen. Die folgenden Eigenschaften können nützlich sein:

• (und so gelten die obengenannten Eigenschaften mit den meisten Kombinationen von o und O).

Als mit der großen O Notation "ist" die Behauptung wird gewöhnlich als geschrieben, der ein geringer Missbrauch der Notation ist.

Familie von Bachmann-Landauer-Notationen

Bachmann-Landauer-Notation wurde um mehrere Gedächtniskunst entworfen, die so in gezeigt ist Wie, schließlich... Säule oben und in den Kugeln unten. Um auf diese begrifflich zuzugreifen, kann Gedächtniskunst, "omicron" gelesen werden "O-Mikron" und "Omega" können "Omega" gelesen werden. Außerdem ist der Kleinbuchstabe gegen die Kapitalisierung der griechischen Briefe in der Bachmann-Landauer-Notation mnemonisch.

• Das o-'micron mnemonische: Vom O-Mikron-Lesen und kann als "O-smaller gedacht werden als" und "o-smaller als" beziehungsweise. Das Mikro-/kleiner mnemonisch bezieht sich auf: Für den genug großen Eingangsparameter , wächst in einem Tempo, das künftig weniger als 'betrachten kann oder.
• Das o-'mega mnemonische: Vom Omega-Lesen und kann als "O-larger gedacht werden als". Das mega/larger mnemonisch bezieht sich auf: Für den genug großen Eingangsparameter , wächst in einem Tempo, das künftig 'größer sein kann als Bewertung oder.
• Die mnemonische Großschrift: Das mnemonisch erinnert uns, wenn man die griechischen Großschrift-Briefe in verwendet und: Für den genug großen Eingangsparameter , wächst in einem Tempo, das künftig der Bewertung 'gleich sein kann.
• Der mnemonische Kleinbuchstabe: Das mnemonisch erinnert uns, wenn man die griechischen Kleinbriefe in verwendet und: Für den genug großen Eingangsparameter , wächst in einem Tempo, das künftig 'inequal zur Bewertung ist.

Beiseite von der Großen O Notation sind Großer Theta Θ und Großes Omega Ω Notationen die in der Informatik meistenteils verwendeten zwei; das Kleine Omega ω Notation wird in der Informatik selten verwendet.

Verwenden Sie in der Informatik

Informell, besonders in der Informatik, wird die Große O Notation häufig erlaubt, etwas missbraucht zu werden, um einen asymptotischen gebundenen dichten zu beschreiben, wo das Verwenden Großer Notation von Theta Θ in einem gegebenen Zusammenhang sachlicher passend sein könnte. Zum Beispiel, wenn er eine Funktion denkt, ist der ganze folgende allgemein annehmbar, aber die Beengtheit von bestimmten (d. h., Kugeln 2 und 3 unten) wird gewöhnlich über die Laxheit von bestimmten (d. h., Nummer 1 unten) stark bevorzugt.

1. T (n) = O (n), der zu T (n)  O (n) identisch

istT (n) = O (n), der zu T (n)  O (n) identisch ist

1. T (n) = Θ (n), der zu T (n)  Θ (n) identisch ist.

Die gleichwertigen englischen Behauptungen sind beziehungsweise:

1. T wächst (n) asymptotisch nicht schneller als n

T wächst (n) asymptotisch nicht schneller als n

1. T wächst (n) asymptotisch so schnell wie n.

So, während alle drei Behauptungen progressiv wahr sind, wird mehr Information in jedem enthalten. In einigen Feldern, jedoch, würde die Große O Notation (Nummer 2 in den Listen oben) allgemeiner verwendet als die Große Theta Notation (Kugeln Nummer 3 in den Listen oben), weil Funktionen, die langsamer wachsen, wünschenswerter sind. Zum Beispiel, wenn die Laufzeit eines kürzlich entwickelten Algorithmus für die Eingangsgröße vertritt, könnten die Erfinder und Benutzer des Algorithmus mehr dazu neigen, einen oberen gebundenen asymptotischen zu stellen, wie lange es bringen wird, um zu laufen, ohne eine ausführliche Erklärung über das niedrigere gebundene asymptotische abzugeben.

Erweiterungen auf die Bachmann-Landauer-Notationen

Eine andere in der Informatik manchmal verwendete Notation ist Õ (lesen Sie weich-O): f (n) = Õ (g (n)) ist Schnellschrift

für f (n) = O (g loggen (n) g (n)), für einen k. Im Wesentlichen ist es Große O Notation, logarithmische Faktoren ignorierend, weil die Wachstumsrate-Effekten einer anderen superlogarithmischen Funktion eine Wachstumsrate-Explosion für großformatige Eingangsrahmen anzeigen, die für das Voraussagen schlechten Zeitverhaltens wichtiger ist als die durch den Faktor (En) des logarithmischen Wachstums beigetragenen Effekten des feineren Punkts. Diese Notation wird häufig verwendet, um das "kleinliche" innerhalb von Wachstumsraten zu begegnen, die, wie zu dicht begrenzt, für die Sachen in der Nähe festgesetzt werden (da n loggen, ist immer o (n) für jeden unveränderlichen k und jeden ε> 0).

Die L Notation, definiert als

:ist

für Funktionen günstig, die zwischen dem Polynom und Exponential-sind.

Generalisationen und verwandter Gebrauch

Die Generalisation zu Funktionen, die Werte in jedem normed Vektorraum nehmen, ist aufrichtig (das Ersetzen absoluter Werte durch Normen), wo f und g ihre Werte in demselben Raum nicht zu nehmen brauchen. Eine Generalisation zu Funktionen g nehmende Werte in jeder topologischen Gruppe ist auch möglich.

Der "Begrenzungsprozess" xx kann auch durch das Einführen einer willkürlichen Filterbasis, d. h. zu geleiteten Netzen f und g verallgemeinert werden.

Die o Notation kann verwendet werden, um Ableitungen und differentiability in ziemlich allgemeinen Räumen, und auch (asymptotical) Gleichwertigkeit von Funktionen, zu definieren

:

der eine Gleichwertigkeitsbeziehung und ein einschränkenderer Begriff ist, als die Beziehung "f Θ (g)" von oben ist. (Es nimmt dazu ab, wenn f und g positive echte geschätzte Funktionen sind.) Zum Beispiel, 2x ist Θ (x), aber 2x  ist x nicht o (x).

Graph-Theorie

Es ist häufig für den bestimmten die Laufzeit von Graph-Algorithmen nützlich. Verschieden von den meisten anderen rechenbetonten Problemen, für einen Graphen G = (V, E) gibt es zwei relevante Rahmen, die die Größe des Eingangs beschreiben: die Zahl |V Scheitelpunkte im Graphen und der Zahl |E Ränder im Graphen. Innerhalb der asymptotischen Notation (und nur dort) ist es üblich, die Symbole V und E zu verwenden, wenn jemand wirklich |V und |E vorhat. Diese Tagung vereinfacht asymptotische Funktionen, und machen Sie sie leicht lesbar. Die Symbole V und E werden innerhalb der asymptotischen Notation mit ihrer wörtlichen Bedeutung nie verwendet, da die Zahl von Scheitelpunkten und Rändern nichtnegativ sein muss, so riskiert dieser Missbrauch der Notation Zweideutigkeit nicht. Zum Beispiel Mittel für einen passenden metrischen von Graphen. Eine andere allgemeine Tagung — sich auf die Werte |V und |E durch die Namen n und M beziehungsweise beziehend — weicht diese Zweideutigkeit aus.

Geschichte

Die Notation wurde zuerst vom Zahl-Theoretiker Paul Bachmann 1894, im zweiten Volumen seines Buches Analytische Zahlentheorie eingeführt ("analytische Zahlentheorie"), dessen erstes Volumen (noch nicht große O Notation enthaltend), 1892 veröffentlicht wurde. Die Notation wurde in der Arbeit des Zahl-Theoretikers Edmund Landau verbreitet; folglich wird es manchmal ein Symbol von Landau genannt. Es wurde in der Informatik von Donald Knuth verbreitet, der die zusammenhängenden Notationen von Omega und Theta wiedereingeführt hat. Er hat auch bemerkt, dass (dann dunkel) Omega-Notation von Hardy und Littlewood unter einer ein bisschen verschiedenen Bedeutung eingeführt worden war, und die aktuelle Definition vorgeschlagen hat. Die Symbole von Hardy waren (in Bezug auf die moderne O Notation)

: und

andere ähnliche Symbole wurden manchmal, solcher als verwendet und.

Das große-O, "für Ordnung" eintretend, war ursprünglich ein Kapital omicron; heute wird der identisch aussehende lateinische Großbuchstabe O verwendet, aber nie die Ziffer-Null.

Siehe auch

• Asymptotische Vergrößerung: Annäherung von Funktionen, die Formel von Taylor verallgemeinernd
• Asymptotisch optimal: Ein Ausdruck hat oft gepflegt, einen Algorithmus zu beschreiben, der einen oberen gebunden asymptotisch innerhalb einer Konstante eines niedrigeren hat, der für das Problem gebunden ist
• Beschränken Sie höher und beschränken Sie untergeordnet: Eine Erklärung von etwas von der Grenze-Notation, die in diesem Artikel verwendet ist
• Der Lehrsatz von Nachbin: Eine genaue Methode, komplizierte analytische Funktionen zu begrenzen, so dass sich das Gebiet der Konvergenz des Integrals verwandelt, kann festgesetzt werden
• Großer O in der Wahrscheinlichkeitsnotation: O, o
• Rechenbetonte Kompliziertheitstheorie: Ein Teilfeld, das stark mit diesem Artikel verbunden ist

Weiterführende Literatur

• Paul Bachmann. Sterben Sie Analytische Zahlentheorie. Zahlentheorie. pt. Das 2 Leipzig:B. G. Teubner, 1894.
• Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen. 2 vols. Leipzig:B. G. Teubner, 1909.
• G. H. Hardy. Ordnungen der Unendlichkeit: Der 'Infinitärcalcül' von Paul du Bois-Reymond, 1910.
• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 1: Grundsätzliche Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89683-4. Abschnitt 1.2.11: Asymptotische Darstellungen, Seiten 107-123.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 3.1: Asymptotische Notation, Seiten 41-50.

• Seiten 226-228 des Abschnitts 7.1: Das Messen der Kompliziertheit.
• Jeremy Avigad, Kevin Donnelly. Das Formalisieren O Notation in Isabelle/HOL
• Paul E. Black, "große-O Notation", im Wörterbuch von Algorithmen und Datenstrukturen [online], Paul E. Black, Hrsg., amerikanisches Nationales Institut für Standards und Technologie. Am 11. März 2005. Wiederbekommen am 16. Dezember 2006.
• Paul E. Black, "wenig-o Notation", im Wörterbuch von Algorithmen und Datenstrukturen [online], Paul E. Black, Hrsg., amerikanisches Nationales Institut für Standards und Technologie. Am 17. Dezember 2004. Wiederbekommen am 16. Dezember 2006.
• Paul E. Black, "Ω", im Wörterbuch von Algorithmen und Datenstrukturen [online], Paul E. Black, Hrsg., amerikanisches Nationales Institut für Standards und Technologie. Am 17. Dezember 2004. Wiederbekommen am 16. Dezember 2006.
• Paul E. Black, "ω", im Wörterbuch von Algorithmen und Datenstrukturen [online], Paul E. Black, Hrsg., amerikanisches Nationales Institut für Standards und Technologie. Am 29. November 2004. Wiederbekommen am 16. Dezember 2006.
• Paul E. Black, "Θ", im Wörterbuch von Algorithmen und Datenstrukturen [online], Paul E. Black, Hrsg., amerikanisches Nationales Institut für Standards und Technologie. Am 17. Dezember 2004. Wiederbekommen am 16. Dezember 2006.

Links

• Einführung in asymptotische Notationen
• Landauer-Symbole