Looking for algorithm Keywords? Try Ask4Keywords

algorithmBig-O-Notation


Bemerkungen

Definition

Die Big-O-Notation ist im Kern eine mathematische Notation, mit der die Konvergenzrate von Funktionen verglichen wird. Sei n -> f(n) und n -> g(n) Funktionen, die über die natürlichen Zahlen definiert sind. Dann sagen wir, dass f = O(g) genau dann ist, wenn f(n)/g(n) begrenzt ist, wenn n gegen unendlich geht. Mit anderen Worten ist f = O(g) genau dann, wenn eine Konstante A existiert, so dass für alle n f(n)/g(n) <= A .

Tatsächlich ist der Umfang der Big-O-Notation in der Mathematik etwas breiter, aber der Einfachheit halber habe ich sie auf das beschränkt, was in der Algorithmus-Komplexitätsanalyse verwendet wird: Funktionen, die auf Naturals definiert sind und deren Werte nicht Null sind, und der Fall n zur Unendlichkeit.

Was heißt das ?

Nehmen wir den Fall von f(n) = 100n^2 + 10n + 1 und g(n) = n^2 . Es ist ziemlich klar, dass beide Funktionen zur Unendlichkeit neigen, während n zur Unendlichkeit neigt. Aber manchmal reicht es nicht aus, das Limit zu kennen, und wir möchten auch wissen, wie schnell sich die Funktionen ihrem Limit nähern. Begriffe wie Big-O helfen, Funktionen anhand ihrer Konvergenzgeschwindigkeit zu vergleichen und zu klassifizieren.

Finden wir heraus, ob f = O(g) indem Sie die Definition anwenden. Wir haben f(n)/g(n) = 100 + 10/n + 1/n^2 . Da 10/n 10 ist , wenn n 1 ist , und nimmt ab, und da 1/n^2 1 ist , wenn n 1 ist und auch abnimmt, haben wir f(n)/g(n) <= 100 + 10 + 1 = 111 f f(n)/g(n) <= 100 + 10 + 1 = 111 . Die Definition ist erfüllt, weil wir eine Grenze von f(n)/g(n) (111) und so f = O(g) (wir sagen, dass f ein Big-O von n^2 ).

Dies bedeutet, dass f bei etwa der gleichen Geschwindigkeit wie g gegen unendlich geht. Nun mag das seltsam erscheinen, denn wir haben festgestellt, dass f höchstens 111-mal größer als g ist. Mit anderen Worten: Wenn g um 1 wächst, wächst f um höchstens 111. Es scheint, als würde es wachsen 111 mal schneller ist nicht "etwa die gleiche Geschwindigkeit". Tatsächlich ist die Big-O-Notation kein sehr präziser Weg, um die Geschwindigkeit der Funktionskonvergenz zu klassifizieren. Aus diesem Grund verwenden wir in der Mathematik die Äquivalenzbeziehung, wenn wir eine genaue Abschätzung der Geschwindigkeit wünschen. Für die Trennung von Algorithmen in großen Geschwindigkeitsklassen reicht Big-O jedoch aus. Wir müssen keine Funktionen trennen, die eine festgelegte Anzahl von Malen schneller wachsen als sich, sondern nur Funktionen, die unendlich schneller wachsen als sich. Wenn wir zum Beispiel h(n) = n^2*log(n) , sehen wir, dass h(n)/g(n) = log(n) was mit n gegen unendlich geht, also ist h nicht O (n ^) 2), weil h unendlich schneller wächst als n ^ 2.

Nun muss ich noch eine Randnotiz machen: Sie haben vielleicht bemerkt, dass wenn f = O(g) und g = O(h) , dann f = O(h) . In unserem Fall haben wir beispielsweise f = O(n^3) und f = O(n^4) ... In der Algorithmuskomplexitätsanalyse sagen wir häufig f = O(g) zu bedeuten, dass f = O(g) und g = O(f) , was als "g ist das kleinste Big-O für f" verstanden werden kann. In der Mathematik sagen wir, dass solche Funktionen große Thetas voneinander sind.

Wie wird es benutzt ?

Beim Vergleich der Algorithmusleistung interessieren wir uns für die Anzahl der Operationen, die ein Algorithmus ausführt. Dies wird als Zeitkomplexität bezeichnet . In diesem Modell wird davon ausgegangen, dass jede Grundoperation (Addition, Multiplikation, Vergleich, Zuweisung usw.) eine bestimmte Zeit in Anspruch nimmt, und wir zählen die Anzahl dieser Operationen. Wir können diese Zahl normalerweise als Funktion der Größe der Eingabe ausdrücken, die wir n nennen. Und leider steigt diese Zahl normalerweise mit n auf unendlich (wenn nicht, sagen wir, dass der Algorithmus O (1) ist). Wir trennen unsere Algorithmen in große, von Big-O definierte Geschwindigkeitsklassen: Wenn wir von einem "O (n ^ 2) -Algorithmus" sprechen, meinen wir, dass die Anzahl der durchgeführten Operationen, ausgedrückt als Funktion von n, ein O ( n ^ 2). Dies besagt, dass unser Algorithmus ungefähr so ​​schnell ist wie ein Algorithmus, der eine Anzahl von Operationen ausführen würde, die dem Quadrat der Größe seiner Eingabe entspricht oder schneller . Der "oder schnellere" Teil ist da, weil ich Big-O anstelle von Big-Theta verwendet habe, aber normalerweise sagen die Leute Big-O, um Big-Theta zu bedeuten.

Beim Zählen von Operationen berücksichtigen wir normalerweise den ungünstigsten Fall: Wenn wir beispielsweise eine Schleife haben, die höchstens n-mal ausgeführt werden kann und 5 Operationen enthält, beträgt die Anzahl der Operationen, die wir zählen, 5n. Es ist auch möglich, die durchschnittliche Fallkomplexität zu berücksichtigen.

Schneller Hinweis: Ein schneller Algorithmus führt nur wenige Operationen aus. Wenn also die Anzahl der Operationen schneller auf unendlich geht, ist der Algorithmus langsamer : O (n) ist besser als O (n ^ 2).

Manchmal interessieren wir uns auch für die räumliche Komplexität unseres Algorithmus. Zu diesem Zweck betrachten wir die Anzahl der Bytes im Speicher, die der Algorithmus als Funktion der Größe der Eingabe belegt, und verwenden Big-O auf dieselbe Weise.

Big-O-Notation Verwandte Beispiele