Was ist der Unterschied zwischen Big-O- Notation O(n)
und Little-O- Notation o(n)
?
quelle
Was ist der Unterschied zwischen Big-O- Notation O(n)
und Little-O- Notation o(n)
?
f ∈ O (g) sagt im Wesentlichen
Für mindestens eine Wahl einer Konstanten k > 0 können Sie eine Konstante a finden, so dass die Ungleichung 0 <= f (x) <= kg (x) für alle x> a gilt.
Beachten Sie, 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 Konstanten k > 0 können Sie eine Konstante a finden, so dass die Ungleichung 0 <= f (x) <kg (x) für alle x> a gilt.
Beachten Sie erneut, dass o (g) eine Menge ist.
In Big-O ist es nur erforderlich, dass Sie einen bestimmten Multiplikator k finden, für den die Ungleichung über ein Minimum x hinausgeht .
In Little-o muss es sein, dass es ein Minimum x gibt, nach dem die Ungleichung gilt, egal wie klein Sie k machen , solange sie nicht negativ oder null ist.
Diese beiden beschreiben Obergrenzen, obwohl etwas kontraintuitiv, ist Little-o die stärkere Aussage. Es gibt eine viel größere Lücke zwischen den Wachstumsraten von f und g, wenn f ∈ o (g) als wenn f ∈ O (g).
Ein Beispiel für die Ungleichheit ist: f ∈ O (f) ist wahr, aber f ∈ o (f) ist falsch. Daher kann Big-O gelesen werden als "f ∈ O (g) bedeutet, dass das asymptotische Wachstum von f nicht schneller ist als das von g", während "f ∈ o (g) bedeutet, dass das asymptotische Wachstum von f streng langsamer ist als das von g". Es ist wie <=
gegen <
.
Insbesondere 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 löschen, wenn Sie mit der Big-O-Notation arbeiten.
Damit jedoch f ∈ o (g) wahr ist, muss g eine höhere Potenz von x in seine Formel aufnehmen, und daher muss der relative Abstand zwischen f (x) und g (x) tatsächlich größer werden, wenn x größer wird.
So verwenden Sie rein mathematische Beispiele (anstatt sich auf Algorithmen zu beziehen):
Folgendes gilt für Big-O, würde aber nicht zutreffen, wenn Sie little-o verwenden:
Für little-o gilt Folgendes:
Beachten Sie, dass wenn f ∈ o (g) ist, dies f ∈ O (g) impliziert. zB x² ∈ o (x³), so dass es auch wahr ist, dass x² ∈ O (x³), (wieder denken Sie an O als <=
und o als <
)
a
gibt esk
das: ...", es ist "für jedenk
gibt esa
das: ..."Big-O ist zu wenig-o wie
≤
zu<
. Big-O ist eine inklusive Obergrenze, während Little-O eine strenge Obergrenze ist.Zum Beispiel die Funktion
f(n) = 3n
:O(n²)
,o(n²)
undO(n)
O(lg n)
,o(lg n)
odero(n)
Analog die Nummer
1
lautet :≤ 2
,< 2
Und≤ 1
≤ 0
,< 0
oder< 1
Hier ist eine Tabelle, die die allgemeine Idee zeigt:
(Hinweis: Die Tabelle ist ein guter Leitfaden, aber ihre Grenzwertdefinition sollte sich auf den übergeordneten Grenzwert anstelle des normalen Grenzwerts beziehen. Beispielsweise
3 + (n mod 2)
schwankt sie für immer zwischen 3 und 4. Sie ist in,O(1)
obwohl sie keinen normalen Grenzwert hat, da sie immer noch vorhanden ist alim sup
: 4.)Ich empfehle, sich zu merken, wie die Big-O-Notation in asymptotische Vergleiche umgewandelt wird. Die Vergleiche sind leichter zu merken, aber weniger flexibel, da man Dinge wie n O (1) = P nicht sagen kann.
quelle
Ich finde das, wenn ich etwas konzeptionell nicht erfassen kann und darüber nachdenke, warum man X verwenden würde ist es hilfreich zu verstehen. (Um nicht zu sagen, dass Sie das nicht versucht haben, ich bereite nur die Bühne vor.)
[Dinge, die Sie wissen] Eine übliche Methode zur Klassifizierung von Algorithmen ist die Laufzeit. Wenn Sie die große Komplexität eines Algorithmus angeben, können Sie ziemlich gut abschätzen, welcher Algorithmus "besser" ist - je nachdem, welcher die "kleinste" Funktion hat im O! Selbst in der realen Welt ist O (N) "besser" als O (N²), abgesehen von albernen Dingen wie supermassiven Konstanten und dergleichen. [/ Sachen, die Sie kennen]
Angenommen, es gibt einen Algorithmus, der in O (N) ausgeführt wird. Ziemlich gut, oder? Angenommen , Sie (Sie brillante Person, Sie) haben einen Algorithmus entwickelt, der in O ( N ⁄ loglogloglogN ) ausgeführt wird. YAY! Es ist schneller! Aber Sie würden sich dumm fühlen, wenn Sie Ihre Abschlussarbeit schreiben. Sie schreiben es also einmal und können sagen: "In diesem Artikel habe ich bewiesen, dass der Algorithmus X, der zuvor in der Zeit O (N) berechenbar war, tatsächlich in o (n) berechenbar ist."
Somit weiß jeder, dass Ihr Algorithmus schneller ist - um wie viel unklar ist, aber er weiß, dass er schneller ist. Theoretisch. :) :)
quelle