Unterschied zwischen Big-O- und Little-O-Notation

Question

Was ist der Unterschied zwischen Big-O Notation O(n) y Little-O Notation o(n) ?

Answer 1

F O(g) sagt, im Wesentlichen

Für mindestens eine Wahl einer Konstante k > 0, kann man eine Konstante finden a so dass die Ungleichung 0 <= f(x) <= k g(x) für alle x > a gilt.

Man beachte, dass O(g) die Menge aller Funktionen ist, für die diese Bedingung gilt.

f o(g) sagt, im Wesentlichen

Für jede Wahl einer Konstante k > 0, kann man eine Konstante finden a so dass die Ungleichung 0 <= f(x) < k g(x) für alle x > a gilt.

Auch hier gilt, dass o(g) eine Menge ist.

Bei Big-O ist es nur notwendig, dass Sie einen bestimmten Multiplikator finden k für die die Ungleichung über ein gewisses Minimum hinaus gilt x .

In Little-o muss es ein Minimum an x danach bleibt die Ungleichheit bestehen, egal wie klein man sie macht k solange sie nicht negativ oder Null ist.

Beide beschreiben obere Schranken, obwohl Little-o etwas kontraintuitiv die stärkere Aussage ist. Der Abstand zwischen den Wachstumsraten von f und g ist viel größer, wenn f o(g) ist, als wenn f O(g) ist.

Eine Illustration der Diskrepanz ist folgende: f O(f) ist wahr, aber f o(f) ist falsch. Daher kann Big-O als "f O(g) bedeutet, dass das asymptotische Wachstum von f nicht schneller ist als das von g" gelesen werden, während "f o(g) bedeutet, dass das asymptotische Wachstum von f streng langsamer ist als das von g". Das ist wie <= gegen < .

Genauer gesagt, wenn der Wert von g(x) ein konstantes Vielfaches des Wertes von f(x) ist, dann ist f O(g) wahr. Aus diesem Grund können Sie Konstanten weglassen, wenn Sie mit der Big-O-Notation arbeiten.

Damit f o(g) wahr ist, muss g jedoch einen höheren Macht von x in seiner Formel, und so muss der relative Abstand zwischen f(x) und g(x) tatsächlich größer werden, wenn x größer wird.

Um rein mathematische Beispiele zu verwenden (und nicht auf Algorithmen zu verweisen):

Die folgenden Aussagen gelten für Big-O, würden aber nicht zutreffen, wenn Sie Little-O verwenden:

• x² O(x²)
• x² O(x² + x)
• x² O(200 * x²)

Für little-o gelten die folgenden Punkte:

• x² o(x³)
• x² o(x!)
• ln(x) o(x)

Beachten Sie, dass wenn f o(g) ist, dies f O(g) impliziert. z.B. x² o(x³), so ist es auch wahr, dass x² O(x³), (wieder denken Sie an O als <= und o als < )

Answer 2

Big-O ist für little-o wie soll < . Big-O ist eine inklusive Obergrenze, während little-o eine strenge Obergrenze ist.

Zum Beispiel kann die Funktion f(n) = 3n ist:

• in O(n²) , o(n²) y O(n)
• nicht in O(lg n) , o(lg n) , oder o(n)

Analog dazu ist die Zahl 1 ist:

• 2 , < 2 y 1
• no 0 , < 0 , oder < 1

Hier ist eine Tabelle, die die allgemeine Idee zeigt:

(Anmerkung: Die Tabelle ist ein guter Anhaltspunkt, aber ihre Grenzdefinition sollte sich auf die höhere Grenze anstelle des normalen Grenzwerts. Zum Beispiel, 3 + (n mod 2) schwankt ständig zwischen 3 und 4. Es ist in O(1) obwohl sie keine normale Grenze hat, weil sie immer noch eine lim sup : 4.)

Ich empfehle, sich einzuprägen, wie die Big-O-Notation in asymptotische Vergleiche umgewandelt wird. Die Vergleiche sind leichter zu merken, aber weniger flexibel, weil man nicht sagen kann: n O(1) \= P.

Answer 3

Wenn ich etwas begrifflich nicht fassen kann, hilft es mir, darüber nachzudenken. warum man X verwenden sollte ist hilfreich, um X zu verstehen. (Das soll nicht heißen, dass Sie das nicht schon versucht haben, ich stelle nur die Weichen).

Dinge, die Sie wissen : Eine gängige Methode zur Klassifizierung von Algorithmen ist die Laufzeit, und indem man die Big-Oh-Komplexität eines Algorithmus angibt, kann man ziemlich gut abschätzen, welcher Algorithmus "besser" ist - derjenige, der die "kleinste" Funktion im O! Selbst in der realen Welt ist O(N) "besser" als O(N²), wenn man von dummen Dingen wie supermassiven Konstanten und dergleichen absieht.

Nehmen wir an, es gibt einen Algorithmus, der in O(N) läuft. Ziemlich gut, nicht wahr? Aber nehmen wir an, Sie (Sie genialer Mensch, Sie) haben einen Algorithmus entwickelt, der in O( N _{loglogloglogN} ). JUHU! Es geht schneller! Aber man käme sich albern vor, das immer wieder zu schreiben, wenn man seine Doktorarbeit schreibt. Also schreibt man es einmal und kann sagen: "In dieser Arbeit habe ich bewiesen, dass der Algorithmus X, der bisher in O(N) Zeit berechenbar war, tatsächlich in o(n) berechenbar ist.

Jeder weiß also, dass Ihr Algorithmus schneller ist - um wie viel ist unklar, aber sie wissen, dass er schneller ist. Theoretisch. :)

Answer 4

Im Allgemeinen

Die asymptotische Notation ist etwas, das Sie verstehen können als: Wie sehen die Funktionen beim Herauszoomen aus? (Eine gute Möglichkeit, dies zu testen, ist die Verwendung eines Tools wie Desmos und spielen Sie mit Ihrem Mausrad). Im Besonderen:

• f(n) o(n) bedeutet: Je weiter man herauszoomt, desto mehr f(n) wird dominiert von n (sie weicht immer weiter davon ab).
• g(n) (n) bedeutet, dass das Herauszoomen an einem bestimmten Punkt nichts daran ändert, wie g(n) vergleichen mit n (wenn wir die Zecken von der Achse entfernen, kann man die Zoomstufe nicht erkennen).

Endlich h(n) O(n) bedeutet, dass die Funktion h kann in eine dieser beiden Kategorien fallen. Es kann entweder sehr ähnlich aussehen wie n oder sie könnte kleiner und kleiner sein als n cuando n erhöht. Grundsätzlich gilt, dass sowohl f(n) y g(n) sind auch in O(n) .

Ich denke, dieses Venn-Diagramm (aus dieser Kurs ) könnte helfen:

In der Informatik

In der Informatik beweist man in der Regel, dass ein bestimmter Algorithmus sowohl eine obere O und eine untere Grenze . Wenn beide Schranken zutreffen, bedeutet dies, dass wir einen asymptotisch optimalen Algorithmus zur Lösung dieses speziellen Problems gefunden haben .

Wenn wir zum Beispiel beweisen, dass die Komplexität eines Algorithmus sowohl in O(n) y (n) bedeutet dies, dass seine Komplexität in (n) . (Das ist die Definition von und das bedeutet mehr oder weniger "asymptotisch gleich"). Das bedeutet auch, dass kein Algorithmus das gegebene Problem lösen kann in o(n) . Auch hier gilt in etwa: "Dieses Problem kann nicht in (streng) weniger als einer Stunde gelöst werden. n Schritte".

Normalerweise ist die o wird im Rahmen des Beweises der unteren Schranke verwendet, um einen Widerspruch zu zeigen. Zum Beispiel:

Angenommen, der Algorithmus A kann den Mindestwert in einem Array der Größe n en o(n) Schritte. Da A o(n) es kann nicht alle Elemente der Eingabe sehen. Mit anderen Worten, es gibt mindestens ein Element x die A nie gesehen. Algorithmus A den Unterschied zwischen zwei ähnlichen Eingaben nicht erkennen kann, bei denen nur x Wert ändert. Wenn x in einem dieser Fälle das Minimum ist und im anderen nicht, dann A wird bei (mindestens) einer dieser Instanzen das Minimum nicht finden. Mit anderen Worten, die Suche nach dem Minimum in einem Array ist in (n) (kein Algorithmus in o(n) kann das Problem lösen).

Details zu den Bedeutungen der unteren/oberen Grenze

Eine Obergrenze von O(n) bedeutet einfach, dass auch Im schlimmsten Fall endet der Algorithmus nach höchstens n Schritte (ohne Berücksichtigung aller konstanten Faktoren, sowohl multiplikativ als auch additiv). Eine untere Schranke von (n) ist eine Aussage über das Problem selbst, sie besagt, dass wir ein oder mehrere Beispiele gebaut haben, bei denen das gegebene Problem kann von keinem Algorithmus in weniger als einer Stunde gelöst werden. n Schritte (ohne Berücksichtigung der multiplikativen und additiven Konstanten). Die Anzahl der Schritte ist höchstens n und mindestens n Diese Problemkomplexität ist also "genau n ". Anstatt jedes Mal "konstanten multiplikativen/additiven Faktor ignorieren" zu sagen, schreiben wir einfach (n) kurz gesagt.

Answer 5

Die Big-O-Notation hat ein Gegenstück, die Small-O-Notation. Die Big-O-Notation besagt, dass die eine Funktion asymptotisch ist no more than eine andere. Zu sagen, dass eine Funktion asymptotisch ist less than eine andere, verwenden wir die Small-O-Notation. Der Unterschied zwischen der big-O- und der small-o-Schreibweise ist analog zum Unterschied zwischen <= (kleiner als gleich) und < (kleiner als).