In der Mathematik , genauer gesagt in der Analyse , ist der asymptotische Vergleich eine Methode, die darin besteht, die Wachstumsrate einer Funktion in der Nähe eines Punktes oder im Unendlichen zu untersuchen, indem sie mit der einer anderen Funktion verglichen wird, die als "einfacher" angesehen wird. Dies wird häufig auf einer Referenzskala gewählt , die im Allgemeinen zumindest bestimmte sogenannte Elementarfunktionen enthält , insbesondere die Summen und Produkte von Polynomen , Exponentialen und Logarithmen . Die entsprechenden Notationen werden insbesondere in der Physik und in der Informatik verwendet , um beispielsweise die Komplexität bestimmter Algorithmen zu beschreiben . Sie werden auch in der analytischen Zahlentheorie verwendet , um den Fehler, der durch Ersetzen einer unregelmäßigen Funktion wie der Zählung von Primzahlen durch eine Funktion der gewählten Skala gemacht wird, fein zu bewerten .
Die Methode wurde durch die Arbeit von Paul du Bois-Reymond von 1872 eingeführt; Um die Berechnung und Darstellung der Ergebnisse zu erleichtern, wurden verschiedene Notationen entwickelt, insbesondere von Bachmann (1894), Landau (1909), Hardy (1910), Hardy und Littlewood (1914 und 1916) und Vinogradov ( ca. 1930).
Sei f und g die durch die Formeln definierten reellen Funktionen
Durch eine Untersuchung der beiden Funktionen wissen wir, dass g Werte annimmt, die so groß sind, wie wir wollen, in der Nachbarschaft der Unendlichkeit, während f nur Werte zwischen 1 und 3 annehmen kann. Der Quotient g geteilt durch f au Nachbarschaft der Unendlichkeit nimmt weiter zu und ist nicht begrenzt. In diesem Zusammenhang können wir sagen , dass f ist in vernachlässigbaren vor g , oder dass g ist überwiegend in vor f , in der Nachbarschaft der Unendlichkeit, wir schreiben (Landau - Notation):
oder (Hardys Notation, veraltet)
Die Hardy-Notation ermöglicht es, die Vorherrschaftsverhältnisse zu verketten, zum Beispiel:
Formale Definition, wenn die Funktion g nicht verschwindetUm diese Eigenschaft formal zu definieren, betrachten wir das Verhalten des Quotienten .
Ist
Sei f und g zwei Funktionen der reellen Variablen x . Wir nehmen an, dass g nicht über einer Nachbarschaft von a verschwindet . Wir sagen , dass f vor vernachlässigbar ist g , oder dass g ist überwiegend in vor f in a , und wir beachten , wenn
Wenn der Kontext klar ist, gibt man den Studienbereich nicht an und man merkt: gerade . Die Notation ist jedoch immer mit einem Ort a und der Nachbarschaft dieses Ortes verbunden: Vernachlässigbarkeit ist ein lokales Konzept .
In dieser Landau-Notation (manchmal auch ) lautet das Symbol klein o . Hardys äquivalente Notation ist . Heute verwenden wir ausschließlich die Landau-Notation.
EigenschaftenDurch Sprachmissbrauch führt man "Operationen" am "kleinen o" durch , dh an den vernachlässigbaren. In der Tat können wir das sagen:
Entweder .
Sei f und g zwei Funktionen der reellen Variablen x . Wir nehmen an, dass g nicht über einer Nachbarschaft von a verschwindet . Wir sagen , dass f äquivalent ist g in einem oder dass g ist äquivalent zu f in a , und wir bezeichnen
, wenn .Beispiel
Landaus große O-Notation bezeichnet den dominierten Charakter einer Funktion gegenüber einer anderen.
Normalerweise wie Paul Bachmann , die dieses Symbol im Jahr 1894 eingeführt, verwenden wir die Hauptstadt Buchstaben O (aus der deutschen Ordnung , „Ordnung“). Viel später (1976) schlug Donald Knuth in Analogie zum Omega- Symbol Ω (siehe unten) vor, das Symbol O mit dem Namen des Omicron- Großbuchstabens umzubenennen , wobei letzteres selten so klar gezeichnet wird unterscheidet sich von O. In beiden Fällen unterscheidet sich das verwendete Symbol vom Symbol 0 (Null).
Formale DefinitionSei f und g zwei Funktionen der reellen Variablen x . Wir sagen, dass f von g in + ∞ dominiert wird oder dass g f in + ∞ dominiert , und wir bezeichnen (Bachmann-Notation, 1894 oder Landau, 1909).
oder (Hardys Notation, 1910, veraltet)
oder wieder (Vinogradov Notation, 1930er Jahre)
wenn es Konstanten N und C gibt, so dass
Intuitiv bedeutet dies, dass f nicht schneller wächst als g .
Wenn a eine reelle Zahl ist, schreiben wir ebenfalls
wenn es Konstanten d > 0 und C gibt, so dass
Beispiele1914 führten Hardy und Littlewood das neue Symbol Ω ein, das wie folgt definiert ist:
.Es wird angenommen, dass die Funktionen f und g in einer Nachbarschaft von unendlich definiert und g positiv sind. So ist die Negation von .
Im Jahr 1916 führten dieselben Autoren die beiden neuen Symbole Ω R und Ω L ein , die wie folgt definiert sind:
;; .Wie zuvor wird angenommen, dass die Funktionen f und g in einer Nachbarschaft von unendlich definiert und g positiv sind. So ist die Negation von und die Negation von .
Im Gegensatz zu dem, was DE Knuth später behauptete , verwendete Edmund Landau 1924 auch diese drei Symbole.
Diese Hardy- und Littlewood-Notationen sind Prototypen, die nach Landau anscheinend nie als solche verwendet wurden: Ω R ist zu Ω + geworden , und Ω L ist zu Ω - geworden .
Diese drei Symbole werden heute häufig in der analytischen Zahlentheorie verwendet , um anzuzeigen, dass die Bedingungen erfüllt sind und beide erfüllt sind.
Es ist klar, dass wir in jeder dieser Definitionen ∞ durch –∞ oder durch eine reelle Zahl ersetzen können .
Wir haben
und genauer gesagt,
Wir haben
und genauer gesagt,
jedoch,
Es ist wichtig zu betonen, dass das Schreiben
hat zwei inkompatible Definitionen in der Mathematik, die beide sehr verbreitet sind, eine in der analytischen Zahlentheorie , die wir gerade vorgestellt haben, die andere in der Theorie der Komplexität von Algorithmen . Wenn sich diese beiden Disziplinen treffen, wird diese Situation wahrscheinlich große Verwirrung stiften.
1976 veröffentlichte Knuth einen Artikel, dessen Hauptzweck darin bestand, seine Verwendung des gleichen Symbols Ω zu rechtfertigen, um eine andere Eigenschaft als die von Hardy und Littlewood beschriebene zu beschreiben. Er versucht den Leser davon zu überzeugen, dass die Definition von Hardy und Littlewood kaum jemals verwendet wird (was selbst 1976 ohnehin seit 25 Jahren falsch ist). Er geht so weit zu behaupten, dass Landau es nie benutzt hat (was auch falsch ist). Er ist zwingend der Notwendigkeit eines anderen Begriffs verpflichtet ( „ Für alle Anwendungen, die ich bisher in der Informatik gesehen habe, ist eine stärkere Anforderung […] viel angemessener “ ) und entschied, dass die Verwendung des Ω-Symbols zur Beschreibung vorbehalten bleiben muss es. Er ist sehr verärgert über die alte Definition ( „ Leider haben Hardy und Littlewood Ω ( f ( n )) nicht so definiert, wie ich es wollte “ ).
Er geht daher das Risiko der Verwirrung ein und definiert
.In der Mathematik ist es oft wichtig, den Fehlerterm einer Näherung im Auge zu behalten. Diese Notation wird insbesondere verwendet, wenn es um begrenzte Entwicklungen und Berechnungen von Äquivalenten geht. Zum Beispiel kann die Erweiterung der Exponentialfunktion auf Ordnung 2 auch geschrieben werden:
um die Tatsache auszudrücken, dass der Fehler, die Differenz , vernachlässigbar ist, wenn gegen 0 tendiert.
Es ist zu beachten, dass die Anzahl der Operanden in dieser Art des Schreibens durch eine Konstante begrenzt sein muss, die nicht von der Variablen abhängt: Zum Beispiel ist die Behauptung offensichtlich falsch, wenn die Auslassungspunkte eine Anzahl von Begriffen verbergen, die nicht begrenzt sind, wenn x variiert.
Hier ist eine Liste von Kategorien von Funktionen, die üblicherweise in der Analyse verwendet werden. Die Variable (hier n angegeben ) tendiert zu + ∞ und c ist eine beliebige reelle Konstante. Wenn c eine Konstante größer als 1 ist, werden die Funktionen in dieser Liste in aufsteigender Größenordnung angezeigt.
Bewertung | Größe höchstens | |
O (1) | Modul um eine Konstante erhöht | |
O (log ( n )) | logarithmisch | |
O ((log ( n )) c ) | ( polylogarithmisch, wenn c eine positive ganze Zahl ist) | |
O ( n ) | linear | |
O ( n log ( n )) | manchmal als " linear " bezeichnet | |
O ( n log c (n) ) | manchmal als " quasi-linear " bezeichnet | |
O ( n 2 ) | quadratisch | |
Y ( n c ) | ( Polynom, wenn c eine positive ganze Zahl ist) | |
O ( c n ) | ( exponentiell, wenn c positiv ist, manchmal " geometrisch ") | |
O ( n! ) | Fakultät |
O ( n c ) und O ( c n ) sind sehr unterschiedlich. Letzteres ermöglicht ein viel schnelleres Wachstum, und dies für jede Konstante c > 1. Eine Funktion, die schneller zunimmt als jedes Polynom, wird als Superpolynom bezeichnet . Eine Funktion, die langsamer wächst als jedes Exponential, wird als subexponentiell bezeichnet . Es gibt sowohl Superpolynom- als auch Subexponentialfunktionen, wie beispielsweise die Funktion n log ( n ) .
Beachten Sie auch, dass O (log n ) genau das gleiche ist wie O (log ( n c )), da diese beiden Logarithmen um einen konstanten Faktor vielfach voneinander sind und die Notation groß O die multiplikativen Konstanten „ignoriert“ . In ähnlicher Weise sind Logarithmen in verschiedenen konstanten Basen äquivalent.
Die vorstehende Liste ist aufgrund der folgenden Eigenschaft nützlich: Wenn eine Funktion f eine Summe von Funktionen ist und eine der Funktionen der Summe schneller wächst als die anderen, bestimmt sie die Wachstumsreihenfolge von f ( n ).
Beispiel:
wenn f ( n ) = 10 log ( n ) + 5 (log ( n )) 3 + 7 n + 3 n 2 + 6 n 3 ,Diese Notation kann auch mit Funktionen mehrerer Variablen verwendet werden:
Schreiben : | wann |
entspricht dem Satz: |
Für einige missbraucht diese Notation das Symbol der Gleichheit, da sie das Axiom der Gleichheit zu verletzen scheint : "Gleiche Dinge sind einander gleich" (mit anderen Worten, Gleichheit ist mit dieser Notation keine Äquivalenz mehr Beziehung ). Das können wir aber auch schriftlich berücksichtigen
Die Notation "= O" bezeichnet einen einzelnen Operator, in dessen Schrift das Zeichen "=" keine eigene unabhängige Existenz hat (und insbesondere keine Äquivalenzbeziehung bezeichnet). In diesem Fall besteht kein Ratingmissbrauch mehr, aber offensichtlich besteht immer noch Verwechslungsgefahr. Es ist auch möglich, O ( g ( x )) als eine Menge von Funktionen zu definieren, deren Elemente alle Funktionen sind, die nicht schneller als g wachsen , und Mengennotationen zu verwenden, um anzuzeigen, ob eine gegebene Funktion somit ein Element der Menge ist definiert. Beispielsweise :
Beiden Vereinbarungen werden häufig verwendet , aber die erste (und älteste) ist bis zum Beginn des XXI - ten am häufigsten Jahrhundert begegnet. Um dieses Problem zu vermeiden, verwenden wir (ebenso häufig) die Vinogradov-Notation (siehe unten).
Ein weiteres Problem besteht darin, dass die Variable, anhand derer das asymptotische Verhalten untersucht wird, klar angegeben werden muss. Eine Behauptung wie diese hat nicht die gleiche Bedeutung, je nachdem, ob auf sie „wann “ oder beispielsweise „(für ein festes) wann “ folgt .
Bewertung | Nachname | Informelle Beschreibung | Wann , ab einem bestimmten Rang ... | Strenge Definition |
---|---|---|---|---|
oder
|
Grand O (Grand Omicron) |
Die Funktion | f | wird durch die Funktion | begrenzt g | asymptotisch, bis |
für ein k > 0 | |
oder
|
Großes Omega |
Zwei Definitionen:
In der Zahlentheorie: |
In der Zahlentheorie: für ein k > 0 |
In der Zahlentheorie:
|
In der Algorithmus-Theorie:
f wird durch g unterschätzt (bis zu einem Faktor) |
In der Algorithmus-Theorie:
für ein k > 0 |
In der Algorithmus-Theorie:
|
||
in der Größenordnung von ; Großer Theta |
f wird dominiert und g asymptotisch ausgesetzt |
für a k 1 > 0 und a k 2 > 0 |
|
|
oder
|
Klein o | f ist vor g asymptotisch vernachlässigbar | , was auch immer > 0 (fest). | |
Kleines Omega | f dominiert g asymptotisch | für alle k > 0 | ||
gleichwertig | f ist ungefährasymptotisch gleich g | , was auch immer > 0 (fest). |
Nach Grand-O werden die Notationen Θ und Ω in der Informatik am häufigsten verwendet. Das Small-O ist in der Mathematik üblich, in der Informatik jedoch seltener. Das ω wird wenig verwendet.
Eine andere in der Informatik manchmal verwendete Notation ist Õ ( Soft-O in Englisch), was groß-o bis zu einem polylogarithmischen Faktor bedeutet.
In der Zahlentheorie hat die Notation f ( x ) g ( x ) die gleiche Bedeutung wie f ( x ) = Θ ( g ( x )) (was nicht verwendet wird).
Die Notationen von Landau sind nach dem auf Zahlentheorie spezialisierten deutschen Mathematiker Edmund Landau benannt , der das ursprünglich von Paul Bachmann eingeführte Symbol O verwendete und sich zur Erfindung des Symbols o inspirieren ließ . Er benutzte das Symbol Ω nur in einem Artikel im Jahr 1924, um ≠ o zu bezeichnen ; Diese Notation wurde 1914 von GH Hardy und JE Littlewood (mit derselben Bedeutung) eingeführt. Seitdem wird Ω üblicherweise in der Zahlentheorie verwendet, jedoch ausschließlich in demselben Sinne und niemals in dem in der obigen Tabelle gezeigten ersten Sinne. Im gleichen Artikel verwendet Landau die Symbole Ω R und Ω L , auch aufgrund von Hardy und Littlewood (und da bezeichnet Ω + und Ω - ) bedeuten jeweils . Natürlich wird auch die Notation ∼ verwendet, aber niemals ω oder Θ.
Die Notationen von Hardy et al. , Die GH Hardy in seinem Traktat von Orden der Unendlichkeit von 1910 eingeführt hat , spielen für den asymptotischen Funktionsvergleich dieselbe Rolle wie die von Landau.
In der Landau-Notation können wir sie wie folgt definieren:
und
Hardys Bewertungen sind veraltet. Hardy gab schnell seine eigenen Bewertungen auf; er verwendet Landaus Notationen in allen seinen Artikeln (fast 400!) und in seinen Büchern, außer in seinem Traktat von 1910 und in 3 Artikeln (1910-1913). Wir können feststellen, dass Hardy, wenn er in seinem Traktat von 1910 einige andere Symbole für den asymptotischen Funktionsvergleich einführte, niemals die Notation (oder ) definiert oder verwendet hat , die wir Vinogradov schulden.
Der russische Zahlentheoretiker Ivan Matveyevich Vinogradov führte in den 1930er Jahren die Notation ein, die seinen Namen trägt.
.Vinogradovs ≪-Notation wird üblicherweise in der Zahlentheorie anstelle von O verwendet ; manchmal werden sogar die beiden Notationen im selben Artikel synonym verwendet.
1982 führte Carl Pomerance eine neue Notation ein, um die komplexen Funktionen abzukürzen, die bei der asymptotischen Untersuchung der Komplexität von Algorithmen eine Rolle spielen . So gehört zum Beispiel eine Funktion f zur Klasse, wenn wir haben ; Das Exponential "trennt" die Funktionen ausreichend, so dass es beispielsweise nicht möglich ist, diese Notation auf die Form zu reduzieren .
Insbesondere Landau-Bewertungen führen zu sehr häufigem Bewertungsmissbrauch, wie z. B. Schreiben oder Schlimmeres ; Diese zweite Notation muss in einer festgelegten Sprache gelesen werden: Durch Aufrufen der Menge vernachlässigbarer Funktionen in Bezug auf und der Menge der Unterschiede zweier Funktionen von bedeutet dies, dass . Allgemeiner bedeutet dieser Missbrauch der Notation, dass die Notation (oder usw.) als eine Klasse von Funktionen und als eine zu dieser Klasse gehörende Bedeutung betrachtet wird.
(en) Big-O Cheat Sheet , eine Site, die eine Klassifizierung der algorithmischen Komplexität nach Domänen auflistet.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">