Frage Was ist eine einfache englische Erklärung der "Big O" -Notation?


Ich würde so wenig formale Definition wie möglich und einfache Mathematik bevorzugen.


4529
2018-01-28 11:10


Ursprung


Antworten:


Schnelle Notiz, das ist fast sicher verwirrend Große O-Notation (das ist eine obere Grenze) mit Theta-Notation (die eine Zwei-Seiten-Grenze ist). Meiner Erfahrung nach ist dies typisch für Diskussionen in nicht-akademischen Umgebungen. Entschuldigung für jede mögliche Verwirrung.


Große O-Komplexität kann mit diesem Graph visualisiert werden:

Big O Analysis

Die einfachste Definition, die ich für die Big-O-Notation geben kann, ist folgende:

Die Big-O-Notation ist eine relative Repräsentation der Komplexität eines Algorithmus.

Es gibt einige wichtige und bewusst gewählte Wörter in diesem Satz:

  • relativ: Sie können Äpfel nur mit Äpfeln vergleichen. Sie können einen Algorithmus zur arithmetischen Multiplikation nicht mit einem Algorithmus vergleichen, der eine Liste von Ganzzahlen sortiert. Aber ein Vergleich von zwei Algorithmen, um arithmetische Operationen (eine Multiplikation, eine Addition) zu tun, wird Ihnen etwas Sinnvolles erzählen;
  • Darstellung: Big-O (in seiner einfachsten Form) reduziert den Vergleich zwischen Algorithmen auf eine einzelne Variable. Diese Variable wird basierend auf Beobachtungen oder Annahmen ausgewählt. Zum Beispiel werden Sortieralgorithmen typischerweise basierend auf Vergleichsoperationen verglichen (Vergleichen von zwei Knoten, um ihre relative Reihenfolge zu bestimmen). Dies setzt voraus, dass der Vergleich teuer ist. Aber was, wenn Vergleich billig ist, aber Swapping ist teuer? Es ändert den Vergleich; und
  • Komplexität: Wenn ich eine Sekunde brauche, um 10.000 Elemente zu sortieren, wie lange brauche ich, um eine Million zu sortieren? Komplexität ist in diesem Fall ein relatives Maß für etwas anderes.

Komm zurück und lies das obige weiter, wenn du den Rest gelesen hast.

Das beste Beispiel für Big-O, das ich mir vorstellen kann, ist das Rechnen. Nimm zwei Nummern (123456 und 789012). Die Grundrechenarten, die wir in der Schule gelernt haben, waren:

  • Zusatz;
  • Subtraktion;
  • Multiplikation; und
  • Aufteilung.

Jeder von diesen ist eine Operation oder ein Problem. Eine Methode, diese zu lösen, nennt man Algorithmus.

Die Addition ist die einfachste. Sie zeichnen die Zahlen nach oben (nach rechts) und fügen die Ziffern in einer Spalte hinzu, die die letzte Nummer dieses Zusatzes in das Ergebnis schreibt. Der Zehner-Teil dieser Nummer wird in die nächste Spalte übertragen.

Nehmen wir an, dass die Addition dieser Zahlen die teuerste Operation in diesem Algorithmus ist. Es liegt nahe, dass wir, um diese zwei Zahlen zusammen zu addieren, 6 Ziffern addieren müssen (und möglicherweise eine 7 tragen). Wenn wir zwei 100-stellige Zahlen addieren, müssen wir 100 hinzufügen. Wenn wir hinzufügen zwei 10.000stellige Zahlen müssen wir 10.000 hinzufügen.

Siehst du das Muster? Das Komplexität (ist die Anzahl der Operationen) ist direkt proportional zur Anzahl der Ziffern n in der größeren Anzahl. Wir nennen das Auf) oder lineare Komplexität.

Die Subtraktion ist ähnlich (außer Sie müssen möglicherweise Geld leihen statt tragen).

Multiplikation ist anders. Sie ordnen die Zahlen an, nehmen die erste Ziffer in der unteren Zahl und multiplizieren sie abwechselnd mit jeder Ziffer in der oberen Zahl und so weiter durch jede Ziffer. Um also unsere zwei sechsstelligen Zahlen zu multiplizieren, müssen wir 36 Multiplikationen machen. Wir müssen möglicherweise 10 oder 11 Spalten hinzufügen, um auch das Endergebnis zu erhalten.

Wenn wir zwei 100-stellige Zahlen haben, müssen wir 10.000 Multiplikationen und 200 Additionen durchführen. Für zwei Millionen Ziffern müssen wir eine Billion (1012) Multiplikationen und zwei Millionen Additionen.

Da der Algorithmus mit n- skaliertkariert, das ist Auf2) oder quadratische Komplexität. Dies ist ein guter Zeitpunkt, um ein weiteres wichtiges Konzept vorzustellen:

Wir kümmern uns nur um den wichtigsten Teil der Komplexität.

Der Schlaue hat vielleicht erkannt, dass wir die Anzahl der Operationen wie folgt ausdrücken können: n2 + 2n. Aber wie Sie aus unserem Beispiel mit zwei Zahlen von je einer Million Ziffern gesehen haben, wird die zweite Amtszeit (2n) bedeutungslos (für 0,0002% der gesamten Vorgänge in dieser Phase).

Man merkt, dass wir hier das Worst-Case-Szenario angenommen haben. Bei der Multiplikation von 6-stelligen Zahlen, wenn eine 4-stellig und die andere 6-stellig ist, haben wir nur 24 Multiplikationen. Dennoch berechnen wir das Worst-Case-Szenario für dieses "n", d. H. Wenn beide 6-stellige Zahlen sind. Daher bezieht sich die Big-O-Notation auf das Worst-Case-Szenario eines Algorithmus

Das Telefonbuch

Das nächstbeste Beispiel, das ich mir vorstellen kann, ist das Telefonbuch, das normalerweise als White Pages oder ähnlich bezeichnet wird, aber es wird von Land zu Land variieren. Aber ich spreche über den, der Leute mit dem Familiennamen und dann mit Initialen oder Vornamen auflistet, möglicherweise Adressen und dann Telefonnummern.

Wenn Sie nun einen Computer anweisen würden, die Telefonnummer für "John Smith" in einem Telefonbuch mit 1.000.000 Namen nachzuschlagen, was würden Sie tun? Ignoriert man die Tatsache, dass man rätseln konnte, wie weit die Ss angefangen haben (nehmen wir an, Sie können das nicht), was würden Sie tun?

Eine typische Implementierung könnte sein, sich bis zur Mitte zu öffnen, die 500.000 zu nehmenth und vergleiche es mit "Smith". Wenn es "Smith, John" ist, haben wir einfach richtig viel Glück. Viel wahrscheinlicher ist, dass "John Smith" vor oder nach diesem Namen steht. Wenn es danach ist, teilen wir die letzte Hälfte des Telefonbuchs in zwei Hälften und wiederholen es. Wenn es vorher ist, teilen wir die erste Hälfte des Telefonbuchs in zwei Hälften und wiederholen es. Und so weiter.

Das nennt man a binäre Suche und wird jeden Tag in der Programmierung verwendet, ob Sie es realisieren oder nicht.

Also, wenn Sie einen Namen in einem Telefonbuch mit einer Million Namen finden möchten, können Sie tatsächlich einen beliebigen Namen finden, indem Sie dies höchstens 20 Mal tun. Beim Vergleich von Suchalgorithmen entscheiden wir, dass dieser Vergleich unser 'n' ist.

  • Für ein Telefonbuch mit 3 Namen braucht es höchstens 2 Vergleiche.
  • Für 7 dauert es höchstens 3.
  • Für 15 dauert es 4.
  • ...
  • Für 1.000.000 sind es 20.

Das ist erstaunlich gut, nicht wahr?

In Big-O-Bedingungen ist das so O (log n) oder logarithmische Komplexität. Nun könnte der Logarithmus ln sein (Basis e), log10, log2 oder irgendeine andere Basis. Es macht nichts, es ist immer noch O (log n) genau wie O (2n2) und O (100n2) sind immer noch beide O (n2).

An dieser Stelle lohnt es sich zu erklären, dass mit Big O drei Fälle mit einem Algorithmus bestimmt werden können:

  • I'm besten fall: In der Telefonbuchsuche ist der beste Fall, dass wir den Namen in einem Vergleich finden. Das ist O (1) oder konstante Komplexität;
  • Erwarteter Fall: Wie oben diskutiert, ist dies O (log n); und
  • Schlimmsten Fall: Dies ist auch O (log n).

Normalerweise interessiert uns der beste Fall nicht. Wir interessieren uns für den erwarteten und den schlimmsten Fall. Manchmal wird der eine oder der andere wichtiger sein.

Zurück zum Telefonbuch.

Was ist, wenn Sie eine Telefonnummer haben und einen Namen finden möchten? Die Polizei hat ein umgekehrtes Telefonbuch, aber solche Nachschlagewerke werden der Öffentlichkeit verweigert. Oder sind Sie? Technisch können Sie eine Nummer in einem gewöhnlichen Telefonbuch nachschlagen. Wie?

Sie beginnen mit dem Vornamen und vergleichen die Nummer. Wenn es ein Match ist, toll, wenn nicht, dann geht es weiter zum nächsten. Sie müssen es so machen, weil das Telefonbuch ist ungeordnet (per Telefonnummer sowieso).

Also um einen Namen mit der Telefonnummer zu finden (Reverse Lookup):

  • I'm besten fall: O (1);
  • Erwarteter Fall: O (n) (für 500.000); und
  • Schlimmsten Fall: O (n) (für 1.000.000).

Der fahrende Verkäufer

Dies ist ein ziemlich bekanntes Problem in der Informatik und verdient eine Erwähnung. In diesem Problem haben Sie N Städte. Jede dieser Städte ist mit einer oder mehreren anderen Städten durch eine bestimmte Straße verbunden. Das Problem des Traveling Salesman ist es, die kürzeste Tour zu finden, die jede Stadt besucht.

Klingt einfach? Denk nochmal.

Wenn Sie 3 Städte A, B und C mit Straßen zwischen allen Paaren haben, dann könnten Sie gehen:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Nun, eigentlich gibt es weniger als das, weil einige von ihnen äquivalent sind (A → B → C und C → B → A sind äquivalent, zum Beispiel, weil sie dieselben Straßen benutzen, nur umgekehrt).

In Wirklichkeit gibt es 3 Möglichkeiten.

  • Nimm das in 4 Städte und du hast 12 Möglichkeiten.
  • Mit 5 ist es 60.
  • 6 wird 360.

Dies ist eine Funktion einer mathematischen Operation namens a Fakultät. Grundsätzlich gilt:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • ...
  • 25! = 25 × 24 × ... × 2 × 1 = 15.511.210.043.330.985.984.000.000
  • ...
  • 50! = 50 × 49 × ... × 2 × 1 = 3,04140932 × 1064

So ist das Big-O des Problems des Traveling Salesman Auf!) oder faktorielle oder kombinatorische Komplexität.

Zu der Zeit, in der du in 200 Städte kommst, ist nicht mehr genug Zeit im Universum, um das Problem mit herkömmlichen Computern zu lösen.

Etwas zum Nachdenken.

Polynomzeit

Ein weiterer Punkt, den ich kurz erwähnen möchte, ist, dass jeder Algorithmus, der eine Komplexität von Aufein) soll gesagt haben Polynomkomplexität oder ist lösbar in Polynomzeit.

O (n), O (n2) usw. sind alle Polynomzeit. Einige Probleme können nicht in polynomieller Zeit gelöst werden. Bestimmte Dinge werden deshalb in der Welt verwendet. Public Key Cryptography ist ein Paradebeispiel. Es ist rechnerisch schwierig, zwei Primfaktoren einer sehr großen Anzahl zu finden. Wenn nicht, könnten wir die von uns verwendeten öffentlichen Schlüsselsysteme nicht verwenden.

Wie auch immer, das ist es für meine (hoffentlich einfache Englisch) Erklärung von Big O (überarbeitet).


6089
2018-01-28 11:18



Es zeigt, wie ein Algorithmus skaliert.

Auf2): bekannt als Quadratische Komplexität

  • 1 Artikel: 1 Sekunde
  • 10 Gegenstände: 100 Sekunden
  • 100 Artikel: 10000 Sekunden

Beachten Sie, dass sich die Anzahl der Elemente um den Faktor 10 erhöht, die Zeit jedoch um den Faktor 10 zunimmt2. Grundsätzlich ist n = 10 und so O (n2) gibt uns den Skalierungsfaktor n2 was 10 ist2.

Auf): bekannt als Lineare Komplexität

  • 1 Artikel: 1 Sekunde
  • 10 Gegenstände: 10 Sekunden
  • 100 Gegenstände: 100 Sekunden

Diesmal erhöht sich die Anzahl der Items um den Faktor 10 und damit auch die Zeit. n = 10 und so ist der Skalierungsfaktor von O (n) 10.

O (1): bekannt als Konstante Komplexität

  • 1 Artikel: 1 Sekunde
  • 10 Artikel: 1 Sekunde
  • 100 Artikel: 1 Sekunde

Die Anzahl der Items nimmt immer noch um den Faktor 10 zu, aber der Skalierungsfaktor von O (1) ist immer 1.

O (log n): bekannt als Logarithmische Komplexität

  • 1 Artikel: 1 Sekunde
  • 10 Gegenstände: 2 Sekunden
  • 100 Gegenstände: 3 Sekunden
  • 1000 Gegenstände: 4 Sekunden
  • 10000 Artikel: 5 Sekunden

Die Anzahl der Berechnungen wird nur um einen Logarithmus des Eingabewerts erhöht. In diesem Fall wird unter der Annahme, dass jede Berechnung 1 Sekunde dauert, das Protokoll der Eingabe verwendet n ist die benötigte Zeit also log n.

Das ist das Wesentliche davon. Sie reduzieren die Mathematik, so dass es nicht genau n sein kann2 oder was auch immer sie sagen, aber das wird der dominierende Faktor in der Skalierung sein.


662
2018-01-28 11:28



Big-O-Notation (auch "asymptotische Wachstum" -Notation genannt) ist Welche Funktionen "sehen" aus, wenn Sie konstante Faktoren und Dinge in der Nähe des Ursprungs ignorieren. Wir sprechen darüber wie Ding skaliert.


Grundlagen

für "ausreichend" große Eingänge ...

  • f(x) ∈ O(upperbound) meint f "wächst nicht schneller als" upperbound
  • f(x) ∈ Ɵ(justlikethis) bedeuten f "wächst genau wie" justlikethis
  • f(x) ∈ Ω(lowerbound) meint f "wächst nicht langsamer als" lowerbound

Die Groß-O-Notation interessiert sich nicht für konstante Faktoren: die Funktion 9x² soll "genau so wachsen" 10x². Weder macht Big-O asymptotisch Notation kümmert sich um nicht asymptotisch stuff ("Zeug in der Nähe des Ursprungs" oder "was passiert, wenn die Problemgröße klein ist"): die Funktion 10x² soll "genau so wachsen" 10x² - x + 2.

Warum möchten Sie die kleineren Teile der Gleichung ignorieren? Weil sie durch die großen Teile der Gleichung völlig in den Schatten gestellt werden, während Sie immer größere Skalen betrachten; ihr Beitrag wird winzig und irrelevant. (Siehe Beispielabschnitt.)

Anders gesagt, es dreht sich alles um die Verhältnis wie du in die Unendlichkeit gehst. Wenn Sie die tatsächliche Zeit durch die teilen O(...), erhalten Sie einen konstanten Faktor in der Grenze der großen Eingänge. Intuitiv macht das Sinn: Funktionen "skalieren" sich gegenseitig, wenn man die eine multiplizieren kann, um die andere zu bekommen. Das heißt, wenn wir sagen ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... das bedeutet, dass für "groß genug" Problemgrößen N (Wenn wir Dinge in der Nähe des Ursprungs ignorieren), gibt es eine Konstante (z. B. 2,5, vollständig erfunden), so dass:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Es gibt viele Möglichkeiten der Konstanten; oft ist die "beste" Wahl bekannt als der "konstante Faktor" des Algorithmus ... aber wir ignorieren sie oft, als ob wir nicht-größte Terme ignorieren würden (siehe Abschnitt Konstante Faktoren für warum sie normalerweise keine Rolle spielen). Sie können die obige Gleichung auch als gebunden betrachten, sagen "Im schlimmsten Fall wird die Zeit niemals schlechter als ungefähr N*log(N)innerhalb eines Faktors von 2,5 (ein konstanter Faktor, um den es uns nicht kümmert)".

Im Algemeinen, O(...) ist am nützlichsten, weil uns oft das Worst-Case-Verhalten am Herzen liegt. Ob f(x) stellt etwas "schlechtes" wie Prozessor oder Speichernutzung dar, dannf(x) ∈ O(upperbound)" meint "upperbound ist das Worst-Case-Szenario der Prozessor- / Speicherbelegung ".


Anwendungen

Als rein mathematisches Konstrukt ist die Groß-O-Notation nicht darauf beschränkt, über Verarbeitungszeit und Speicher zu sprechen. Sie können es verwenden, um die Asymptotik von allem zu diskutieren, wo Skalierung sinnvoll ist, wie zum Beispiel:

  • die Anzahl der möglichen Handshakes unter N Leute auf einer Party (Ɵ(N²)speziell N(N-1)/2, aber was zählt ist, dass es "skaliert" )
  • probabilistisch erwartete Anzahl von Menschen, die etwas virales Marketing als eine Funktion der Zeit gesehen haben
  • wie die Latenz der Website mit der Anzahl der Verarbeitungseinheiten in einer CPU oder einem GPU oder Computercluster skaliert
  • Wie die Wärmeabgabe auf die CPU skaliert als Funktion der Anzahl der Transistoren, der Spannung usw.
  • Wie viel Zeit benötigt ein Algorithmus als Funktion der Eingabegröße?
  • Wie viel Platz benötigt ein Algorithmus als Funktion der Eingabegröße?

Beispiel

Für das obige Handshake-Beispiel schüttelt jeder in einem Raum die Hand aller anderen. In diesem Beispiel #handshakes ∈ Ɵ(N²). Warum?

Backup ein wenig: die Anzahl der Handshakes ist genau n-wählen-2 oder N*(N-1)/2 (jeder von N Leuten schüttelt die Hände von N-1 anderen Leuten, aber dieses Doppel-zählt Handshakes so durch 2 teilen):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Für sehr viele Menschen jedoch der lineare Ausdruck N ist winzig und trägt effektiv 0 zum Verhältnis bei (in der Grafik: der Anteil leerer Kästchen auf der Diagonalen über den Kästchen wird kleiner, wenn die Anzahl der Teilnehmer größer wird). Daher ist das Skalierungsverhalten order N²oder die Anzahl der Handshakes "wächst wie N²".

#handshakes(N)
────────────── ≈ 1/2
     N²

Es ist, als ob die leeren Kästchen auf der Diagonale des Diagramms (N * (N - 1) / 2 Häkchen) nicht einmal da wären (N2 Häkchen asymptotisch).

(vorübergehende Exkurs von "plain English" :) Wenn Sie das selbst beweisen wollten, könnten Sie eine einfache Algebra über das Verhältnis durchführen, um es in mehrere Begriffe aufzuteilen (limbedeutet "im Grenzbereich betrachtet", ignoriere es einfach, wenn du es nicht gesehen hast, es ist nur Notation für "und N ist wirklich sehr groß"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: Die Anzahl der Handshakes sieht für große Werte wie 'x² so aus, dass wenn wir das Verhältnis # handshakes / x² aufschreiben würden, die Tatsache, dass wir nicht brauchen genau x²-Handshakes würden für eine beliebig lange Zeit nicht einmal in der Dezimalzahl erscheinen.

z.B. für x = 1million, Verhältnis # handshakes / x²: 0,499999 ...


Gebäudeintuition

So können wir Aussagen machen wie ...

"Für groß genug Inputsize = N, egal was der konstante Faktor ist, wenn ich doppelt die Eingabegröße


362
2017-07-08 04:46



EDIT: Schnelle Notiz, das ist fast sicher verwirrend Große O-Notation (das ist eine obere Grenze) mit Theta-Notation (die sowohl eine obere und untere Grenze ist). Meiner Erfahrung nach ist dies typisch für Diskussionen in nicht-akademischen Umgebungen. Entschuldigung für jede mögliche Verwirrung.

In einem Satz: Wie lange dauert es, bis die Arbeit abgeschlossen ist?

Offensichtlich benutzt man nur "size" als Eingabe und "time take" als Ausgabe - das gleiche gilt, wenn man über die Speichernutzung usw. sprechen möchte.

Hier ist ein Beispiel, wo wir N T-Shirts haben, die wir trocknen wollen. Gut annehmen es ist unglaublich schnell, sie in die Trockenposition zu bringen (d. h. die menschliche Interaktion ist vernachlässigbar). Das ist im echten Leben natürlich nicht der Fall ...

  • Mit einer Wäscheleine im Freien: Wenn Sie einen unendlich großen Garten haben, trocknet das Waschen in O (1) Zeit. Wie viel Sie davon haben, es wird die gleiche Sonne und frische Luft bekommen, so dass die Größe die Trocknungszeit nicht beeinflusst.

  • Verwenden Sie einen Wäschetrockner: Sie legen 10 Shirts in jede Ladung, und dann sind sie eine Stunde später fertig. (Ignoriere die tatsächlichen Zahlen hier - sie sind irrelevant.) Also trocknet 50 Shirts Über 5 mal so lang wie 10 Hemden trocknen.

  • Alles in einen Lümmelschrank stellen: Wenn wir alles in einen großen Stapel legen und es nur der allgemeinen Wärme überlassen, wird es lange dauern, bis die mittleren Hemden trocken sind. Ich würde nicht gerne im Detail raten, aber ich vermute, das ist mindestens O (N ^ 2) - wenn Sie die Waschladung erhöhen, erhöht sich die Trocknungszeit schneller.

Ein wichtiger Aspekt der "großen O" -Notation ist das nicht Sagen Sie, welcher Algorithmus für eine gegebene Größe schneller ist. Nehmen Sie eine Hashtabelle (Zeichenfolgenschlüssel, Ganzzahlwert) im Vergleich zu einem Array von Paaren (Zeichenfolge, Ganzzahl). Ist es schneller, einen Schlüssel in der Hashtabelle oder ein Element im Array basierend auf einer Zeichenfolge zu finden? (zB für das Array, "finde das erste Element, wo der Stringteil mit dem gegebenen Schlüssel übereinstimmt.") Hashtables werden im Allgemeinen amortisiert (~ = "im Durchschnitt") O (1) - sobald sie eingerichtet sind, sollte es etwa dauern die gleiche Zeit, um einen Eintrag in einer 100-Eintragstabelle wie in einer 1.000.000 Eintragstabelle zu finden. Das Finden eines Elements in einem Array (basierend auf Inhalt statt Index) ist linear, d. H. O (N) - im Durchschnitt müssen Sie sich die Hälfte der Einträge ansehen.

Macht dies eine Hashtabelle schneller als ein Array für Suchvorgänge? Nicht unbedingt. Wenn Sie eine sehr kleine Sammlung von Einträgen haben, ist ein Array vielleicht schneller - Sie können vielleicht alle Strings in der Zeit überprüfen, die es braucht, um nur den Hashcode des gesuchten zu berechnen. Wenn der Datensatz jedoch größer wird, wird die Hashtable schließlich das Array schlagen.


237
2018-01-28 11:16



Big O beschreibt eine Obergrenze für das Wachstumsverhalten einer Funktion, zum Beispiel die Laufzeit eines Programms, wenn Eingaben groß werden.

Beispiele:

  • O (n): Wenn ich die Eingabegröße verdopple verdoppelt sich die Laufzeit

  • Auf2): Wenn sich die Eingabegröße verdoppelt, vervierfacht sich die Laufzeit

  • O (log n): Wenn sich die Eingabegröße verdoppelt, erhöht sich die Laufzeit um eins

  • O (2n): Wenn sich die Eingabegröße um eins erhöht, verdoppelt sich die Laufzeit

Die Eingabegröße ist normalerweise der Platz in Bits, die benötigt werden, um die Eingabe darzustellen.


120
2018-01-28 11:23



Die große O-Notation wird von Programmierern am häufigsten als ein ungefähres Maß dafür verwendet, wie lange eine Berechnung (Algorithmus) dauert, um sie als eine Funktion der Größe des Eingabesatzes auszudrücken.

Big O ist nützlich, um zu vergleichen, wie gut zwei Algorithmen skaliert werden, wenn die Anzahl der Eingaben erhöht wird.

Etwas präziser Große O-Notation wird verwendet, um das asymptotische Verhalten einer Funktion auszudrücken. Das bedeutet, wie sich die Funktion verhält, wenn sie sich der Unendlichkeit nähert.

In vielen Fällen fällt das "O" eines Algorithmus in einen der folgenden Fälle:

  • O (1) - Die Zeit bis zum Abschluss ist unabhängig von der Größe des Eingabesatzes gleich. Ein Beispiel ist der Zugriff auf ein Array-Element nach Index.
  • O (Log N) - Die Zeit bis zur Fertigstellung steigt ungefähr in Übereinstimmung mit log2 (n). Zum Beispiel dauert 1024 Elemente ungefähr doppelt so lang wie 32 Elemente, da Log2 (1024) = 10 und Log2 (32) = 5 ist. Ein Beispiel ist das Finden eines Elements in einem binärer Suchbaum (BST).
  • AUF) - Zeit zum Abschluss, die linear mit der Größe des Eingabesatzes skaliert wird. Mit anderen Worten, wenn Sie die Anzahl der Elemente im Eingabe-Set verdoppeln, dauert der Algorithmus etwa doppelt so lang. Ein Beispiel zählt die Anzahl der Elemente in einer verknüpften Liste.
  • O (N Log N) - Die Zeit bis zum Abschluss erhöht sich um die Anzahl der Elemente multipliziert mit dem Ergebnis von Log2 (N). Ein Beispiel dafür ist Haufen sortieren und schnelle Sorte.
  • O (N ^ 2) - Die Zeit bis zur Fertigstellung entspricht ungefähr dem Quadrat der Anzahl der Objekte. Ein Beispiel dafür ist Blasensortieren.
  • AUF!) - Die Zeit bis zum Abschluss ist die Fakultät der eingegebenen Menge. Ein Beispiel dafür ist die fahrendes Verkäuferproblem Brute-Force-Lösung.

Big O ignoriert Faktoren, die nicht sinnvoll zur Wachstumskurve einer Funktion beitragen, da die Eingabegröße in Richtung Unendlichkeit zunimmt. Dies bedeutet, dass Konstanten, die zu der Funktion hinzugefügt oder mit ihr multipliziert werden, einfach ignoriert werden.


97
2017-09-05 16:31



Big O ist nur eine Möglichkeit, sich auf eine gebräuchliche Art und Weise "auszudrücken": "Wie viel Zeit / Raum braucht es, um meinen Code auszuführen?".

Sie können oft O (n), O (n2), O (nlogn) und so weiter, all dies sind nur Wege zu zeigen; Wie ändert sich ein Algorithmus?

O (n) bedeutet Big O ist n, und jetzt könntest du denken: "Was ist n !?" Nun "n" ist die Anzahl der Elemente. Imaging, wenn Sie nach einem Objekt in einem Array suchen möchten. Sie müssten auf Jedes Element und als "Sind Sie das richtige Element / Element?" Im schlimmsten Fall befindet sich das Item auf dem letzten Index, was bedeutet, dass es genauso lange gedauert hat, wie es Items in der Liste gibt. Um also generisch zu sein, sagen wir "Oh hey, n ist eine faire gegebene Menge an Werten!" .

Dann könntest du verstehen, was "n2"bedeutet, aber um noch spezifischer zu sein, spielen Sie mit dem Gedanken, dass Sie einen einfachen, den einfachsten Sortieralgorithmus haben; bubblesort. Dieser Algorithmus muss für jedes Element die gesamte Liste durchsehen.

Meine Liste

  1. 1
  2. 6
  3. 3

Der Fluss hier wäre:

  • Vergleichen Sie 1 und 6, was am größten ist? Ok 6 ist in der richtigen Position und bewegt sich vorwärts!
  • Vergleichen Sie 6 und 3, oh, 3 ist weniger! Lass uns das verschieben, Ok, die Liste hat sich geändert, wir müssen jetzt von vorne anfangen!

Das ist On2 weil Sie alle Elemente in der Liste betrachten müssen, gibt es "n" Elemente. Für jeden Gegenstand schaust du noch einmal alle Gegenstände an, zum Vergleichen ist das auch "n", also suchst du für jeden Gegenstand "n" mal mit n * n = n2

Ich hoffe, das ist so einfach wie du es willst.

Aber denken Sie daran, Big O ist nur ein Weg, sich in der Art von Zeit und Raum auszuleben.


77
2018-01-28 11:14



Big O beschreibt die fundamentale Skalierung eines Algorithmus.

Es gibt viele Informationen, die Big O Ihnen nicht über einen bestimmten Algorithmus erzählt. Es schneidet bis auf die Knochen und gibt nur Informationen über die Skalierungsart eines Algorithmus, insbesondere wie die Ressourcennutzung (Denkzeit oder Speicher) eines Algorithmus als Antwort auf die "Eingabegröße" skaliert.

Betrachten Sie den Unterschied zwischen einer Dampfmaschine und einer Rakete. Sie sind nicht nur verschiedene Varianten der gleichen Sache (wie gesagt, ein Prius Motor vs. Lamborghini-Motor), aber sie sind dramatisch verschiedene Arten von Antriebssystemen, in ihrem Kern. Eine Dampfmaschine kann schneller sein als eine Spielzeugrakete, aber kein Dampfkolbenmotor wird in der Lage sein, die Geschwindigkeiten einer orbitalen Trägerrakete zu erreichen. Dies liegt daran, dass diese Systeme unterschiedliche Skalierungseigenschaften in Bezug auf das Verhältnis von benötigtem Brennstoff ("Ressourcennutzung") zum Erreichen einer gegebenen Geschwindigkeit ("Eingabegröße") aufweisen.

Warum ist das so wichtig? Weil Software sich mit Problemen befasst, die sich in der Größe um Faktoren bis zu einer Billion unterscheiden können. Bedenken Sie das für einen Moment. Das Verhältnis zwischen der Geschwindigkeit, die notwendig ist, um zum Mond zu reisen, und der menschlichen Gehgeschwindigkeit ist weniger als 10.000: 1, und das ist im Vergleich zu dem Bereich, in den die Eingabegrößen der Software hineinpassen, absolut winzig. Und da Software möglicherweise einem astronomischen Bereich in den Eingabegrößen gegenübersteht, gibt es das Potenzial für die große O-Komplexität eines Algorithmus, es ist die grundlegende Skalierungsnatur, alle Implementierungsdetails zu übertrumpfen.

Betrachten Sie das Beispiel der kanonischen Sortierung. Blasensortierung ist O (n2) während merge-sort ist O (n log n). Angenommen, Sie haben zwei Sortieranwendungen, Anwendung A, die bubble-sort verwendet, und Anwendung B, die merge-sort verwendet. Bei Eingabegrößen von etwa 30 Elementen ist Anwendung A 1000x schneller als Anwendung B beim Sortieren. Wenn Sie nie mehr als 30 Elemente sortieren müssen, ist es offensichtlich, dass Sie Anwendung A bevorzugen sollten, da sie bei diesen Eingabegrößen viel schneller ist. Wenn Sie jedoch feststellen, dass Sie möglicherweise zehn Millionen Elemente sortieren müssen, dann würden Sie erwarten, dass Anwendung B in diesem Fall tatsächlich tausendmal schneller ist als Anwendung A, was allein auf die Skalierbarkeit jedes Algorithmus zurückzuführen ist.


52
2018-01-28 13:12