Big O notation

Groß O Notation ist eine mathematische Notation, die das beschreibt Verhalten einschränken von a Funktion wenn der Streit tendiert zu einem bestimmten Wert oder Unendlichkeit. Big O ist Mitglied von a Familie der Notationen erfunden von Paul Bachmann,^[1] Edmund Landau,^[2] und andere, gemeinsam genannt Bachmann -Landau Notation oder Asymptotische Notation. Der Brief O wurde von Bachmann ausgewählt, um für zu stehen Ordnung, bedeutet die Reihenfolge der Annäherung.

Im Informatik, Big o Notation ist gewohnt Klassifizieren Sie Algorithmen Wie ihre Laufzeit oder der Platzanforderungen mit zunehmender Eingangsgröße wachsen.^[3] Im analytische Zahlentheorie, Big o Notation wird oft verwendet, um eine Grenze für den Unterschied zwischen einem auszudrücken arithmetische Funktion und eine besser verstandene Annäherung; Ein berühmtes Beispiel für einen solchen Unterschied ist der Restbegriff in der Primzahl Theorem. In vielen anderen Bereichen wird auch eine große O -Notation verwendet, um ähnliche Schätzungen zu liefern.

Big O Notation charakterisiert Funktionen nach ihren Wachstumsraten: Unter Verwendung der gleichen O -Notation können unterschiedliche Funktionen mit derselben Wachstumsrate dargestellt werden. Der Buchstaben O wird verwendet, weil die Wachstumsrate einer Funktion auch als die bezeichnet wird Reihenfolge der Funktion. Eine Beschreibung einer Funktion in Bezug auf die große O -Notation liefert normalerweise nur eine obere Grenze über die Wachstumsrate der Funktion.

Mit großer O -Notation verbunden sind mehrere verwandte Notationen, die die Symbole unter Verwendung der Symbole verwenden o, Ω, ω, und Θ, um andere Arten von Grenzen der asymptotischen Wachstumsraten zu beschreiben.

Formale Definition

Lassen f, die zu geschätzte Funktion, sei a real oder Komplex geschätzte Funktion und lassen gDie Vergleichsfunktion ist eine real geschätzte Funktion. Lassen Sie beide Funktionen auf einigen definiert werden ungebunden Teilmenge des positiven reale Nummern, und ${\ displayStyle g (x)}$ Seien Sie streng positiv für alle groß genug Werte von x.^[4] Man schreibt

Wenn die absoluter Wert von ${\ displayStyle f (x)}$ ist höchstens ein positives konstantes Vielfaches von ${\ displayStyle g (x)}$ für alle ausreichend großen Werte von x. Das ist, ${\ displayStyle f (x) = o {\ bigl (} g (x) {\ bigr)}}$ Wenn es eine positive reelle Zahl gibt M und eine reelle Zahl x₀ so dass

In vielen Kontexten ist die Annahme, dass wir an der Wachstumsrate als Variable interessiert sind x Geht in Unendlichkeit bleibt nicht

Die Notation kann auch verwendet werden, um das Verhalten von zu beschreiben f in der Nähe einer realen Anzahl a (häufig, a = 0): wir sagen Wenn es positive Zahlen gibt ${\ displayStyle \ Delta}$ und M so dass für alle x mit ${\ displayStyle 0 <| x-a | <\ delta}$, Wie g(x) wird für Werte von als ungleich Null ausgewählt x ausreichend nah zu aBeide Definitionen können mit dem vereinheitlicht werden Begrenzen Sie überlegen: wenn

In der Informatik ist eine etwas restriktivere Definition üblich: ${\ displayStyle f}$ und ${\ displayStyle g}$ sind beide Funktionen aus der positive ganze Zahlen zu den nichtnegativen reellen Zahlen; ${\ displayStyle f (x) = o {\ bigl (} g (x) {\ bigr)}}$ Wenn es positive Ganzzahl -Zahlen gibt M und n₀ so dass ${\ displayStyle f (n) \ leq mg (n)}$ für alle ${\ displayStyle n \ geq n_ {0}}$.^[5] Bei Bedarf werden endliche Bereiche (stillschweigend) von ausgeschlossen ${\ displayStyle f}$und ${\ displayStyle g}$Domäne durch Auswahl n₀ ausreichend groß. (Zum Beispiel, ${\ displayStyle \ log (n)}$ ist undefiniert bei ${\ displayStyle n = 0}$.))

Beispiel

In typischer Verwendung die O Notation ist asymptotisch, das heißt, sie bezieht sich auf sehr große x. In dieser Umgebung wird der Beitrag der Begriffe, die "am schnellsten" wachsen, schließlich die anderen irrelevant machen. Infolgedessen können die folgenden Vereinfachungsregeln angewendet werden:

• Wenn f(x) ist eine Summe mehrerer Begriffe, wenn es eine mit größter Wachstumsrate gibt, kann sie gehalten und alle anderen weggelassen werden.
• Wenn f(x) ist ein Produkt mehrerer Faktoren, alle Konstanten (Begriffe im Produkt, von denen nicht abhängt x) kann ausgelassen werden.

Zum Beispiel lassen f(x) = 6x⁴ - 2x³ + 5und nehme an, wir möchten diese Funktion mithilfe verwenden O Notation, um seine Wachstumsrate als zu beschreiben x nähert sich unendlich. Diese Funktion ist die Summe von drei Begriffen: 6x⁴, –2x³, und 5. Von diesen drei Begriffen ist die mit der höchsten Wachstumsrate die mit dem größten Exponenten als Funktion von x, nämlich 6x⁴. Jetzt kann man die zweite Regel anwenden: 6x⁴ ist ein Produkt von 6 und x⁴ in dem der erste Faktor nicht abhängt x. Der Weglassen dieses Faktors führt zur vereinfachten Form x⁴. So sagen wir das f(x) ist ein "großes O" von x⁴. Mathematisch können wir schreiben f(x) = O(x⁴). Man kann diese Berechnung anhand der formalen Definition bestätigen: let f(x) = 6x⁴ - 2x³ + 5 und g(x) = x⁴. Anwenden des formale Definition von oben die Aussage, dass f(x) = O(x⁴) entspricht seiner Expansion,

für eine geeignete Wahl von x₀ und M und für alle x > x₀. Um dies zu beweisen, lassen Sie es x₀ = 1 und M = 13. Dann für alle x > x₀: Also

Verwendungszweck

Big O Notation hat zwei Hauptanwendungsbereiche:

• Im MathematikEs wird häufig verwendet, um zu beschreiben Wie genau eine endliche Serie einer bestimmten Funktion nähertbesonders bei einem verkürzten Fall Taylor -Serie oder Asymptotische Expansion
• Im Informatik, es ist nützlich in der Analyse von Algorithmen

In beiden Anwendungen die Funktion g(x) Erscheinen innerhalb der O(·) wird in der Regel so einfach wie möglich gewählt, ständige Faktoren weglassen und Begriffe niedrigerer Ordnung.

Es gibt zwei formal enge, aber merklich unterschiedliche Verwendungen dieser Notation:

• unendlich Asymptotik
• infinitesimal Asymptotik.

Diese Unterscheidung ist jedoch nur im Anwendung und nicht im Prinzip - die formale Definition für das "Big O" ist für beide Fälle gleich, nur mit unterschiedlichen Grenzen für das Funktionsargument.^{[Originalforschung?]}

Unendliche Asymptotik

Big o Notation ist nützlich, wenn Analyse von Algorithmen für Effizienz. Zum Beispiel die Zeit (oder die Anzahl der Schritte), die erforderlich sind, um ein Problem der Größe zu vervollständigen n könnte festgestellt werden T(n) = 4n² - 2n + 2. Wie n wächst groß, die n² Begriff wird dominieren, damit alle anderen Begriffe vernachlässigt werden können - zum Beispiel wann n = 500, der Begriff 4n² ist 1000 -mal so groß wie das 2n Begriff. Das Ignorieren des letzteren hätte für die meisten Zwecke einen vernachlässigbaren Einfluss auf den Wert des Ausdrucks. Ferner das Koeffizienten werden irrelevant, wenn wir uns mit einem anderen vergleichen bestellen des Ausdrucks, wie ein Ausdruck, der einen Term enthält n³ oder n⁴. Selbst wenn T(n) = 1.000.000n², wenn U(n) = n³Letzteres wird immer einmal den ersteren überschreiten n wächst größer als 1.000.000 (T(1.000.000) = 1.000.000³ = U(1.000.000)). Darüber hinaus hängt die Anzahl der Schritte von den Details des Maschinenmodells ab, auf dem der Algorithmus ausgeführt wird, aber verschiedene Arten von Maschinen variieren typischerweise nur einen konstanten Faktor in der Anzahl der für die Ausführung eines Algorithmus erforderlichen Schritte. Die große O -Notation erfasst also, was übrig bleibt: Wir schreiben auch

${\ displayStyle t (n) = o (n^{2})}$

oder

${\ displayStyle t (n) \ in o (n^{2})}$

Und sagen Sie, dass der Algorithmus hat Reihenfolge von n² Zeitkomplexität. Das Schild "="soll nicht ausdrücken" ist gleich "in seinem normalen mathematischen Sinne, sondern ein umgangssprachlicherer" ist ", daher wird der zweite Ausdruck manchmal als genauer angesehen (siehe das"Gleiches Zeichen"Diskussion unten), während der erste von einigen als als betrachtet wird Missbrauch der Notation.^[6]

Infinitesimale Asymptotik

Big O kann auch verwendet werden, um die zu beschreiben Fehlerbegriff in einer Annäherung an eine mathematische Funktion. Die bedeutendsten Begriffe werden explizit geschrieben, und dann werden die am wenigsten signifikanten Begriffe in einem einzigen Big O-Begriff zusammengefasst. Betrachten Sie zum Beispiel die Exponentialserie und zwei Ausdrücke davon, die gültig sind, wenn x ist klein:

$oder +{\ frac {x^{4}} {4!}}+\ dotsb & {\ text {für alle}} x \\ [4pt] & = 1+x+{\ frac {x^{2} { 2}}+o (x^{3}) & {\ text {as}} x \ bis 0 \\ [4pt] & = 1+x+o (x^{2}) & {\ text {as} } x \ bis 0 \ end {ausgerichtet}}}$

Der zweite Ausdruck (der mit O(x³)) bedeutet den absoluten Wert des Fehlers e^x - (1 + x + x²/2) ist höchstens konstante Zeiten |x³| Wenn x ist nah genug bis 0.

Eigenschaften

Wenn die Funktion f kann als endliche Summe anderer Funktionen geschrieben werden, dann bestimmt die am schnellsten wachsende Reihenfolge der Reihenfolge von f(n). Zum Beispiel,

$oder als}} n \ bis \ uninfty.}$

Insbesondere, wenn eine Funktion durch ein Polynom in der in den n, Dann als n neigt dazu Unendlichkeit, man kann ignorieren niedrigerer Ordnung Begriffe des Polynoms. Die Sätze O(n^c) und O(cⁿ) sind sehr verschieden. Wenn c ist größer als eins, dann wächst letzteres viel schneller. Eine Funktion, die schneller wächst als n^c für jeden c wird genannt Superpolynom. Eine, die langsamer wächst als jede exponentielle Funktion der Form cⁿ wird genannt unterexponentiell. Ein Algorithmus kann eine Zeit erfordern, die sowohl superpolynomisch als auch subtexponentiell ist. Beispiele hierfür sind die am schnellsten bekannten Algorithmen für Ganzzahlfaktorisierung und die Funktion n^{Protokoll n}.

Wir können alle Kräfte von ignorieren n Innerhalb der Logarithmen. Der Satz O(Protokoll n) ist genau das gleiche wie O(Protokoll(n^c)). Die Logarithmen unterscheiden sich nur um einen konstanten Faktor (seitdem Protokoll(n^c) = c Protokoll n) und so ignoriert die große O -Notation das. In ähnlicher Weise sind Protokolle mit unterschiedlichen konstanten Basen gleichwertig. Andererseits sind Exponentiale mit unterschiedlichen Basen nicht in der gleichen Reihenfolge. Zum Beispiel, 2ⁿ und 3ⁿ sind nicht der gleichen Reihenfolge.

Das Ändern von Einheiten kann die Reihenfolge des resultierenden Algorithmus beeinflussen oder nicht. Das Ändern von Einheiten entspricht der Multiplizierung der entsprechenden Variablen mit einer Konstante, wo immer sie erscheint. Zum Beispiel, wenn ein Algorithmus in der Reihenfolge von läuft n², ersetzen n durch CN bedeutet, dass der Algorithmus in der Reihenfolge von läuft c²n²und die große O -Notation ignoriert die Konstante c². Dies kann geschrieben werden als c²n² = O (n²). Wenn jedoch ein Algorithmus in der Reihenfolge von läuft 2ⁿ, ersetzen n mit CN gibt 2^CN = (2^c)ⁿ. Dies entspricht nicht zu 2ⁿ Im Algemeinen. Ändern von Variablen kann auch die Reihenfolge des resultierenden Algorithmus beeinflussen. Zum Beispiel, wenn die Laufzeit eines Algorithmus ist O(n) Wenn die Anzahl gemessen wird n von Ziffern einer Eingangszahl xdann ist seine Laufzeit O(Protokoll x) Bei der Messung der Eingangszahl gemessen x selbst, weil n = O(Protokoll x).

Produkt

$oder } g_ {2})}$

${\ displayStyle f \ cdot o (g) = o (fg)}$

Summe

Wenn ${\ displayStyle f_ {1} = o (g_ {1})}$ und ${\ displayStyle f_ {2} = o (g_ {2})}$ dann ${\ displayStyle f_ {1}+f_ {2} = o (\ max (g_ {1}, g_ {2})}$. Daraus folgt, wenn wenn ${\ displayStyle f_ {1} = o (g)}$ und ${\ displayStyle f_ {2} = o (g)}$ dann ${\ displayStyle f_ {1}+f_ {2} \ in o (g)}$. Mit anderen Worten, diese zweite Aussage sagt das ${\ displayStyle o (g)}$ ist ein konvexer Kegel.

Multiplikation durch eine Konstante

Lassen k Sei eine Konstante ungleich Null. Dann ${\ displayStyle o (| k | \ cdot g) = o (g)}$. Mit anderen Worten, wenn ${\ displayStyle f = o (g)}$, dann ${\ displayStyle k \ cdot f = o (g).}$

Mehrere Variablen

Groß O (und Little O, ω usw.) können auch mit mehreren Variablen verwendet werden. Big definieren O formally for multiple variables, suppose ${\ displayStyle f}$ und ${\ displayStyle g}$ are two functions defined on some subset of ${\ displaystyle \ mathbb {r} ^{n}}$. Wir sagen

${\displaystyle f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty }$

if and only if there exist constants ${\ displayStyle m}$ und ${\displaystyle C>0}$ so dass ${\displaystyle |f(\mathbf {x} )|\leq C|g(\mathbf {x} )|}$ für alle ${\ displaystyle \ mathbf {x}}$ mit ${\displaystyle x_{i}\geq M}$ für einige ${\ displayStyle i.}$^[7] Equivalently, the condition that ${\displaystyle x_{i}\geq M}$ für einige ${\ displayStyle i}$ kann geschrieben werden ${\displaystyle \|\mathbf {x} \|_{\infty }\geq M}$, wo ${\displaystyle \|\mathbf {x} \|_{\infty }}$ bezeichnet die Chebyshev norm. For example, the statement

${\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty }$

asserts that there exist constants C und M so dass

${\displaystyle |f(n,m)-(n^{2}+m^{3})|\leq C|n+m|}$

whenever either ${\displaystyle m\geq M}$ oder ${\displaystyle n\geq M}$ hält. This definition allows all of the coordinates of ${\ displaystyle \ mathbf {x}}$ to increase to infinity. In particular, the statement

${\displaystyle f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty }$

(d. h., ${\displaystyle \exists C\,\exists M\,\forall n\,\forall m\,\cdots }$) is quite different from

${\displaystyle \forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty }$

(d. h., ${\displaystyle \forall m\,\exists C\,\exists M\,\forall n\,\cdots }$).

Under this definition, the subset on which a function is defined is significant when generalizing statements from the univariate setting to the multivariate setting. Zum Beispiel wenn ${\displaystyle f(n,m)=1}$ und ${\displaystyle g(n,m)=n}$, dann ${\displaystyle f(n,m)=O(g(n,m))}$ if we restrict ${\ displayStyle f}$ und ${\ displayStyle g}$ zu ${\displaystyle [1,\infty )^{2}}$, but not if they are defined on ${\displaystyle [0,\infty )^{2}}$.

This is not the only generalization of big O to multivariate functions, and in practice, there is some inconsistency in the choice of definition.^[8]

Notationfragen

Gleiches Zeichen

Die Aussage "f(x) ist O(g(x))" as defined above is usually written as f(x) = O(g(x)). Some consider this to be an Missbrauch der Notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. Wie de bruijn sagt, O(x) = O(x²) ist wahr aber O(x²) = O(x) ist nicht.^[9] Knuth describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like n = n² from the identities n = O(n²) und n² = O(n²). "^[10] In another letter, Knuth also pointed out that "the equality sign is not symmetric with respect to such notations", as, in this notation, "mathematicians customarily use the = sign as they use the word "is" in English: Aristotle is a man, but a man isn't necessarily Aristotle".^[11]

For these reasons, it would be more precise to use Notation setzen und schreibe f(x) ∈ O(g(x)) (read as: "f(x) ist ein Element von O(g(x))", oder "f(x) is in the set O(g(x))"), in Gedanken an O(g(x)) as the class of all functions h(x) such that |h(x) | ≤C|g(x) | for some constant C.^[10] However, the use of the equals sign is customary.^[9][10]

Andere arithmetische Operatoren

Big O notation can also be used in conjunction with other arithmetic operators in more complicated equations. Zum Beispiel, h(x) + O(f(x)) denotes the collection of functions having the growth of h(x) plus a part whose growth is limited to that of f(x). Daher,

${\displaystyle g(x)=h(x)+O(f(x))}$

expresses the same as

${\displaystyle g(x)-h(x)=O(f(x)).}$

Beispiel

Suppose an Algorithmus is being developed to operate on a set of n Elemente. Its developers are interested in finding a function T(n) that will express how long the algorithm will take to run (in some arbitrary measurement of time) in terms of the number of elements in the input set. The algorithm works by first calling a subroutine to sort the elements in the set and then perform its own operations. The sort has a known time complexity of O(n²), and after the subroutine runs the algorithm must take an additional 55n³ + 2n + 10 steps before it terminates. Thus the overall time complexity of the algorithm can be expressed as T(n) = 55n³ + O(n²). Here the terms 2n + 10 are subsumed within the faster-growing O(n²). Again, this usage disregards some of the formal meaning of the "=" symbol, but it does allow one to use the big O notation as a kind of convenient placeholder.

Mehrere Verwendungen

In more complicated usage, O(·) can appear in different places in an equation, even several times on each side. For example, the following are true for ${\ displayStyle n \ to \ inty}$:

The meaning of such statements is as follows: for irgendein functions which satisfy each O(·) on the left side, there are etwas functions satisfying each O(·) on the right side, such that substituting all these functions into the equation makes the two sides equal. For example, the third equation above means: "For any function f(n) = O(1), there is some function g(n) = O(eⁿ) so dass n^f(n) = g(n)." In terms of the "set notation" above, the meaning is that the class of functions represented by the left side is a subset of the class of functions represented by the right side. In this use the "=" is a formal symbol that unlike the usual use of "=" is not a Symmetrische Beziehung. Thus for example n^O(1) = O(eⁿ) does not imply the false statement O(eⁿ) = n^O(1).

Artensett

Big O is typeset as an italicized uppercase "O", as in the following example: ${\ displayStyle o (n^{2})}$.^[12][13] Im Tex, it is produced by simply typing O inside math mode. Unlike Greek-named Bachmann–Landau notations, it needs no special symbol. Yet, some authors use the calligraphic variant ${\ displaystyle {\ mathcal {o}}}$ stattdessen.^[14][15]

Bestellungen gemeinsamer Funktionen

Hier finden Sie eine Liste von Funktionen, die bei der Analyse der Laufzeit eines Algorithmus häufig auftreten. In jedem Fall, c is a positive constant and n zunimmt ohne gebunden. Die langsamer wachsenden Funktionen sind im Allgemeinen zuerst aufgeführt.

Notation	Name	Beispiel
${\ displayStyle o (1)}$	Konstante	Feststellen, ob eine Binärzahl gerade oder ungerade ist; Berechnung ${\displaystyle (-1)^{n}}$; Verwenden einer konstanten Größe Nachschlagwerk
${\ displayStyle o (\ log \ log n)}$	Doppelte logarithmisch	Durchschnittliche Anzahl von Vergleiche, die ein Element verwendet haben, das verwendet wurde Interpolationssuche in einer sortierten Reihe von gleichmäßig verteilten Werten
${\ displayStyle o (\ log n)}$	logarithmisch	Finden eines Elements in einem sortierten Array mit a binäre Suche oder eine ausgewogene Suche Baum sowie alle Operationen in a binomial heap
${\ displayStyle o ((\ log n)^{c})}$ ${\ textstyle c> 1}$	Polylogarithmic	Die Matrixkettenordnung kann in polylogarithmischer Zeit auf a gelöst werden Parallele Zufallszugriffsmaschine.
${\ displayStyle o (n^{c})}$ ${\ textStyle 0 <c <1}$	Bruchkraft	Suche in a K-D-Baum
${\ displayStyle o (n)}$	linear	Finden eines Elements in einer unsortierten Liste oder in einem unsortierten Array; zwei hinzufügen n-bit Ganzzahlen von Ripple Carry
${\ displayStyle o (n \ log ^{*} n)}$	n Protokollstar n	Leistung Triangulation eines einfachen Polygons verwenden Seidels Algorithmus, oder der Union -Find -Algorithmus. Beachten Sie, dass ${\ displayStyle \ log ^{*} (n) = {\ begin {cases} 0, & {\ text {if}} n \ leq 1 \\ 1+ \ log ^{*} (\ log n), & & & & & & & & {\ text {if}} n> 1 \ end {cases}}}$
${\ displayStyle o (n \ log n) = o (\ log n!)}$	linearithmisch, loglinear, quasilear oder "n Protokoll n"	Ausführen a Schnelle Fourier-Transformation; am schnellsten möglich Vergleichsart; Haufen und Zusammenführen, sortieren
${\ displayStyle o (n^{2})}$	quadratisch	Zwei multiplizieren n-Digit -Zahlen von Schulbuchmultiplikation; einfache Sortieralgorithmen wie z. Blasenart, Auswahlsorten und Sortieren durch Einfügen; (schlimmste Fall) gebunden an einigen normalerweise schnelleren Sortieralgorithmen wie z. schnelle Sorte, Shellsort, und Baumart
${\ displayStyle o (n^{c})}$	Polynom oder algebraisch	Baum-Adjoining-Grammatik Parsing; maximal Matching zum Bipartitale Grafiken; Finden der bestimmend mit LU -Zersetzung
$oder }$ ${\ textstyle 0 <\ alpha <1}$	L-Notation oder Subexponential	Faktoring einer Nummer mit der quadratisches Sieb oder Zahlenfeld Sieb
${\ displayStyle o (c^{n})}$ ${\ textstyle c> 1}$	exponentiell	Finden der (exakten) Lösung für die Problem mit reisenden Verkäufern Verwendung Dynamische Programmierung; Bestimmen Sie, ob zwei logische Anweisungen gleichwertig sind Brute-Force-Suche
${\ displayStyle o (n!)}$	Fakultät	Lösen des Problem mit reisenden Verkäufern Über Brute-Force-Suche; Erzeugen aller uneingeschränkten Permutationen von a Poset; Finden der bestimmend mit Laplace -Expansion; Aufzählung Alle Partitionen eines Satzes

Die Aussage ${\ displayStyle f (n) = o (n!)}$ wird manchmal geschwächt zu ${\ displayStyle f (n) = o \ links (n^{n} \ rechts)}$ einfachere Formeln für die asymptotische Komplexität abzuleiten. Für jeden ${\ displayStyle k> 0}$ und ${\ displayStyle c> 0}$, ${\ displayStyle o (n^{c} (\ log n)^{k})}$ ist eine Teilmenge von ${\ displayStyle o (n^{c+\ varepsilon})}$ für jeden ${\ displayStyle \ varepsilon> 0}$, Es kann also als Polynom mit einer größeren Ordnung angesehen werden.

Verwandte asymptotische Notationen

Groß O wird in der Informatik weit verbreitet. Zusammen mit einigen anderen verwandten Notationen bildet es die Familie von Bachmann -Landau -Notationen.

Little-o Notation

Intuitiv die Behauptung "f(x) ist o(g(x))" (lesen "f(x) ist wenig g(x)") bedeutet, dass g(x) wächst viel schneller als f(x). Lass wie zuvor f eine echte oder komplexe Funktion sein und g Eine real geschätzte Funktion, beide auf einer unbegrenzten Untergruppe des Positiven definiert reale Nummern, so dass g(x) ist streng positiv für alle groß genug Werte von x. Man schreibt

$oder$

Wenn für jede positive Konstante ε Es gibt eine Konstante ${\ displayStyle x_ {0}}$ so dass

$oder$^[16]

Zum Beispiel hat man

${\ displayStyle 2x = o (x^{2})}$ und ${\ displayStyle 1/x = o (1),},}$ beide als ${\ displayStyle x \ to \ inty.}$

Der Unterschied zwischen der Definition der Big-o Notation und die Definition von Little-O ist, dass der erstere zwar für wahr sein muss für mindestens ein Konstante M, Letzteres muss halten für jeder Positive Konstante ε, wie klein.^[17] Auf diese Weise macht Little-o Notation a stärkere Aussage als die entsprechende Big-O-Notation: jede Funktion, die wenig ist von O von g ist auch groß-o von g, aber nicht jede Funktion, die groß ist von O von g ist auch wenig von O von g. Zum Beispiel, ${\ displayStyle 2x^{2} = o (x^{2})}$ aber ${\ displayStyle 2x^{2} \ neq o (x^{2})}$.

Wie g(x) ist ungleich Null oder wird zumindest außerhalb eines bestimmten Punktes ungleich Null, die Beziehung ${\ displayStyle f (x) = o (g (x))}$ ist äquivalent zu

$oder$ (Und das ist in der Tat wie Landau^[16] ursprünglich die Little-O-Notation definiert).

Little-o respektiert eine Reihe von arithmetischen Operationen. Zum Beispiel,

wenn c ist eine Konstante ungleich Null und ${\ displayStyle f = o (g)}$ dann ${\ displayStyle c \ cdot f = o (g)}$, und

wenn ${\ displayStyle f = o (f)}$ und ${\ displayStyle g = o (g)}$ dann ${\ displayStyle f \ cdot g = o (f \ cdot g).}$

Es erfüllt auch a Transitivität Beziehung:

wenn ${\ displayStyle f = o (g)}$ und ${\ displayStyle g = o (h)}$ dann ${\ displayStyle f = o (h).}$

Big Omega Notation

Eine andere asymptotische Notation ist ${\ displayStyle \ Omega}$, Lesen Sie "Big Omega".^[18] Es gibt zwei weit verbreitete und inkompatible Definitionen der Aussage

${\ displayStyle f (x) = \ Omega (g (x))}$ wie ${\ displayStyle x \ bis a}$,

wo a ist eine reelle Zahl, ∞ oder −∞, wo f und g sind reale Funktionen in einer Nachbarschaft von definiert a, und wo g ist in dieser Nachbarschaft positiv.

Die Hardy -Littlewood -Definition wird hauptsächlich in verwendet analytische Zahlentheorieund die Knuth -Definition hauptsächlich in Computerkomplexitätstheorie; Die Definitionen sind nicht gleichwertig.

Die Hardy -Littlewood -Definition

1914 Godfrey Harold Hardy und John Edensor Littlewood stellte das neue Symbol vor ${\ displayStyle \ Omega}$,^[19] was wie folgt definiert wird:

${\ displayStyle f (x) = \ Omega (g (x))}$ wie ${\ displayStyle x \ bis \ inty}$ wenn $oder$

Daher ${\ displayStyle f (x) = \ Omega (g (x))}$ ist die Negation von ${\ displayStyle f (x) = o (g (x))}$.

1916 stellten die gleichen Autoren die beiden neuen Symbole ein ${\ displayStyle \ Omega _ {r}}$ und ${\ displayStyle \ Omega _ {l}}$, definiert als:^[20]

${\ displayStyle f (x) = \ Omega _ {r} (g (x))}$ wie ${\ displayStyle x \ bis \ inty}$ wenn $oder$;

${\ displayStyle f (x) = \ Omega _ {l} (g (x))}$ wie ${\ displayStyle x \ bis \ inty}$ wenn $oder$

Diese Symbole wurden von verwendet von Edmund Landaumit den gleichen Bedeutungen im Jahr 1924.^[21] Nach Landau wurden die Notationen nie genau so verwendet; ${\ displayStyle \ Omega _ {r}}$ wurde ${\ displayStyle \ Omega _ {+}}$ und ${\ displayStyle \ Omega _ {l}}$ wurde ${\ displayStyle \ Omega _ {-}}$.

Diese drei Symbole ${\ displayStyle \ Omega, \ Omega _ {+}, \ Omega _ {-}}$, ebenso gut wie ${\ displayStyle f (x) = \ Omega _ {\ pm} (g (x))}$ (bedeutet, dass ${\ displayStyle f (x) = \ Omega _ {+} (g (x))}$ und ${\ displayStyle f (x) = \ Omega _ {-} (g (x))}$ sind beide zufrieden), werden jetzt derzeit in verwendet analytische Zahlentheorie.^[22][23]

Einfache Beispiele

Wir haben

${\ displayStyle \ sin x = \ Omega (1)}$ wie ${\ displayStyle x \ to \ inty,}$

und genauer gesagt

${\ displayStyle \ sin x = \ Omega _ {\ pm} (1)}$ wie ${\ displayStyle x \ to \ inty.}$

Wir haben

${\ displayStyle \ sin x+1 = \ Omega (1)}$ wie ${\ displayStyle x \ to \ inty,}$

und genauer gesagt

${\ displayStyle \ sin x+1 = \ Omega _ {+} (1)}$ wie ${\ displayStyle x \ to \ inty;}$

jedoch

${\ displayStyle \ sin x+1 \ nicht = \ Omega _ {-} (1)}$ wie ${\ displayStyle x \ to \ inty.}$

Die Knuth -Definition

1976 Donald Knuth veröffentlichte ein Papier, um seine Verwendung der zu rechtfertigen ${\ displayStyle \ Omega}$-Symbol, um eine stärkere Eigenschaft zu beschreiben.^[24] Knuth schrieb: "Für alle Anwendungen, die ich bisher in der Informatik gesehen habe, ist eine stärkere Anforderung ... viel geeigneter." Er definierte

${\ displayStyle f (x) = \ Omega (g (x)) \ leftrightarrow g (x) = o (f (x))}$

mit dem Kommentar: "Obwohl ich die Definition von Hardy und Littlewood von verändert habe ${\ displayStyle \ Omega}$Ich fühle mich berechtigt, dies zu tun, weil ihre Definition keineswegs in großem Umfang verwendet wird und weil es andere Möglichkeiten gibt, zu sagen, was sie in den vergleichsweise seltenen Fällen sagen möchten, wenn ihre Definition gilt. "^[24]

Familie von Bachmann -Landau Notationen

Notation	Name[24]	Beschreibung	Formale Definition	Begrenzung der Definition[25][26][27][24][19]
${\ displayStyle f (n) = o (g (n))}$	Klein O; Kleine Oh	f wird dominiert von g asymptotisch	$oder$	$oder$
${\ displayStyle f (n) = o (g (n))}$	Big O; Big OH; Big Omicron	${\ displayStyle | f |}$ wird oben von oben begrenzt g (bis zu konstantem Faktor) asymptotisch	$oder$	$oder$
${\ displayStyle f (n) = \ theta (g (n))}}$	Big Theta	f wird sowohl oben als auch unten durch begrenzt g asymptotisch	$oder$ ${\ displayStyle k_ {1} \ cdot g (n) \ leq | f (n) | \ leq k_ {2} \ cdot g (n)}$	${\ displayStyle f (n) = o (g (n))}$ und ${\ displayStyle f (n) = \ Omega (g (n))}}$ (Knuth -Version)
${\ displayStyle f (n) \ sim g (n)}$	Im Auftrag von	f ist gleich g asymptotisch	$oder \ rechts | <\ varepsilon}$	$oder$
${\ displayStyle f (n) = \ Omega (g (n))}}$	Big Omega in der Komplexitätstheorie (Knuth)	f ist unten nach unten begrenzt g asymptotisch	$oder$	$oder$
${\ displayStyle f (n) = \ Omega (g (n))}}$	Kleine Omega	f dominiert g asymptotisch	$oder$	$oder$
${\ displayStyle f (n) = \ Omega (g (n))}}$	Big Omega in der Zahlentheorie (Hardy -Littlewood)	${\ displayStyle | f |}$ wird nicht dominiert von g asymptotisch	$oder$	$oder$

Die Grenzdefinitionen gehen davon aus ${\ displayStyle g (n)> 0}$ für ausreichend groß ${\ displayStyle n}$. Die Tabelle ist (teilweise) in dem Sinne vom kleinsten zum größten sortiert, in dem Sinne, dass ${\ displayStyle o, o, \ theta, \ sim,}$ (Knuths Version von) ${\ displayStyle \ Omega, \ Omega}$ auf Funktionen entsprechen ${\ displayStyle <, \ leq, \ ca., =,}$${\ displayStyle \ Geq,>}$ auf der realen Linie^[27] (die Hardy-Littlewood-Version von ${\ displayStyle \ Omega}$entspricht jedoch nicht einer solchen Beschreibung).

Informatik nutzt die großen ${\ displayStyle o}$, Big Theta ${\ displayStyle \ theta}$, wenig ${\ displayStyle o}$, kleiner Omega ${\ displayStyle \ Omega}$ Und Knuths großer Omega ${\ displayStyle \ Omega}$ Notationen.^[28] Die analytische Zahlentheorie verwendet oft die großen ${\ displayStyle o}$, klein ${\ displayStyle o}$, Hardy -Littlewoods Big Omega ${\ displayStyle \ Omega}$ (mit oder ohne die +, - oder ± Abschluss) und ${\ displayStyle \ Sim}$ Notationen.^[22] Der kleine Omega ${\ displayStyle \ Omega}$ Notation wird nicht so oft in der Analyse verwendet.^[29]

Verwendung in Informatik

Informell, insbesondere in der Informatik, die große O Notation kann oft etwas anders verwendet werden, um einen Asymptotikum zu beschreiben fest gebunden, wo die Verwendung von großer Theta θ in einem bestimmten Kontext sachlicher angemessener sein könnte. Zum Beispiel bei der Betrachtung einer Funktion T(n) = 73n³ + 22n² + 58, alle folgenden folgenden sind allgemein akzeptabel, aber engere Grenzen (z. B. die Zahlen 2 und 3 unten) werden normalerweise gegenüber lockereren Grenzen (z. B. Nummer 1 unten) stark bevorzugt.

1. T(n) = O(n¹⁰⁰)
2. T(n) = O(n³)
3. T(n) = Θ (n³)

Die äquivalenten englischen Aussagen sind jeweils:

1. T(n) wächst asymptotisch nicht schneller als n¹⁰⁰
2. T(n) wächst asymptotisch nicht schneller als n³
3. T(n) wächst asymptotisch so schnell wie n³.

Während alle drei Aussagen wahr sind, sind progressiv mehr Informationen in jeweils enthalten. In einigen Bereichen würde jedoch die große O -Notation (Nummer 2 in den oben genannten Listen) häufiger verwendet als die große Theta -Notation (Elemente, die 3 in den oben genannten Listen nummerieren). Zum Beispiel wenn T(n) repräsentiert die Laufzeit eines neu entwickelten Algorithmus für die Eingangsgröße nDie Erfinder und Benutzer des Algorithmus sind möglicherweise eher geneigt, eine obere asymptotische Verbindung zu setzen, wie lange es dauern wird, um zu laufen, ohne eine explizite Aussage über die untere asymptotische Grenze zu machen.

Andere Notation

In ihrem Buch Einführung in Algorithmen, Cormen, Leiserson, Rivest und Stein Betrachten Sie die Funktionen der Funktionen f was befriedigt

${\ displayStyle f (n) = o (g (n)) \ quad (n \ to \ inty) ~.}$

In einer korrekten Notation kann dieser Satz zum Beispiel aufgerufen werden O(g), wo

$oder f (n) \ leq cg (n) {\ text {für alle}} n \ geq n_ {0} \}.}$^[30]

Die Autoren geben an, dass die Verwendung des Gleichstellungsbetreibers (=) zur Bezeichnung der festgelegten Mitgliedschaft anstelle des festgelegten Mitgliedsbetreibers (∈) ein Notationsmissbrauch ist, dies hat jedoch Vorteile.^[6] In einer Gleichung oder Ungleichheit steht die Verwendung von asymptotischer Notation für eine anonyme Funktion im Satz O(g), was Begriffe niedrigerer Ordnung beseitigt und hilft, beispielsweise in Essentialstörungen in Gleichungen zu reduzieren:^[31]

${\ displayStyle 2n^{2}+3n+1 = 2n^{2}+o (n).}$

Erweiterungen zu den Bachmann -Landau -Notationen

Eine andere Notation, die manchmal in der Informatik verwendet wird, ist õ (lesen Soft-o): f(n) =Õ(g(n)) ist eine Abkürzung für f(n) = O(g(n) Protokoll^k n) für einige k.^[32] Einige Autoren schreiben o^* Für den gleichen Zweck.^[33] Im Wesentlichen ist es eine große Notation, die logarithmische Faktoren ignoriert, da die Wachstumseffekte einer anderen Super-Logarithmischen Funktion auf eine Explosion der Wachstumspreis für große Eingangsparameter hinweisen, die für die Vorhersage einer schlechten Laufzeitleistung wichtiger sind als die feineren -Point-Effekte, die durch den logarithmischen Wachstumsfaktor (en) beigetragen werden. Diese Notation wird häufig verwendet, um das "Nitpicking" innerhalb von Wachstumsraten zu vermeiden, die als zu eng für die vorliegenden Angelegenheiten (seit Log^k n ist immer o(n^ε) für jede Konstante k und alle ε > 0).

Auch die L Notation, definiert als

$oder }$

ist praktisch für Funktionen, die zwischeneinander liegen Polynom und exponentiell bezüglich ${\ displayStyle \ ln n}$.

Verallgemeinerungen und verwandte Verwendungen

Die Verallgemeinerung auf Funktionen, die Werte in jedem nehmen Normed Vektorraum ist unkompliziert (ersetzen absolute Werte durch Normen), wo f und g Müssen Sie ihre Werte nicht im selben Raum nehmen. Eine Verallgemeinerung auf Funktionen g Werte in jedem nehmen Topologische Gruppe ist auch möglich. Der "Begrenzungsprozess" x→x_o kann auch durch Einführung eines willkürlichen Einführung verallgemeinert werden Filterbasis, d.h. Netze f undg. Das o Notation kann verwendet werden, um zu definieren Derivate und Differenzierbarkeit in ganz allgemeinen Räumen und auch (asymptotische) Äquivalenz von Funktionen,

${\ displayStyle f \ sim g \ iff (f-g) \ in o (g)}$

Welches ist ein Äquivalenzbeziehung und eine restriktivere Vorstellung als die Beziehung "f ist θ (g) "von oben. (Es reduziert sich auf Lim f / g = 1 if f und g sind positive real geschätzte Funktionen.) Zum Beispiel 2x ist θ (x), aber 2x − x ist nicht o(x).

Geschichte (Bachmann -Landau-, Hardy- und Vinogradov -Notationen)

Das Symbol O wurde zuerst vom Zahlen -Theoretiker eingeführt Paul Bachmann 1894 im zweiten Band seines Buches Analytische Zahlentheorie (""analytische Zahlentheorie").^[1] Der Zahlen -Theoretiker Edmund Landau adoptierte es und wurde daher inspiriert, 1909 die Notation O vorzustellen;^[2] Daher werden beide jetzt Landau -Symbole genannt. Diese Notationen wurden in den 1950er Jahren für die asymptotische Analyse in der angewandten Mathematik verwendet.^[34]Das Symbol ${\ displayStyle \ Omega}$ (im Sinne "ist keine o von ") wurde 1914 von Hardy und Littlewood eingeführt.^[19] Hardy und Littlewood stellten auch 1916 die Symbole vor ${\ displayStyle \ Omega _ {r}}$ ("richtig und ${\ displayStyle \ Omega _ {l}}$ ("links"),^[20] Vorläufer der modernen Symbole ${\ displayStyle \ Omega _ {+}}$ ("ist nicht kleiner als ein kleines o von") und ${\ displayStyle \ Omega _ {-}}$ ("ist nicht größer als ein kleines o von"). Somit werden die Omega -Symbole (mit ihren ursprünglichen Bedeutungen) manchmal auch als "Landau -Symbole" bezeichnet. Diese Notation ${\ displayStyle \ Omega}$ wurde mindestens seit den 1950er Jahren häufig in der Zahlentheorie verwendet.^[35] In den 1970er Jahren wurde das Big O in Informatik in der Informatik populär gemacht Donald Knuth, der die verwandte Theta -Notation einführte und eine andere Definition für die Omega -Notation vorschlug.^[24]

Landau benutzte nie die großen Theta- und kleinen Omega -Symbole.

Hardys Symbole waren (in Bezug auf die Moderne O Notation)

${\ displayStyle f \ preccurlyeq g \ iff f \ in o (g)}$ und ${\ displayStyle f \ prec g \ iff f \ in o (g);}$

(Hardy jedoch nie definiert oder verwendet die Notation ${\ displaystyle \ prec \! \! \ prec}$, noch ${\ displayStyle \ ll}$, wie es manchmal berichtet wurde). Hardy stellte die Symbole vor ${\ displayStyle \ präccurlyeq}$ und ${\ displayStyle \ prec}$ (sowie einige andere Symbole) in seinem 1910er -Gebiet "Infinity Orders" und nutzte sie nur in drei Papieren (1910–1913). In seinen fast 400 verbleibenden Papieren und Büchern benutzte er die Landau -Symbole o und o konsequent.

Hardys Notation wird nicht mehr verwendet. Andererseits in den 1930er Jahren,^[36] der russische Zahlen -Theoretiker Ivan Matveyevich Vinogradov stellte seine Notation vor${\ displayStyle \ ll}$, was zunehmend in der Zahlentheorie anstelle der verwendet wurde ${\ displayStyle o}$ Notation. Wir haben

${\ displayStyle f \ ll g \ iff f \ in o (g),}$

und häufig werden beide Notationen im selben Papier verwendet.

Das Big-O steht ursprünglich für "Order of" ("Ordnung", Bachmann 1894) und ist somit ein lateinischer Brief. Weder Bachmann noch Landau nennen es jemals "Omicron". Das Symbol war viel später (1976), der von Knuth als Kapital angesehen wurde Omicron,^[24] Wahrscheinlich in Bezug auf seine Definition des Symbols Omega. Die Ziffer Null sollte nicht benutzt werden.

Siehe auch

• Asymptotische Expansion: Näherung der Funktionen, die die Formel von Taylor verallgemeinert
• Asymptotisch optimaler Algorithmus: Eine Ausdruck
• Big O in Wahrscheinlichkeitsnotation: O_p, o_p
• Begrenzen Sie überlegen und begrenzen minderwertig: Eine Erläuterung einiger der in diesem Artikel verwendeten Grenznotation
• Master -Theorem (Analyse von Algorithmen): Zur Analyse von rekursiven Algorithmen mit großer O-Notation
• Nachbin's Theorem: Eine genaue Methode der Begrenzung Komplexe Analyse Funktionen so, dass die Konvergenzdomäne von Integrale Transformationen kann angegeben werden
• Annäherungsaufträge
• Computerkomplexität der mathematischen Operationen

Referenzen und Notizen

Weitere Lektüre

• Hardy, G. H. (1910). Unendlichkeitsbefehle: 'Infinitärcalcül' von Paul du Bois-Reymond. Cambridge University Press.
• Knuth, Donald (1997). "1.2.11: Asymptotische Darstellungen". Grundalgorithmen. Die Kunst der Computerprogrammierung. Vol. 1 (3. Aufl.). Addison-Wesley. ISBN 978-0-201-89683-1.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "3.1: Asymptotische Notation". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. ISBN 978-0-262-03293-3.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. pp.226–228. ISBN 978-0-534-94728-6.
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalisierung der Notation in Isabelle/Hol (PDF). Internationale gemeinsame Konferenz über automatisiertes Denken. doi:10.1007/978-3-540-25984-8_27.
• Black, Paul E. (11. März 2005). Black, Paul E. (Hrsg.). "Big-o Notation". Wörterbuch von Algorithmen und Datenstrukturen.US Nationales Institut für Standards und Technologie. Abgerufen 16. Dezember, 2006.
• Black, Paul E. (17. Dezember 2004).Black, Paul E. (Hrsg.). "Little-o Notation". Wörterbuch von Algorithmen und Datenstrukturen.US Nationales Institut für Standards und Technologie. Abgerufen 16. Dezember, 2006.
• Black, Paul E. (17. Dezember 2004).Black, Paul E. (Hrsg.). "Ω". Wörterbuch von Algorithmen und Datenstrukturen.US Nationales Institut für Standards und Technologie. Abgerufen 16. Dezember, 2006.
• Black, Paul E. (17. Dezember 2004).Black, Paul E. (Hrsg.). "ω". Wörterbuch von Algorithmen und Datenstrukturen.US Nationales Institut für Standards und Technologie. Abgerufen 16. Dezember, 2006.
• Black, Paul E. (17. Dezember 2004).Black, Paul E. (Hrsg.). "Θ". Wörterbuch von Algorithmen und Datenstrukturen.US Nationales Institut für Standards und Technologie. Abgerufen 16. Dezember, 2006.

Externe Links

• Wachstum der Sequenzen - OEIS (Online -Enzyklopädie von Ganzzahlsequenzen) Wiki
• Einführung in asymptotische Notationen^{[Permanent Dead Link]}
• Landau -Symbole
• Big-o Notation-wofür ist es gut
• Big O Notation im einfachen Englisch erklärt
• Ein Beispiel für eine große O -Genauigkeit des zentral geteilten Differenzschemas für das erste Derivat Archiviert 2018-10-07 bei der Wayback -Maschine
• Eine sanfte Einführung in die Algorithmuskomplexitätsanalyse