Der Unterschied zwischen Big-O und Little-O Notation

Question

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

Answer 1

f ∈ O (g) sagt, im wesentlichen

  

mindestens ein Wahl eines konstanten k > 0, können Sie eine Konstante finden a , so dass die Ungleichheit 0 <= f (x) <= kg (x) für alle x> a.

Beachten Sie, dass O (g) ist die Menge aller Funktionen, für die diese Bedingung erfüllt ist.

f ∈ o (g) sagt, im wesentlichen

  

alle Wahl eines konstanten k > 0, können Sie eine Konstante finden a , so dass die Ungleichheit 0 <= f (x ) a.

Noch einmal zur Kenntnis, dass o (g) ist ein Satz.

In Big-O, es ist nur notwendig, dass Sie einen bestimmten Multiplikator finden k , für die die Ungleichheit hält über einige Mindest x .

In Little-o, muss es sein, dass es ein Minimum x , nach der die Ungleichheit egal hält, wie klein Sie machen k , solange es nicht negativ oder Null.

Diese beiden oberen Grenzen beschreiben, wenn auch etwas Gegen intuitiv, Little-o die stärkere Aussage ist. Es gibt eine viel größere Lücke zwischen den Wachstumsraten von f und g, wenn f ∈ o (g), als wenn f ∈ O (g).

Eine Darstellung der Unterschiede ist dies: f ∈ O (f) ist wahr, aber f ∈ o (f) falsch ist. Daher kann Big-O gelesen werden als „f ∈ O (g) bedeutet, dass asymptotisch Wachstum f nicht schneller als g ist“, während „f ∈ o (g) bedeutet, dass asymptotisch Wachstum f ist streng langsamer als g ist“. Es ist wie <= gegen <.

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

Doch für f ∈ o (g) um wahr zu sein, dann muß g umfasst eine höhere Macht von x in der Formel, und so die relative Trennung zwischen f (x) und g (x ) muss tatsächlich größer wird als x größer wird.

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

Die folgenden Bedingungen erfüllt sind für Big-O, aber ich würde nicht wahr sein, wenn Sie wenig-o verwendet:

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

Die folgenden Bedingungen erfüllt sind für wenig o:

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

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

Answer 2

Big-O ist zu wenig-o als ≤ zu < ist. Big-O ist ein integrative obere gebunden, während wenig-o eine obere Grenze ist.

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

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

In analoger Weise die Zahl 1 ist:

• ≤ 2, < 2 und ≤ 1
• nicht ≤ 0, < 0 oder < 1

Hier ist eine Tabelle, die allgemeine Idee zeigt:

(Hinweis: Die Tabelle ist ein guter Führer, aber ihre Grenze Definition in Bezug auf der oberen Grenze sein sollte < .. statt der normalen Grenze / a> Zum Beispiel 3 + (n mod 2) oszilliert zwischen 3 und 4 für immer es ist in O(1) obwohl sie nicht eine normale Grenze hat, weil es immer noch einen lim sup hat: 4.)

Ich empfehle, das Auswendiglernen, wie die Big-O-Notation konvertiert zu asymptotisch Vergleichen. Die Vergleiche sind leichter zu merken, aber weniger flexibel, weil Sie nicht Dinge wie n sagen ^{O (1)} = P.

Answer 3

Ich finde, dass, wenn ich nicht vom Konzept her kann über etwas, das Denken erfassen , warum man verwenden würde X hilfreich zu verstehen, X. (Um nicht zu sagen Sie nicht versucht haben, dass, ich bin nur die Bühne.)

[Sachen, die Sie kennen] Ein üblicher Weg zum Klassifizieren Algorithmen ist von der Laufzeit und unter Berufung auf die Big-Oh Komplexität eines Algorithmus, können Sie eine ziemlich gute Schätzung erhalten, von denen man „besser“ - je nachdem, was hat die " kleinste“-Funktion in der O! Auch in der realen Welt, O (N) ist „besser“ als O (N²), abgesehen dumme Dinge wie supermassiven Konstanten und dergleichen. [/ Stuff wissen Sie]

Lassen Sie uns sagen, es gibt einige Algorithmus, dass läuft in O (N). Ziemlich gut, nicht wahr? Aber lassen Sie uns sagen, Sie (brillante Person, Sie) kommen mit einem Algorithmus, der läuft in O ( ^N / _{loglogloglogN} ). YAY! Es ist schneller! Aber würden Sie dumme Schreiben das Gefühl, dass immer und immer wieder, wenn Sie Ihre These gerade schreiben. So können Sie sie einmal schreiben, und man kann sagen: "In dieser Arbeit habe ich bewiesen, dass Algorithmus X, vorher berechenbar in der Zeit O (N), ist in der Tat berechenbar in o (n)."

Damit jeder weiß, dass Ihr Algorithmus ist schneller --- wie viel ist unklar, aber sie wissen, seine schneller. Theoretisch. :)