Wie lautet eine einfache englische Erklärung der "Big O"-Notation?

Question

Ich bevorzuge so wenig formale Definitionen wie möglich und einfache Mathematik.

Answer 1

Wie lautet eine einfache englische Erklärung der "Big O"-Notation?

Sehr kurze Anmerkung:

Das "O" in "Big O" steht für "Order" (oder genauer gesagt für "Bestellung von")
Man könnte also buchstäblich auf die Idee kommen, dass es dazu dient, etwas zu bestellen, um es zu vergleichen.

• "Big O" macht zwei Dinge:

  1. Schätzt, wie viele Schritte der Methode Ihr Computer anwendet, um eine Aufgabe zu erledigen.
  2. Erleichtern Sie den Prozess des Vergleichs mit anderen, um festzustellen, ob er gut ist oder nicht?
  3. "Big O' erreicht die beiden oben genannten Ziele mit standardisierten Notations .

• Es gibt sieben häufig verwendete Bezeichnungen

  1. O(1), bedeutet, dass Ihr Computer eine Aufgabe erledigt mit 1 Schritt, es ist ausgezeichnet, Bestellte Nr.1
  2. O(logN), d. h. Ihr Computer erledigt eine Aufgabe mit logN steps, its good, No.2 bestellt
  3. O(N), beenden Sie eine Aufgabe mit N Schritte, seine Messe, Auftrag Nr.3
  4. O(NlogN), beendet eine Aufgabe mit O(NlogN) Stufen, das ist nicht gut, Auftrag Nr.4
  5. O(N^2), erledigen Sie eine Aufgabe mit N^2 Schritte, es ist schlimm, Auftrag Nr.5
  6. O(2^N), eine Aufgabe zu erledigen mit 2^N Stufen, es ist furchtbar, Auftrag Nr. 6
  7. O(N!), erledigen Sie eine Aufgabe mit N! Stufen, es ist schrecklich, Auftrag Nr. 7

Angenommen, Sie erhalten die Notation O(N^2) ist nicht nur klar, dass die Methode N*N Schritte benötigt, um eine Aufgabe zu erledigen, sondern auch, dass sie nicht so gut ist wie O(NlogN) von seiner Rangliste.

Bitte beachten Sie zum besseren Verständnis die Reihenfolge am Zeilenende, es gibt mehr als 7 Notationen, wenn man alle Möglichkeiten berücksichtigt.

In der Informatik werden die einzelnen Schritte zur Erfüllung einer Aufgabe als Algorithmen bezeichnet.
In der Terminologie wird die Big-O-Notation verwendet, um die Leistung oder Komplexität eines Algorithmus zu beschreiben.

Darüber hinaus legt Big O den ungünstigsten Fall fest oder misst die Upper-Bound-Schritte.
Sie können sich im besten Fall auf Big- (Big-Omega) beziehen.

Big- (Big-Omega) Notation (Artikel) | Khan Academy

• Zusammenfassung
  "Big O" beschreibt die Leistung des Algorithmus und bewertet sie.

  Big O" klassifiziert die Algorithmen und standardisiert den Vergleichsprozess.

Answer 2

Ich habe einen einfacheren Weg, um die zeitliche Komplexität zu verstehen ie gebräuchlichste Metrik zur Berechnung der Zeitkomplexität ist die Big-O-Notation. Dabei werden alle konstanten Faktoren entfernt, so dass die Laufzeit im Verhältnis zu N geschätzt werden kann, wenn N sich der Unendlichkeit nähert. Im Allgemeinen kann man sich das so vorstellen:

statement;

ist konstant. Die Laufzeit der Anweisung ändert sich nicht in Abhängigkeit von N

for ( i = 0; i < N; i++ )
  statement;

ist linear. Die Laufzeit der Schleife ist direkt proportional zu N. Wenn sich N verdoppelt, verdoppelt sich auch die Laufzeit.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

ist quadratisch. Die Laufzeit der beiden Schleifen ist proportional zum Quadrat von N. Wenn sich N verdoppelt, steigt die Laufzeit um N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

ist logarithmisch. Die Laufzeit des Algorithmus ist proportional zu der Anzahl, wie oft N durch 2 geteilt werden kann, da der Algorithmus den Arbeitsbereich bei jeder Iteration halbiert.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Ist N * log ( N ). Die Laufzeit besteht aus N Schleifen (iterativ oder rekursiv), die logarithmisch sind, der Algorithmus ist also eine Kombination aus linear und logarithmisch.

Im Allgemeinen ist es linear, etwas mit jedem Element in einer Dimension zu tun, quadratisch, etwas mit jedem Element in zwei Dimensionen zu tun, und logarithmisch, den Arbeitsbereich zu halbieren. Es gibt noch andere Big-O-Maße wie kubisch, exponentiell und Quadratwurzel, aber sie sind nicht annähernd so gebräuchlich. Die Big-O-Notation wird als O ( ) beschrieben, wobei das Maß das Maß ist. Der Quicksortieralgorithmus würde als O ( N * log ( N ) ) beschrieben werden.

Hinweis: Bei all diesen Überlegungen wurden der beste, der durchschnittliche und der schlechteste Fall nicht berücksichtigt. Für jeden Fall gibt es eine eigene Big-O-Notation. Beachten Sie auch, dass dies eine SEHR vereinfachte Erklärung ist. Big O ist die gebräuchlichste Notation, aber sie ist auch komplexer, als ich gezeigt habe. Es gibt auch andere Notationen wie Big Omega, Little O und Big Theta. Außerhalb eines Algorithmus-Analysekurses werden Sie ihnen wahrscheinlich nicht begegnen.

• Siehe mehr unter: Hier

Answer 3

Angenommen, es handelt sich um einen Algorithmus A die etwas mit einem Datensatz der Größe n .

Entonces O( <some expression X involving n> ) bedeutet, in einfachem Englisch:

Wenn Sie bei der Ausführung von A Pech haben, kann es bis zu X(n) Operationen dauern, um abzuschließen.

Tatsächlich gibt es bestimmte Funktionen (denken Sie an sie als Implementierungen de X(n) ), die in der Regel recht häufig auftreten. Diese sind gut bekannt und leicht zu vergleichen (Beispiele: 1 , Log N , N , N^2 , N! , etc..)

Wenn man diese vergleicht, wenn man über A und anderen Algorithmen ist es einfach, die Algorithmen nach der Anzahl der Operationen zu ordnen, die sie Mai (im schlimmsten Fall) bis zum Abschluss benötigen.

Im Allgemeinen besteht unser Ziel darin, einen Algorithmus zu finden oder zu strukturieren A in der Weise, dass sie eine Funktion haben wird X(n) die eine möglichst niedrige Zahl ergibt.

Answer 4

Wenn Sie eine geeignete Vorstellung von der Unendlichkeit in Ihrem Kopf haben, dann gibt es eine sehr kurze Beschreibung:

Die Big-O-Notation gibt die Kosten für die Lösung eines unendlich großen Problems an.

Und darüber hinaus

Konstante Faktoren sind vernachlässigbar

Wenn Sie auf einen Computer aufrüsten, der Ihren Algorithmus doppelt so schnell ausführen kann, wird die Big-O-Notation das nicht bemerken. Verbesserungen durch konstante Faktoren sind zu gering, um in dem Maßstab, mit dem die Big-O-Notation arbeitet, überhaupt bemerkt zu werden. Beachten Sie, dass dies ein bewusster Teil des Designs der Big-O-Notation ist.

Alles, was "größer" als ein konstanter Faktor ist, kann jedoch erkannt werden.

Wenn Sie daran interessiert sind, Berechnungen durchzuführen, deren Umfang "groß" genug ist, um als annähernd unendlich betrachtet zu werden, dann ist die Notation Big O ungefähr die Kosten für die Lösung Ihres Problems.

---

Wenn die obigen Ausführungen keinen Sinn ergeben, dann haben Sie keine kompatible intuitive Vorstellung von der Unendlichkeit in Ihrem Kopf, und Sie sollten wahrscheinlich alles oben Gesagte ignorieren; die einzige Möglichkeit, die ich kenne, um diese Ideen rigoros zu machen oder sie zu erklären, wenn sie nicht bereits intuitiv nützlich sind, ist, Ihnen zuerst die Big-O-Notation oder etwas Ähnliches beizubringen. (obwohl es sich lohnen könnte, diese Ideen wieder aufzugreifen, wenn Sie die Big-O-Notation in Zukunft gut verstehen)

Answer 5

Sagen wir, Sie bestellen Harry Potter: Complete 8-Film Collection [Blu-ray] bei Amazon und laden Sie die gleiche Filmsammlung gleichzeitig online herunter. Sie möchten testen, welche Methode schneller ist. Die Lieferung braucht fast einen Tag, um anzukommen, und der Download ist etwa 30 Minuten früher abgeschlossen. Na toll! Es ist also ein knappes Rennen.

Was ist, wenn ich mehrere Blu-ray-Filme wie Der Herr der Ringe, Twilight, The Dark Knight Trilogy, usw. bestelle und alle Filme gleichzeitig online herunterlade? In diesem Fall dauert die Lieferung immer noch einen Tag, aber der Online-Download ist erst nach 3 Tagen abgeschlossen. Beim Online-Einkauf hat die Anzahl der gekauften Artikel (Input) keinen Einfluss auf die Lieferfrist. Die Ausgabe ist konstant. Wir nennen dies O(1) .

Beim Online-Download ist die Download-Zeit direkt proportional zur Größe der Filmdateien (Input). Wir nennen dies O(n) .

Aus den Experimenten wissen wir, dass Online-Einkäufe besser skalieren als Online-Downloads. Es ist sehr wichtig, die Big-O-Notation zu verstehen, denn sie hilft Ihnen bei der Analyse der Skalierbarkeit y Effizienz von Algorithmen.

Note : Die Notation des großen O steht für die Worst-Case-Szenario eines Algorithmus. Nehmen wir an, dass O(1) y O(n) sind die Worst-Case-Szenarien des obigen Beispiels.

Referenz : http://carlcheo.com/compsci