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

Kurz gesagt, dies verwechselt mit ziemlicher Sicherheit die Big O-Notation (eine Obergrenze) mit der Theta-Notation "Θ" (eine zweiseitige Grenze). Nach meiner Erfahrung ist dies tatsächlich typisch für Diskussionen in nicht-akademischen Umgebungen. Entschuldigung für etwaige Verwirrung.

Die Komplexität von Big O kann mit diesem Diagramm visualisiert werden:

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

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

Dieser Satz enthält einige wichtige und bewusst ausgewählte Wörter:

• relativ: Sie können nur Äpfel mit Äpfeln vergleichen. Sie können einen Algorithmus zur arithmetischen Multiplikation nicht mit einem Algorithmus vergleichen, der eine Liste von Ganzzahlen sortiert. Ein Vergleich zweier Algorithmen für arithmetische Operationen (eine Multiplikation, eine Addition) zeigt jedoch etwas Sinnvolles.
• 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. Beispielsweise werden Sortieralgorithmen typischerweise basierend auf Vergleichsoperationen verglichen (Vergleichen von zwei Knoten, um ihre relative Reihenfolge zu bestimmen). Dies setzt voraus, dass ein Vergleich teuer ist. Aber was ist, wenn der Vergleich billig ist, aber das Tauschen teuer ist? 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? Die Komplexität ist in diesem Fall ein relatives Maß für etwas anderes.

Komm zurück und lies das Obige noch einmal, wenn du den Rest gelesen hast.

Das beste Beispiel für Big-O, das ich mir vorstellen kann, ist das Rechnen. Nehmen Sie zwei Zahlen (123456 und 789012). Die grundlegenden arithmetischen Operationen, die wir in der Schule gelernt haben, waren:

• Zusatz;
• Subtraktion;
• Multiplikation; und
• Teilung.

Jedes davon ist eine Operation oder ein Problem. Eine Methode zur Lösung dieser Probleme wird als Algorithmus bezeichnet .

Der Zusatz ist der einfachste. Sie richten die Zahlen (rechts) aus und fügen die Ziffern in eine Spalte ein, in der die letzte Zahl dieser Addition im Ergebnis angegeben ist. Der Zehnerteil dieser Zahl wird in die nächste Spalte übertragen.

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

Sehen Sie das Muster? Die Komplexität (die Anzahl der Operationen) ist direkt proportional zur Anzahl der Stellen n in der größeren Anzahl. Wir nennen dies O (n) oder lineare Komplexität .

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

Multiplikation ist anders. Sie richten die Zahlen aus, nehmen die erste Ziffer in der unteren Zahl und multiplizieren sie nacheinander mit jeder Ziffer in der oberen Zahl usw. durch jede Ziffer. Um unsere zwei 6-stelligen Zahlen zu multiplizieren, müssen wir 36 Multiplikationen durchführen. Möglicherweise müssen wir bis zu 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 Zahlen mit einer Million Ziffern müssen wir eine Billion (10 ¹² ) Multiplikationen und zwei Millionen Additionen durchführen.

Da der Algorithmus mit n- Quadrat skaliert , ist dies O (n ² ) oder quadratische Komplexität . Dies ist ein guter Zeitpunkt, um ein weiteres wichtiges Konzept vorzustellen:

Wir kümmern uns nur um den größten Teil der Komplexität.

Der Kluge hat vielleicht erkannt, dass wir die Anzahl der Operationen wie folgt ausdrücken können: n ² + 2n. Wie Sie jedoch aus unserem Beispiel mit zwei zweistelligen Ziffern pro Stück gesehen haben, wird der zweite Term (2n) unbedeutend (er macht zu diesem Zeitpunkt 0,0002% der gesamten Operationen aus).

Man kann feststellen, dass wir hier das Worst-Case-Szenario angenommen haben. Wenn beim Multiplizieren von 6-stelligen Zahlen eine von ihnen 4-stellig und die andere 6-stellig ist, haben wir nur 24 Multiplikationen. Dennoch berechnen wir das Worst-Case-Szenario für dieses 'n', dh wenn beide 6-stellige Zahlen sind. Daher handelt es sich bei der Big-O-Notation um das Worst-Case-Szenario eines Algorithmus.

Das Telefonbuch

Das nächstbeste Beispiel, an das ich denken kann, ist das Telefonbuch, das normalerweise als Weiße Seiten oder ähnliches bezeichnet wird, aber von Land zu Land unterschiedlich ist. Aber ich spreche von dem, der Menschen nach Nachnamen und dann Initialen oder Vornamen, möglicherweise Adresse und dann Telefonnummern auflistet.

Was würden Sie tun, wenn Sie 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, wenn Sie die Tatsache ignorieren, dass Sie erraten können, wie weit die S begonnen haben (nehmen wir an, Sie können nicht)?

Eine typische Implementierung könnte sein , bis in die Mitte zu öffnen, nehmen Sie die 500.000 ^th und vergleichen Sie es mit „Smith“. Wenn es zufällig "Smith, John" ist, haben wir wirklich Glück gehabt. 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. Wenn es vorher ist, teilen wir die erste Hälfte des Telefonbuchs in zwei Hälften und wiederholen. Und so weiter.

Dies wird als binäre Suche bezeichnet und wird jeden Tag bei der Programmierung verwendet, unabhängig davon, ob Sie dies realisieren oder nicht.

Wenn Sie also einen Namen in einem Telefonbuch mit einer Million Namen finden möchten, können Sie tatsächlich jeden 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 sind (höchstens) 2 Vergleiche erforderlich.
• 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-Begriffen ist dies O (log n) oder logarithmische Komplexität . Nun könnte der fragliche Logarithmus ln (Basis e), log ₁₀ , log ₂ oder eine andere Basis sein. Es spielt keine Rolle, dass es immer noch O (log n) ist, genau wie O (2n ² ) und O (100n ² ) immer noch beide O (n ² ) sind.

An dieser Stelle lohnt es sich zu erklären, dass Big O verwendet werden kann, um drei Fälle mit einem Algorithmus zu bestimmen:

• Bester Fall: Bei der Telefonbuchsuche ist der beste Fall, dass wir den Namen in einem Vergleich finden. Dies ist O (1) oder konstante Komplexität ;
• Erwarteter Fall: Wie oben erläutert, ist dies O (log n); und
• Schlimmster Fall: Dies ist auch O (log n).

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

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 Nachforschungen werden der Öffentlichkeit verweigert. Oder sind Sie? Technisch gesehen können Sie eine Nummer in einem normalen Telefonbuch nachschlagen. Wie?

Sie beginnen beim Vornamen und vergleichen die Nummer. Wenn es ein Match ist, großartig, wenn nicht, fahren Sie mit dem nächsten fort. Sie müssen dies auf diese Weise tun, da das Telefonbuch ungeordnet ist (ohnehin nach Telefonnummer).

So finden Sie einen Namen unter Angabe der Telefonnummer (Reverse Lookup):

• Bester Fall: O (1);
• Erwarteter Fall: O (n) (für 500.000); und
• Schlimmster Fall: O (n) (für 1.000.000).

Der reisende 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 durch eine Straße mit einer bestimmten Entfernung mit einer oder mehreren anderen Städten verbunden. Das Problem des Handlungsreisenden besteht darin, 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, können Sie gehen:

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

Nun, tatsächlich gibt es weniger als das, weil einige davon äquivalent sind (A → B → C und C → B → A sind äquivalent, zum Beispiel, weil sie die gleichen Straßen benutzen, nur umgekehrt).

In Wirklichkeit gibt es 3 Möglichkeiten.

• Nehmen Sie dies in 4 Städte und Sie haben (iirc) 12 Möglichkeiten.
• Mit 5 ist es 60.
• 6 wird 360.

Dies ist eine Funktion einer mathematischen Operation, die als Fakultät bezeichnet wird . Grundsätzlich:

• 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 × 10 ⁶⁴

Das Big-O des Travelling Salesman-Problems ist also O (n!) Oder faktorielle oder kombinatorische Komplexität .

Bis Sie 200 Städte erreichen, bleibt im Universum nicht mehr genügend Zeit, um das Problem mit herkömmlichen Computern zu lösen.

Etwas zum Nachdenken.

Polynomzeit

Ein weiterer Punkt, den ich kurz erwähnen wollte, ist, dass jeder Algorithmus, der eine Komplexität von O (n ^a ) hat, eine Polynomkomplexität haben soll oder in Polynomzeit lösbar ist .

O (n), O (n ² ) usw. sind alle Polynomzeiten. Einige Probleme können nicht in Polynomzeit gelöst werden. Aus diesem Grund werden auf der Welt bestimmte Dinge verwendet. Die Kryptographie mit öffentlichen Schlüsseln ist ein Paradebeispiel. Es ist rechnerisch schwierig, zwei Primfaktoren einer sehr großen Anzahl zu finden. Andernfalls könnten wir die von uns verwendeten Public-Key-Systeme nicht verwenden.

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

Es zeigt, wie ein Algorithmus basierend auf der Eingabegröße skaliert.

O (n ² ) : bekannt als quadratische Komplexität

• 1 Artikel: 1 Sekunde
• 10 Elemente: 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 ² . Grundsätzlich ist n = 10 und so ergibt O (n ² ) den Skalierungsfaktor n ^2, der 10 ^{2 ist} .

O (n) : bekannt als lineare Komplexität

• 1 Artikel: 1 Sekunde
• 10 Elemente: 10 Sekunden
• 100 Artikel: 100 Sekunden

Diesmal erhöht sich die Anzahl der Elemente um den Faktor 10, ebenso wie die Zeit. n = 10 und somit beträgt 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 Elemente erhöht sich immer noch um den Faktor 10, aber der Skalierungsfaktor von O (1) ist immer 1.

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

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

Die Anzahl der Berechnungen wird nur durch ein Protokoll des Eingabewerts erhöht. Unter der Annahme, dass jede Berechnung 1 Sekunde dauert, ist in diesem Fall das Protokoll der Eingabe ndie erforderliche Zeit log n.

Das ist der Kern davon. Sie reduzieren die Mathematik, so dass es möglicherweise nicht genau n ^{2 ist} oder was auch immer sie sagen, aber das wird der dominierende Faktor bei der Skalierung sein.

Mit der Big-O-Notation (auch als "asymptotisches Wachstum" bezeichnet) sehen Funktionen "aus", wenn Sie konstante Faktoren und Dinge in der Nähe des Ursprungs ignorieren . Wir verwenden es, um darüber zu sprechen, wie sich die Dinge skalieren lassen .

Grundlagen

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

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

Die Big-O-Notation kümmert sich nicht um konstante Faktoren: Die Funktion 9x²soll "genau so wachsen wie" 10x². Die asymptotische Notation von big-O kümmert sich auch nicht um nicht asymptotische Dinge ("Dinge 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 sollten Sie die kleineren Teile der Gleichung ignorieren wollen? Weil sie durch die großen Teile der Gleichung völlig in den Schatten gestellt werden, wenn Sie immer größere Maßstäbe betrachten; ihr Beitrag wird in den Schatten gestellt und irrelevant. (Siehe Beispielabschnitt.)

Anders ausgedrückt, es geht nur um das Verhältnis, wenn Sie ins Unendliche gehen. Wenn Sie die tatsächlich benötigte Zeit durch die dividieren O(...), erhalten Sie einen konstanten Faktor für die Grenze großer Eingaben. Intuitiv macht dies Sinn: Funktionen "skalieren wie einander", wenn Sie eine multiplizieren können, um die andere zu erhalten. Dann sagen wir ...

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

... dies bedeutet, dass für "groß genug" Problemgrößen N (wenn wir Dinge in der Nähe des Ursprungs ignorieren) eine Konstante existiert (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 als "konstanter Faktor" des Algorithmus bekannt ... aber wir ignorieren sie oft so, als würden wir nicht größte Begriffe ignorieren (siehe Abschnitt Konstante Faktoren, warum sie normalerweise keine Rolle spielen). Sie können sich die obige Gleichung auch als Grenze vorstellen und sagen: " Im schlimmsten Fall wird die Zeit, die benötigt wird, niemals schlechter als ungefähr sein N*log(N), innerhalb eines Faktors von 2,5 (ein konstanter Faktor, den wir nicht besonders interessieren). " .

Im Allgemeinen O(...)ist dies das nützlichste, da wir uns häufig um das Worst-Case-Verhalten kümmern. Wenn es sich f(x)um etwas "Schlechtes" wie den Prozessor oder die Speichernutzung handelt, f(x) ∈ O(upperbound)bedeutet "" " upperbounddas Worst-Case-Szenario der Prozessor- / Speichernutzung".

Anwendungen

Als rein mathematisches Konstrukt beschränkt sich die Big-O-Notation nicht darauf, ü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 möglicher Handshakes unter NLeuten auf einer Party ( Ɵ(N²)insbesondere N(N-1)/2, aber was zählt, ist, dass es "skaliert wie" N²)
• Wahrscheinlichkeitlich erwartete Anzahl von Menschen, die virales Marketing als Funktion der Zeit gesehen haben
• Wie die Website-Latenz mit der Anzahl der Verarbeitungseinheiten in einer CPU, GPU oder einem Computercluster skaliert
• Wie skaliert die Wärmeabgabe auf CPU-Chips in Abhängigkeit von Transistoranzahl, Spannung usw.
• Wie viel Zeit ein Algorithmus benötigt, um in Abhängigkeit von der Eingabegröße ausgeführt zu werden
• Wie viel Speicherplatz ein Algorithmus benötigt, um in Abhängigkeit von der Eingabegröße ausgeführt zu werden

Beispiel

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

Sichern Sie ein bisschen: Die Anzahl der Handshakes ist genau n-select-2 oder N*(N-1)/2(jede von N Personen schüttelt die Hände von N-1 anderen Personen, aber diese Handshakes mit doppelter Zählung werden durch 2 geteilt):

Bei einer sehr großen Anzahl von Personen ist der lineare Term Njedoch in den Schatten gestellt und trägt effektiv 0 zum Verhältnis bei (in der Tabelle: Der Anteil der leeren Kästchen in der Diagonale an der Gesamtzahl der 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 in der Diagonale des Diagramms (N * (N-1) / 2 Häkchen) nicht einmal vorhanden wären (N ² Häkchen asymptotisch).

(vorübergehender Exkurs von "normalem Englisch" :) Wenn Sie sich dies selbst beweisen möchten, können Sie eine einfache Algebra für das Verhältnis durchführen, um es in mehrere Begriffe aufzuteilen ( limbedeutet "im Grenzbereich von" berücksichtigt ", ignorieren Sie es einfach, wenn Sie dies tun) habe es nicht gesehen, es ist nur eine Notation für "und N ist wirklich sehr, 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 bei großen Werten so aus wie x², dass, wenn wir das Verhältnis # Handshakes / x² aufschreiben würden, die Tatsache, dass wir nicht genau x² Handshakes benötigen , nicht einmal auftauchen würde in der Dezimalstelle für eine beliebig große Zeit.

zB für x = 1 Million, Verhältnis # Handshakes / x²: 0,499999 ...

Intuition aufbauen

Dies lässt uns Aussagen machen wie ...

„Für groß genug inputsize = N, egal , was der konstante Faktor ist, wenn ich das Doppelte der Eingangsgröße ...

• ... Ich verdopple die Zeit, die ein O (N) -Algorithmus ("lineare Zeit") benötigt. "

  N → (2N) = 2 ( N )

• ... Ich habe die Zeit, die ein O (N²) -Algorithmus ("quadratische Zeit") benötigt, doppelt quadriert (vervierfacht). " (ZB ein 100x so großes Problem dauert 100² = 10000x so lange ... möglicherweise nicht nachhaltig)

  N² → (2N )² = 4 ( N² )

• ... Ich habe die Zeit, die ein O (N³) -Algorithmus ("kubische Zeit") benötigt, doppelt gewürfelt (Oktupel). " (ZB ein 100x so großes Problem dauert 100³ = 1000000x so lange ... sehr unhaltbar)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... Ich addiere einen festen Betrag zu der Zeit, die ein O (log (N)) ("logarithmische Zeit") Algorithmus benötigt. " (Billig!)

  c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (fester Betrag) + ( c log (N) )

• ... Ich ändere nicht die Zeit, die ein O (1) -Algorithmus ("konstante Zeit") benötigt. " (Am billigsten!)

  c * 1 → c * 1

• ... Ich "(im Grunde) verdopple" die Zeit, die ein O (N log (N)) - Algorithmus benötigt. " (Ziemlich häufig)

  Es ist kleiner als O (N ^1.000001 ), was Sie möglicherweise als linear bezeichnen ^möchten

• ... Ich erhöhe auf lächerliche Weise die Zeit, die ein O (2 ^N ) -Algorithmus ("Exponentialzeit") benötigt. " (Sie würden die Zeit verdoppeln (oder verdreifachen usw.), indem Sie das Problem nur um eine einzelne Einheit erhöhen.)

  2 ^N → 2 ^2N = (4 ^N ) ............ anders ausgedrückt ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N.

[Für Mathematiker können Sie mit der Maus über die Spoiler fahren, um kleinere Nebenbemerkungen zu erhalten.]

(mit Gutschrift an https://stackoverflow.com/a/487292/711085 )

(Technisch gesehen könnte der konstante Faktor in einigen esoterischeren Beispielen eine Rolle spielen, aber ich habe die obigen Dinge (z. B. in log (N)) so formuliert, dass dies nicht der Fall ist.)

Dies sind die Brot-und-Butter-Wachstumsordnungen, die Programmierer und angewandte Informatiker als Bezugspunkte verwenden. Sie sehen diese die ganze Zeit. (Während Sie also technisch denken könnten: "Durch Verdoppeln der Eingabe wird ein O (√N) -Algorithmus 1,414-mal langsamer", ist es besser, sich das als "dies ist schlechter als logarithmisch, aber besser als linear" vorzustellen.)

Konstante Faktoren

Normalerweise ist es uns egal, welche spezifischen konstanten Faktoren vorliegen, da sie die Art und Weise, wie die Funktion wächst, nicht beeinflussen. Zum Beispiel kann es einige O(N)Zeit dauern, bis zwei Algorithmen abgeschlossen sind, aber einer kann doppelt so langsam sein wie der andere. Wir kümmern uns normalerweise nicht zu sehr darum, es sei denn, der Faktor ist sehr groß, da die Optimierung ein heikles Geschäft ist ( Wann ist die Optimierung verfrüht? ). Auch die bloße Auswahl eines Algorithmus mit einem besseren Big-O verbessert die Leistung häufig um Größenordnungen.

Einige asymptotisch überlegene Algorithmen (z. B. eine nicht vergleichende O(N log(log(N)))Sortierung) können einen so großen konstanten Faktor (z. B. 100000*N log(log(N))) oder einen relativ großen Overhead wie O(N log(log(N)))bei einem versteckten haben + 100*N, dass sie sich selbst bei "Big Data" selten lohnen.

Warum O (N) manchmal das Beste ist, was Sie tun können, dh warum wir Datenstrukturen benötigen

O(N)Algorithmen sind in gewissem Sinne die "besten" Algorithmen, wenn Sie alle Ihre Daten lesen müssen. Das Lesen einer Reihe von Daten ist eine O(N)Operation. Das Laden in den Speicher erfolgt normalerweise O(N)(oder schneller, wenn Sie Hardware-Unterstützung haben, oder überhaupt keine Zeit, wenn Sie die Daten bereits gelesen haben). Wenn Sie jedoch jedes Datenelement (oder sogar jedes andere Datenelement) berühren oder sogar betrachten , benötigt Ihr Algorithmus O(N)Zeit, um dieses Suchen durchzuführen. Unabhängig davon, wie lange Ihr tatsächlicher Algorithmus dauert, wird dies zumindest O(N)darauf zurückzuführen sein, dass er diese Zeit damit verbracht hat, alle Daten zu untersuchen.

Gleiches gilt für das Schreiben . Alle Algorithmen, die N Dinge ausdrucken, benötigen N Zeit, da die Ausgabe mindestens so lang ist (z. B. das Ausdrucken aller Permutationen (Möglichkeiten zum Neuanordnen) eines Satzes von N Spielkarten ist faktoriell :) O(N!).

Dies motiviert die Verwendung von Datenstrukturen : Eine Datenstruktur erfordert das einmalige Lesen der Daten (normalerweise O(N)Zeit) sowie eine beliebige Menge an Vorverarbeitung (z. B. O(N)oder O(N log(N))oder O(N²)), die wir klein halten möchten. Danach dauert das Ändern der Datenstruktur (Einfügen / Löschen / usw.) und das Abfragen der Daten sehr wenig Zeit, wie z. B. O(1)oder O(log(N)). Sie stellen dann eine große Anzahl von Abfragen! Je mehr Arbeit Sie im Voraus erledigen möchten, desto weniger Arbeit müssen Sie im Allgemeinen später erledigen.

Angenommen, Sie hatten die Längen- und Breitengradkoordinaten von Millionen von Straßensegmenten und wollten alle Straßenkreuzungen finden.

• Naive Methode: Wenn Sie die Koordinaten einer Straßenkreuzung hätten und nahe gelegene Straßen untersuchen möchten, müssten Sie jedes Mal die Millionen von Segmenten durchgehen und jedes auf Nachbarschaft prüfen.
• Wenn Sie dies nur einmal tun müssten, wäre es kein Problem, die naive O(N)Arbeitsweise nur einmal ausführen zu müssen, aber wenn Sie dies viele Male tun möchten (in diesem Fall Neinmal für jedes Segment), wir Würd zu tun haben , O(N²)arbeiten oder 1000000² = 1000000000000 Operationen. Nicht gut (ein moderner Computer kann ungefähr eine Milliarde Operationen pro Sekunde ausführen).
• Wenn wir eine einfache Struktur verwenden, die als Hash-Tabelle bezeichnet wird (eine Instant-Speed-Lookup-Tabelle, auch als Hashmap oder Wörterbuch bezeichnet), zahlen wir geringe Kosten, indem wir alles O(N)rechtzeitig vorverarbeiten . Danach dauert es im Durchschnitt nur noch konstante Zeit, um etwas anhand seines Schlüssels nachzuschlagen (in diesem Fall sind unsere Schlüssel die Längen- und Breitengradkoordinaten, die zu einem Gitter gerundet sind; wir suchen die benachbarten Gitterräume, von denen es nur 9 gibt, was a ist Konstante).
• Unsere Aufgabe ging von einem nicht realisierbaren O(N²)zu einem überschaubaren über O(N), und wir mussten nur geringe Kosten für die Erstellung eines Hash-Tisches bezahlen.
• Analogie : Die Analogie in diesem speziellen Fall ist ein Puzzle: Wir haben eine Datenstruktur erstellt, die einige Eigenschaften der Daten ausnutzt. Wenn unsere Straßensegmente wie Puzzleteile sind, gruppieren wir sie nach Farbe und Muster. Wir nutzen dies dann aus, um später keine zusätzliche Arbeit zu erledigen (indem wir Puzzleteile gleicher Farbe miteinander vergleichen, nicht mit jedem anderen Puzzleteil).

Die Moral der Geschichte: Eine Datenstruktur ermöglicht es uns, den Betrieb zu beschleunigen. Darüber hinaus können Sie mit fortschrittlichen Datenstrukturen Vorgänge auf unglaublich clevere Weise kombinieren, verzögern oder sogar ignorieren. Unterschiedliche Probleme hätten unterschiedliche Analogien, aber sie würden alle beinhalten, die Daten so zu organisieren, dass sie eine Struktur ausnutzen, die uns wichtig ist, oder die wir ihr künstlich für die Buchhaltung auferlegt haben. Wir arbeiten im Voraus (im Grunde planen und organisieren), und jetzt sind wiederholte Aufgaben viel einfacher!

Praktisches Beispiel: Visualisierung von Wachstumsordnungen beim Codieren

Die asymptotische Notation ist im Kern völlig unabhängig von der Programmierung. Die asymptotische Notation ist ein mathematischer Rahmen, um darüber nachzudenken, wie Dinge skaliert werden und in vielen verschiedenen Bereichen verwendet werden können. Das heißt ... auf diese Weise wenden Sie die asymptotische Notation auf die Codierung an.

Die Grundlagen: Immer wenn wir mit jedem Element in einer Sammlung der Größe A (z. B. einem Array, einer Menge, allen Schlüsseln einer Karte usw.) interagieren oder A-Iterationen einer Schleife ausführen, ist dies ein multiplikativer Faktor der Größe A. Warum sage ich "ein multiplikativer Faktor"? - weil Schleifen und Funktionen (fast per Definition) eine multiplikative Laufzeit haben: die Anzahl der Iterationen, die Arbeitszeit in der Schleife (oder für Funktionen: die Häufigkeit, mit der Sie die aufrufen Funktion, Zeiten Arbeit in der Funktion erledigt). (Dies gilt, wenn wir nichts Besonderes tun, z. B. Schleifen überspringen oder die Schleife vorzeitig verlassen oder den Kontrollfluss in der Funktion basierend auf Argumenten ändern, was sehr häufig vorkommt.) Hier einige Beispiele für Visualisierungstechniken mit zugehörigem Pseudocode.

(Hier stehen die xs für zeitkonstante Arbeitseinheiten, Prozessoranweisungen, Interpreter-Opcodes usw.)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Beispiel 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Beispiel 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Wenn wir etwas Kompliziertes tun, können Sie sich möglicherweise noch visuell vorstellen, was los ist:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Hier kommt es auf den kleinsten erkennbaren Umriss an, den Sie zeichnen können. ein Dreieck ist eine zweidimensionale Form (0,5 A ^ 2), genau wie ein Quadrat eine zweidimensionale Form (A ^ 2) ist; Der konstante Faktor zwei bleibt hier im asymptotischen Verhältnis zwischen den beiden, wir ignorieren ihn jedoch wie alle Faktoren ... (Es gibt einige unglückliche Nuancen bei dieser Technik, auf die ich hier nicht eingehe; sie kann Sie irreführen.)

Dies bedeutet natürlich nicht, dass Schleifen und Funktionen schlecht sind. im Gegenteil, sie sind die Bausteine ​​moderner Programmiersprachen, und wir lieben sie. Wir können jedoch sehen, dass die Art und Weise, wie wir Schleifen, Funktionen und Bedingungen zusammen mit unseren Daten (Kontrollfluss usw.) weben, die zeitliche und räumliche Nutzung unseres Programms nachahmt! Wenn die Nutzung von Zeit und Raum zu einem Problem wird, greifen wir auf Klugheit zurück und finden einen einfachen Algorithmus oder eine Datenstruktur, die wir nicht berücksichtigt haben, um die Reihenfolge des Wachstums irgendwie zu verringern. Trotzdem können diese Visualisierungstechniken (obwohl sie nicht immer funktionieren) eine naive Vermutung für eine Worst-Case-Laufzeit geben.

Folgendes können wir visuell erkennen:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Wir können dies einfach neu anordnen und sehen, dass es O (N) ist:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Oder Sie protokollieren (N) Durchläufe der Daten für die Gesamtzeit O (N * log (N)):

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Unabhängig, aber noch einmal erwähnenswert: Wenn wir einen Hash durchführen (z. B. eine Wörterbuch- / Hashtabellensuche), ist dies ein Faktor von O (1). Das geht ziemlich schnell.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

Wenn wir etwas sehr Kompliziertes tun, z. B. mit einer rekursiven Funktion oder einem Divide-and-Conquer-Algorithmus, können Sie den Master-Satz (funktioniert normalerweise) oder in lächerlichen Fällen den Akra-Bazzi-Satz (funktioniert fast immer) verwenden, den Sie nachschlagen Laufzeit Ihres Algorithmus auf Wikipedia.

Aber Programmierer denken nicht so, weil die Intuition des Algorithmus schließlich zur zweiten Natur wird. Sie werden anfangen, etwas Ineffizientes zu codieren und sofort denken: "Mache ich etwas grob Ineffizientes? ". Wenn die Antwort "Ja" lautet UND Sie vorhersehen, dass es tatsächlich wichtig ist, können Sie einen Schritt zurücktreten und sich verschiedene Tricks überlegen, um die Dinge schneller laufen zu lassen (die Antwort lautet fast immer "Verwenden Sie eine Hashtabelle", selten "Verwenden Sie einen Baum"). und sehr selten etwas etwas komplizierter).

Amortisierte und durchschnittliche Komplexität

Es gibt auch das Konzept des "amortisierten" und / oder "durchschnittlichen Falls" (beachten Sie, dass diese unterschiedlich sind).

Durchschnittlicher Fall : Dies ist nicht mehr als die Verwendung der Big-O-Notation für den erwarteten Wert einer Funktion und nicht für die Funktion selbst. Im Normalfall, in dem Sie alle Eingaben als gleich wahrscheinlich betrachten, ist der Durchschnittsfall nur der Durchschnitt der Laufzeit. Zum Beispiel mit Quicksort, obwohl der schlechteste Fall O(N^2)für einige wirklich schlechte Eingaben ist, ist der durchschnittliche Fall der übliche O(N log(N))(die wirklich schlechten Eingaben sind sehr klein, so wenige, dass wir sie im durchschnittlichen Fall nicht bemerken).

Amortisierter Worst-Case : Einige Datenstrukturen weisen möglicherweise eine große Worst-Case-Komplexität auf. Stellen Sie jedoch sicher, dass bei vielen dieser Vorgänge der durchschnittliche Arbeitsaufwand besser ist als im Worst-Case. Beispielsweise haben Sie möglicherweise eine Datenstruktur, die normalerweise eine konstante O(1)Zeit benötigt. Gelegentlich kommt es jedoch zu einem Schluckauf und O(N)es dauert einige Zeit für eine zufällige Operation, da möglicherweise eine Buchhaltung oder Müllabfuhr oder ähnliches erforderlich ist. Es verspricht Ihnen jedoch, dass es bei N nicht wieder zu Schluckauf kommt, wenn es zu Schluckauf kommt mehr Operationen. Die Worst-Case - Kosten sind nach wie vor O(N)pro Betrieb, aber die fortgeführten Anschaffungskosten über viele Läufe sind O(N)/N=O(1)pro Operation. Da die großen Operationen ausreichend selten sind, kann davon ausgegangen werden, dass sich die enorme Menge an gelegentlicher Arbeit als konstanter Faktor in den Rest der Arbeit einfügt. Wir sagen, die Arbeit wird über eine ausreichend große Anzahl von Anrufen "amortisiert", so dass sie asymptotisch verschwindet.

Die Analogie zur amortisierten Analyse:

Du fährst ein Auto. Gelegentlich müssen Sie 10 Minuten zur Tankstelle gehen und dann 1 Minute damit verbringen, den Tank mit Benzin aufzufüllen. Wenn Sie dies jedes Mal tun würden, wenn Sie mit Ihrem Auto irgendwohin fahren (10 Minuten zur Tankstelle fahren, ein paar Sekunden damit verbringen, einen Bruchteil einer Gallone aufzufüllen), wäre dies sehr ineffizient. Wenn Sie den Tank jedoch alle paar Tage auffüllen, werden die 11 Minuten Fahrt zur Tankstelle über eine ausreichend große Anzahl von Fahrten "amortisiert", sodass Sie ihn ignorieren und so tun können, als wären alle Ihre Fahrten möglicherweise 5% länger.

Vergleich zwischen durchschnittlichem und amortisiertem Worst-Case:

• Durchschnittsfall: Wir machen einige Annahmen über unsere Eingaben; dh wenn unsere Eingaben unterschiedliche Wahrscheinlichkeiten haben, haben unsere Ausgaben / Laufzeiten unterschiedliche Wahrscheinlichkeiten (von denen wir den Durchschnitt nehmen). Normalerweise gehen wir davon aus, dass unsere Eingaben alle gleich wahrscheinlich sind (einheitliche Wahrscheinlichkeit), aber wenn die realen Eingaben nicht unseren Annahmen der "durchschnittlichen Eingabe" entsprechen, sind die Berechnungen der durchschnittlichen Ausgabe / Laufzeit möglicherweise bedeutungslos. Wenn Sie jedoch gleichmäßig zufällige Eingaben erwarten, ist dies nützlich, um darüber nachzudenken!
• Amortisierter Worst-Case: Wenn Sie eine amortisierte Worst-Case-Datenstruktur verwenden, liegt die Leistung garantiert innerhalb des amortisierten Worst-Case ... schließlich (selbst wenn die Eingaben von einem bösen Dämon ausgewählt werden, der alles weiß und es versucht scheiß auf dich). Normalerweise verwenden wir dies, um Algorithmen zu analysieren, deren Leistung mit unerwartet großen Schluckauf sehr "abgehackt" sein kann, die jedoch im Laufe der Zeit genauso gut funktionieren wie andere Algorithmen. (Wenn Ihre Datenstruktur jedoch keine Obergrenzen für herausragende Arbeiten aufweist, die sie zögern möchte, könnte ein böser Angreifer Sie möglicherweise dazu zwingen, die maximale Menge an zögernder Arbeit auf einmal nachzuholen.

Wenn Sie sich jedoch einigermaßen Sorgen um einen Angreifer machen, gibt es neben Amortisation und Durchschnittsfall noch viele andere algorithmische Angriffsmethoden, über die Sie sich Sorgen machen müssen.)

Sowohl der Durchschnittsfall als auch die Amortisation sind unglaublich nützliche Werkzeuge, um über Skalierung nachzudenken und sie zu entwerfen.

(Siehe Unterschied zwischen durchschnittlicher Fall- und amortisierter Analyse, wenn Sie an diesem Unterthema interessiert sind.)

Mehrdimensionales Big-O

Meistens merken die Leute nicht, dass mehr als eine Variable am Werk ist. In einem String-Suchalgorithmus kann Ihr Algorithmus beispielsweise einige Zeit in Anspruch nehmen O([length of text] + [length of query]), dh er ist in zwei Variablen wie linear linear O(N+M). Andere naivere Algorithmen können O([length of text]*[length of query])oder sein O(N*M). Das Ignorieren mehrerer Variablen ist eines der häufigsten Probleme, die ich bei der Algorithmusanalyse sehe, und kann Sie beim Entwerfen eines Algorithmus behindern.

Die ganze Geschichte

Denken Sie daran, dass Big-O nicht die ganze Geschichte ist. Sie können einige Algorithmen drastisch beschleunigen, indem Sie Caching verwenden, sie nicht mehr im Cache speichern, Engpässe vermeiden, indem Sie mit RAM anstelle von Festplatte arbeiten, Parallelisierung verwenden oder im Voraus arbeiten. Diese Techniken sind häufig unabhängig von der Reihenfolge des Wachstums "Big-O" -Notation, obwohl Sie häufig die Anzahl der Kerne in der Big-O-Notation paralleler Algorithmen sehen.

Denken Sie auch daran, dass Sie sich aufgrund versteckter Einschränkungen Ihres Programms möglicherweise nicht wirklich für asymptotisches Verhalten interessieren. Möglicherweise arbeiten Sie mit einer begrenzten Anzahl von Werten, zum Beispiel:

• Wenn Sie etwa 5 Elemente sortieren, möchten Sie die schnelle O(N log(N))Quicksortierung nicht verwenden. Sie möchten die Einfügesortierung verwenden, die bei kleinen Eingaben eine gute Leistung erbringt. Diese Situationen treten häufig bei Divide-and-Conquer-Algorithmen auf, bei denen Sie das Problem in immer kleinere Teilprobleme aufteilen, z. B. rekursive Sortierung, schnelle Fourier-Transformationen oder Matrixmultiplikation.
• Wenn einige Werte aufgrund einer verborgenen Tatsache effektiv begrenzt sind (z. B. ist der durchschnittliche menschliche Name bei vielleicht 40 Buchstaben weich begrenzt, und das menschliche Alter ist bei etwa 150 weich begrenzt). Sie können Ihrer Eingabe auch Grenzen setzen, um Begriffe effektiv konstant zu halten.

In der Praxis kann selbst bei Algorithmen mit derselben oder einer ähnlichen asymptotischen Leistung ihr relativer Wert tatsächlich durch andere Faktoren bestimmt werden, wie z. B.: Andere Leistungsfaktoren (Quicksort und Mergesort sind beide O(N log(N)), aber Quicksort nutzt CPU-Caches); Nichterfüllungsaspekte wie einfache Implementierung; ob eine Bibliothek verfügbar ist und wie seriös und gepflegt die Bibliothek ist.

Programme laufen auch auf einem 500-MHz-Computer langsamer als auf einem 2-GHz-Computer. Wir betrachten dies nicht wirklich als Teil der Ressourcengrenzen, da wir die Skalierung in Bezug auf Maschinenressourcen (z. B. pro Taktzyklus) und nicht pro echte Sekunde betrachten. Es gibt jedoch ähnliche Dinge, die die Leistung "heimlich" beeinflussen können, z. B. ob Sie unter Emulation ausgeführt werden oder ob der Compiler den Code optimiert hat oder nicht. Dies kann dazu führen, dass einige grundlegende Operationen länger dauern (sogar relativ zueinander) oder einige Operationen asymptotisch beschleunigen oder verlangsamen (sogar relativ zueinander). Der Effekt kann zwischen verschiedenen Implementierungen und / oder Umgebungen klein oder groß sein. Wechseln Sie die Sprache oder die Maschine, um diese zusätzliche Arbeit zu erledigen? Das hängt von hundert anderen Gründen ab (Notwendigkeit, Fähigkeiten, Mitarbeiter, Produktivität der Programmierer,

Die oben genannten Probleme, wie die Auswirkung der Wahl der verwendeten Programmiersprache, werden fast nie als Teil des konstanten Faktors betrachtet (und sollten es auch nicht sein). dennoch sollte man sich ihrer bewusst sein, weil sie manchmal (wenn auch selten) Dinge beeinflussen können. Beispielsweise ist in cpython die Implementierung der systemeigenen Prioritätswarteschlange asymptotisch nicht optimal ( O(log(N))und nicht O(1)für Ihre Wahl von Einfügung oder find-min). Verwenden Sie eine andere Implementierung? Wahrscheinlich nicht, da die C-Implementierung wahrscheinlich schneller ist und es wahrscheinlich anderswo ähnliche Probleme gibt. Es gibt Kompromisse; manchmal sind sie wichtig und manchmal nicht.

( Bearbeiten : Die "einfache englische" Erklärung endet hier.)

Mathe-Nachträge

Der Vollständigkeit halber lautet die genaue Definition der Big-O-Notation wie folgt: f(x) ∈ O(g(x))bedeutet, dass "f asymptotisch durch const * g begrenzt ist": Wenn alles unter einem endlichen Wert von x ignoriert wird, existiert eine Konstante, so dass |f(x)| ≤ const * |g(x)|. (Die anderen Symbole lauten wie folgt: Genau wie OMittel ≤, ΩMittel ≥. Es gibt Kleinbuchstabenvarianten: oMittel <und ωMittel>.) f(x) ∈ Ɵ(g(x))Bedeutet beides f(x) ∈ O(g(x))und f(x) ∈ Ω(g(x))(Ober- und Untergrenze durch g): Es gibt einige Konstanten, so dass f wird immer in der "Band" zwischen const1*g(x)und liegen . (Entschuldigung, ich habe mich aus Gründen der Klarheit dafür entschieden, die Erwähnung der Absolutwertsymbole bis jetzt zu verschieben. Dies liegt insbesondere daran, dass ich in einem Informatikkontext noch nie negative Werte gesehen habe.)const2*g(x) . Es ist die stärkste asymptotische Aussage, die Sie machen können und die in etwa gleichwertig ist==

Die Leute werden oft verwenden = O(...), was vielleicht die korrektere "comp-sci" -Notation ist und völlig legitim zu verwenden ist. "f = O (...)" wird gelesen "f ist Ordnung ... / f ist xxx-begrenzt durch ..." und wird als "f ist ein Ausdruck, dessen Asymptotik ... ist" angesehen. Mir wurde beigebracht, die strengeren zu verwenden ∈ O(...). ∈bedeutet "ist ein Element von" (immer noch wie zuvor gelesen). In diesem speziellen Fall O(N²)enthält Elemente wie { 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} und ist unendlich groß, aber es ist immer noch eine Menge.

O und Ω sind nicht symmetrisch (n = O (n²), aber n² ist nicht O (n)), aber Ɵ ist symmetrisch und (da diese Beziehungen alle transitiv und reflexiv sind) Ɵ ist daher symmetrisch und transitiv und reflexiv und unterteilt daher die Menge aller Funktionen in Äquivalenzklassen . Eine Äquivalenzklasse ist eine Reihe von Dingen, die wir als gleich betrachten. Das heißt, bei jeder Funktion, die Sie sich vorstellen können, können Sie einen kanonischen / einzigartigen "asymptotischen Vertreter" der Klasse finden (indem Sie im Allgemeinen die Grenze nehmen ... denke ich ); So wie Sie alle ganzen Zahlen in Quoten oder Gleichungen gruppieren können, können Sie alle Funktionen mit Ɵ in x-ish, log (x) ^ 2-ish usw. gruppieren, indem Sie kleinere Begriffe im Grunde ignorieren (aber manchmal bleiben Sie möglicherweise hängen kompliziertere Funktionen, die für sich getrennte Klassen sind).

Die =Notation könnte die gebräuchlichste sein und wird sogar in Artikeln von weltbekannten Informatikern verwendet. Darüber hinaus ist es häufig der Fall, dass in einer ungezwungenen Umgebung die Leute sagen, O(...)wann sie meinen Ɵ(...); Dies ist technisch wahr, da die Menge der Dinge Ɵ(exactlyThis)eine Teilmenge von O(noGreaterThanThis)... ist und es einfacher ist zu tippen. ;-);

EDIT: Kurzer Hinweis, dies verwechselt mit ziemlicher Sicherheit die Big O-Notation (die eine Obergrenze ist) mit der Theta-Notation (die sowohl eine Ober- als auch eine Untergrenze ist). Nach meiner Erfahrung ist dies typisch für Diskussionen in nicht-akademischen Umgebungen. Entschuldigung für etwaige Verwirrung.

In einem Satz: Wie lange dauert es, bis Ihr Job abgeschlossen ist?

Offensichtlich wird nur "Größe" als Eingabe und "Zeitaufwand" als Ausgabe verwendet - die gleiche Idee gilt, wenn Sie über die Speichernutzung usw. sprechen möchten.

Hier ist ein Beispiel, wo wir N T-Shirts haben, die wir trocknen möchten. Wir gehen davon aus, dass es unglaublich schnell ist, sie in die Trocknungsposition zu bringen (dh die menschliche Interaktion ist vernachlässigbar). Das ist im wirklichen Leben natürlich nicht der Fall ...

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

• Verwenden eines Wäschetrockners: Sie legen 10 Hemden in jede Ladung, und eine Stunde später sind sie fertig. (Ignorieren Sie die tatsächlichen Zahlen hier - sie sind irrelevant.) Das Trocknen von 50 Hemden dauert also ungefähr fünfmal so lange wie das Trocknen von 10 Hemden.

• Alles in einen Lüftungsschrank stellen: Wenn wir alles auf einen großen Haufen legen und nur die allgemeine Wärme zulassen, dauert es lange, bis die mittleren Hemden trocken sind. Ich möchte das Detail nicht erraten, aber ich vermute, dass dies mindestens O (N ^ 2) ist - wenn Sie die Waschlast erhöhen, erhöht sich die Trocknungszeit schneller.

Ein wichtiger Aspekt der "Big O" -Notation ist, dass dies nicht der Fall ist , welcher Algorithmus für eine bestimmte Größe schneller ist. Nehmen Sie eine Hashtabelle (Zeichenfolgenschlüssel, ganzzahliger Wert) gegen ein 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? (dh für das Array "Finden Sie das erste Element, bei dem der Zeichenfolgenteil mit dem angegebenen Schlüssel übereinstimmt.") Hashtabellen werden im Allgemeinen amortisiert (~ = "im Durchschnitt") O (1) - sobald sie eingerichtet sind, sollte es ungefähr dauern Die gleiche Zeit, um einen Eintrag in einer 100-Eintragstabelle zu finden, wie in einer 1.000.000-Eintragstabelle. Das Finden eines Elements in einem Array (basierend auf Inhalt und nicht auf Index) ist linear, dh 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 möglicherweise schneller - Sie können möglicherweise alle Zeichenfolgen in der Zeit überprüfen, die erforderlich ist, um nur den Hashcode des von Ihnen betrachteten zu berechnen. Wenn der Datensatz jedoch größer wird, schlägt die Hashtabelle schließlich das Array.

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

Beispiele:

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

• O (n ² ): 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 (2 ⁿ ): Wenn die Eingabegröße um eins erhöht wird, verdoppelt sich die Laufzeit

Die Eingabegröße ist normalerweise der Raum in Bits, der zur Darstellung der Eingabe benötigt wird.

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

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

Genauer gesagt wird die Big O-Notation verwendet, um das asymptotische Verhalten einer Funktion auszudrücken. Das heißt, 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 zur Fertigstellung ist unabhängig von der Größe des Eingabesatzes gleich. Ein Beispiel ist der Zugriff auf ein Array-Element über den Index.
• O (Log N) - Die Zeit bis zur Fertigstellung erhöht sich ungefähr im Einklang mit log2 (n). Zum Beispiel dauern 1024 Elemente ungefähr doppelt so lange wie 32 Elemente, da Log2 (1024) = 10 und Log2 (32) = 5. Ein Beispiel ist das Finden eines Elements in einem binären Suchbaum (BST).
• O (N) - Zeit bis zur Fertigstellung, die linear mit der Größe des Eingabesatzes skaliert. Mit anderen Worten, wenn Sie die Anzahl der Elemente im Eingabesatz verdoppeln, dauert der Algorithmus ungefähr doppelt so lange. Ein Beispiel ist das Zählen der Anzahl von Elementen in einer verknüpften Liste.
• O (N Log N) - Die Zeit bis zur Fertigstellung erhöht sich um die Anzahl der Elemente gegenüber dem Ergebnis von Log2 (N). Ein Beispiel hierfür ist die Heap-Sortierung und die schnelle Sortierung .
• O (N ^ 2) - Die Zeit bis zur Fertigstellung entspricht ungefähr dem Quadrat der Anzahl der Elemente. Ein Beispiel hierfür ist die Blasensortierung .
• O (N!) - Die Zeit bis zur Fertigstellung ist die Fakultät des Eingabesatzes. Ein Beispiel hierfür ist die Brute-Force-Lösung für das Problem des Handlungsreisenden .

Big O ignoriert Faktoren, die nicht sinnvoll zur Wachstumskurve einer Funktion beitragen, wenn die Eingabegröße gegen unendlich zunimmt. Dies bedeutet, dass Konstanten, die der Funktion hinzugefügt oder mit dieser multipliziert werden, einfach ignoriert werden.

Big O ist nur eine Möglichkeit, sich auf übliche Weise auszudrücken: "Wie viel Zeit / Raum benötigt ich, um meinen Code auszuführen?".

Sie können oft O (n), O (n ² ), O (nlogn) usw. sehen, all dies sind nur Möglichkeiten zu zeigen; Wie ändert sich ein Algorithmus?

O (n) bedeutet, dass Big O n ist, und jetzt könnten Sie denken: "Was ist n!?" Nun, "n" ist die Anzahl der Elemente. Imaging Sie möchten nach einem Element in einem Array suchen. Sie müssten auf jedes Element schauen und als "Sind Sie das richtige Element / Element?" Im schlimmsten Fall befindet sich das Element am letzten Index, was bedeutet, dass es so lange gedauert hat, wie Elemente in der Liste vorhanden sind. Um generisch zu sein, sagen wir: "Oh hey, n ist eine faire Menge an Werten!" .

Dann verstehen Sie vielleicht, was "n ² " bedeutet, aber um noch genauer zu sein, spielen Sie mit dem Gedanken, dass Sie einen einfachen, einfachsten Sortieralgorithmus haben. Bubblesort. Dieser Algorithmus muss für jedes Element die gesamte Liste durchsuchen.

Meine Liste

1. 1
2. 6
3. 3

Der Fluss hier wäre:

• Vergleiche 1 und 6, welches ist das größte? Ok 6 ist in der richtigen Position und bewegt sich vorwärts!
• Vergleiche 6 und 3, oh, 3 ist weniger! Lassen Sie uns das verschieben, Ok, die Liste hat sich geändert, wir müssen jetzt von vorne beginnen!

Dies ist O n ^2, da Sie sich alle Elemente in der Liste ansehen müssen, in denen "n" Elemente vorhanden sind. Für jeden Artikel sehen Sie sich noch einmal alle Artikel an. Zum Vergleich ist dies auch "n". Für jeden Artikel sehen Sie also "n" mal, was n * n = n ^{2 bedeutet}

Ich hoffe das ist so einfach wie du es willst.

Aber denken Sie daran, Big O ist nur ein Weg, sich in Zeit und Raum zu versetzen.

Big O beschreibt die grundlegende Skalierung eines Algorithmus.

Es gibt viele Informationen, die Big O Ihnen nicht über einen bestimmten Algorithmus sagt. Es schneidet bis auf den Knochen und gibt nur Informationen über die Skalierung eines Algorithmus, insbesondere darüber, wie die Ressourcennutzung (Denkzeit oder Speicher) eines Algorithmus als Reaktion auf die "Eingabegröße" skaliert.

Betrachten Sie den Unterschied zwischen einer Dampfmaschine und einer Rakete. Sie sind nicht nur verschiedene Sorten derselben Sache (wie zum Beispiel ein Prius-Motor gegen einen Lamborghini-Motor), sondern im Kern dramatisch unterschiedliche Arten von Antriebssystemen. Eine Dampfmaschine kann schneller sein als eine Spielzeugrakete, aber keine Dampfkolbenmaschine kann die Geschwindigkeiten einer Trägerrakete erreichen. Dies liegt daran, dass diese Systeme unterschiedliche Skalierungseigenschaften in Bezug auf das Verhältnis des Kraftstoffs aufweisen, der zum Erreichen einer bestimmten Geschwindigkeit ("Eingangsgröße") erforderlich ist ("Ressourcenverbrauch").

Warum ist das so wichtig? Denn Software befasst sich mit Problemen, deren Größe sich um Faktoren bis zu einer Billion unterscheiden kann. Betrachten Sie das für einen Moment. Das Verhältnis zwischen der Geschwindigkeit, die erforderlich ist, um zum Mond zu gelangen, und der menschlichen Gehgeschwindigkeit beträgt weniger als 10.000: 1, und das ist absolut winzig im Vergleich zu dem Bereich, in dem Software möglicherweise Eingabegrößen aufweist. Und da Software möglicherweise einem astronomischen Bereich bei den Eingabegrößen ausgesetzt ist, besteht das Potenzial für die Big O-Komplexität eines Algorithmus, dessen grundlegende Skalierung die Implementierung von Implementierungsdetails übertrifft.

Betrachten Sie das kanonische Sortierbeispiel. Die Blasensortierung ist O (n ² ), während die Zusammenführungssortierung O (n log n) ist. Angenommen, Sie haben zwei Sortieranwendungen, Anwendung A mit Blasensortierung und Anwendung B mit Zusammenführungssortierung. Angenommen, für Eingabegrößen von etwa 30 Elementen ist Anwendung A beim Sortieren 1.000-mal schneller als Anwendung B. Wenn Sie nie mehr als 30 Elemente sortieren müssen, sollten Sie Anwendung A bevorzugen, da diese bei diesen Eingabegrößen viel schneller ist. Wenn Sie jedoch feststellen, dass Sie möglicherweise zehn Millionen Elemente sortieren müssen, ist zu erwarten, dass Anwendung B in diesem Fall tatsächlich tausendmal schneller als Anwendung A ist, was ausschließlich auf die Art und Weise zurückzuführen ist, wie jeder Algorithmus skaliert.

Hier ist das einfache englische Bestiarium, das ich normalerweise benutze, um die gängigen Sorten von Big-O zu erklären

Ziehen Sie in allen Fällen Algorithmen vor, die weiter oben in der Liste stehen, und Algorithmen, die weiter unten in der Liste stehen. Die Kosten für den Wechsel zu einer teureren Komplexitätsklasse variieren jedoch erheblich.

O (1):

Kein Wachstum. Unabhängig davon, wie groß das Problem ist, können Sie es in der gleichen Zeit lösen. Dies ist etwas analog zum Rundfunk, bei dem für die Übertragung über eine bestimmte Entfernung dieselbe Energiemenge benötigt wird, unabhängig von der Anzahl der Personen, die sich innerhalb des Sendebereichs befinden.

O (log n ):

Diese Komplexität ist die gleiche wie bei O (1), nur dass sie nur ein bisschen schlimmer ist. Für alle praktischen Zwecke können Sie dies als eine sehr große konstante Skalierung betrachten. Der Unterschied in der Arbeit zwischen der Verarbeitung von 1 Tausend und 1 Milliarde Artikeln ist nur ein Faktor sechs.

O ( n ):

Die Kosten für die Lösung des Problems sind proportional zur Größe des Problems. Wenn sich Ihr Problem verdoppelt, verdoppeln sich die Kosten der Lösung. Da die meisten Probleme auf irgendeine Weise in den Computer gescannt werden müssen, z. B. Dateneingabe, Festplattenlesevorgänge oder Netzwerkverkehr, ist dies im Allgemeinen ein erschwinglicher Skalierungsfaktor.

O ( n log n ):

Diese Komplexität ist O ( n ) sehr ähnlich . Für alle praktischen Zwecke sind die beiden gleichwertig. Dieser Komplexitätsgrad wird im Allgemeinen immer noch als skalierbar angesehen. Durch Optimieren der Annahmen können einige O ( n log n ) -Algorithmen in O ( n ) -Algorithmen umgewandelt werden. Wenn Sie beispielsweise die Größe der Schlüssel begrenzen, wird die Sortierung von O ( n log n ) auf O ( n ) reduziert .

O ( n ² ):

Wächst als Quadrat, wobei n die Länge der Seite eines Quadrats ist. Dies ist die gleiche Wachstumsrate wie der "Netzwerkeffekt", bei dem jeder in einem Netzwerk möglicherweise alle anderen im Netzwerk kennt. Wachstum ist teuer. Die meisten skalierbaren Lösungen können keine Algorithmen mit dieser Komplexität verwenden, ohne signifikante Gymnastik zu betreiben. Dies gilt im Allgemeinen auch für alle anderen Polynomkomplexitäten - O ( n ^k ) -.

O (2 ⁿ ):

Skaliert nicht. Sie haben keine Hoffnung, ein nicht trivial großes Problem zu lösen. Nützlich, um zu wissen, was zu vermeiden ist, und um Experten zu finden, die ungefähre Algorithmen in O ( n ^k ) finden .

Big O ist ein Maß dafür, wie viel Zeit / Raum ein Algorithmus im Verhältnis zur Größe seiner Eingabe verwendet.

Wenn ein Algorithmus O (n) ist, nimmt die Zeit / der Raum mit der gleichen Geschwindigkeit zu wie seine Eingabe.

Wenn ein Algorithmus O (n ² ) ist, nimmt die Zeit / der Raum mit der Rate seiner Eingabe im Quadrat zu.

und so weiter.

Was ist eine einfache englische Erklärung für Big O? Mit möglichst wenig formaler Definition und einfacher Mathematik.

Eine einfache englische Erklärung der Notwendigkeit einer Big-O-Notation:

Wenn wir programmieren, versuchen wir, ein Problem zu lösen. Was wir codieren, wird als Algorithmus bezeichnet. Mit der Big O-Notation können wir die Leistung unserer Algorithmen im ungünstigsten Fall auf standardisierte Weise vergleichen. Die Hardwarespezifikationen variieren im Laufe der Zeit, und Verbesserungen der Hardware können die Zeit verkürzen, die ein Algorithmus zum Ausführen benötigt. Das Ersetzen der Hardware bedeutet jedoch nicht, dass unser Algorithmus im Laufe der Zeit besser oder besser ist, da unser Algorithmus immer noch derselbe ist. Um verschiedene Algorithmen vergleichen zu können und festzustellen, ob einer besser ist oder nicht, verwenden wir die Big O-Notation.

Eine einfache englische Erklärung, was Big O-Notation ist:

Nicht alle Algorithmen werden in derselben Zeit ausgeführt und können abhängig von der Anzahl der Elemente in der Eingabe variieren, die wir n nennen . Basierend darauf betrachten wir die Worst-Case-Analyse oder eine Obergrenze der Laufzeit, wenn n immer größer wird. Wir müssen uns bewusst sein, was n ist, weil viele der Big O-Notationen darauf verweisen.

Es ist sehr schwierig, die Geschwindigkeit von Softwareprogrammen zu messen, und wenn wir es versuchen, können die Antworten sehr komplex und voller Ausnahmen und Sonderfälle sein. Dies ist ein großes Problem, da all diese Ausnahmen und Sonderfälle ablenkend und nicht hilfreich sind, wenn wir zwei verschiedene Programme miteinander vergleichen möchten, um herauszufinden, welches "am schnellsten" ist.

Aufgrund all dieser nicht hilfreichen Komplexität versuchen die Menschen, die Geschwindigkeit von Softwareprogrammen mit den kleinstmöglichen und am wenigsten komplexen (mathematischen) Ausdrücken zu beschreiben. Diese Ausdrücke sind sehr, sehr grobe Annäherungen: Obwohl sie mit etwas Glück die "Essenz" erfassen, ob eine Software schnell oder langsam ist.

Da es sich um Annäherungen handelt, verwenden wir den Ausdruck "O" (Big Oh) im Ausdruck als Konvention, um dem Leser zu signalisieren, dass wir eine grobe Vereinfachung vornehmen. (Und um sicherzustellen, dass niemand fälschlicherweise denkt, dass der Ausdruck in irgendeiner Weise korrekt ist).

Wenn Sie das "Oh" als "in der Größenordnung von" oder "ungefähr" lesen, werden Sie nicht zu weit falsch liegen. (Ich denke, die Wahl des Big-Oh könnte ein Versuch des Humors gewesen sein).

Das einzige, was diese "Big-Oh" -Ausdrücke versuchen, ist zu beschreiben, wie stark die Software langsamer wird, wenn wir die Datenmenge erhöhen, die die Software verarbeiten muss. Wenn wir die Datenmenge verdoppeln, die verarbeitet werden muss, benötigt die Software dann doppelt so lange, um ihre Arbeit zu beenden? Zehnmal so lang? In der Praxis gibt es eine sehr begrenzte Anzahl von Big-Oh-Ausdrücken, denen Sie begegnen und über die Sie sich Sorgen machen müssen:

Der gute:

• O(1) Konstante : Das Programm benötigt dieselbe Zeit, um ausgeführt zu werden, egal wie groß die Eingabe ist.
• O(log n) Logarithmisch : Die Programmlaufzeit steigt nur langsam an, selbst wenn die Größe der Eingabe stark zunimmt.

Das Schlechte:

• O(n) Linear : Die Programmlaufzeit erhöht sich proportional zur Größe der Eingabe.
• O(n^k) Polynom : - Die Verarbeitungszeit wächst als Polynomfunktion immer schneller, wenn die Größe der Eingabe zunimmt.

... und das Hässliche:

• O(k^n) Exponentiell Die Programmlaufzeit nimmt sehr schnell zu, selbst wenn die Größe des Problems moderat zunimmt. Es ist nur praktisch, kleine Datensätze mit exponentiellen Algorithmen zu verarbeiten.
• O(n!) Factorial Die Programmlaufzeit ist länger, als Sie es sich leisten können, auf etwas anderes als die kleinsten und trivialsten Datensätze zu warten.

Eine einfache und unkomplizierte Antwort kann sein:

Big O repräsentiert die schlechtestmögliche Zeit / den schlechtesten Raum für diesen Algorithmus. Der Algorithmus wird niemals mehr Raum / Zeit über dieser Grenze benötigen. Big O steht im Extremfall für zeitliche / räumliche Komplexität.

Ok, meine 2 Cent.

Big-O ist die Rate des Anstiegs der vom Programm verbrauchten Ressourcen in Bezug auf die Größe der Probleminstanz

Ressource: Könnte die Gesamt-CPU-Zeit sein, könnte maximaler RAM-Speicher sein. Standardmäßig bezieht sich auf die CPU-Zeit.

Angenommen, das Problem ist "Finde die Summe".

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

problem-instance = {5,10,15} ==> problem-instance-size = 3, iterations-in-loop = 3

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5 iterations-in-loop = 5

Für die Eingabe der Größe "n" wächst das Programm mit einer Geschwindigkeit von "n" Iterationen im Array. Daher ist Big-O N ausgedrückt als O (n)

Angenommen, das Problem ist "Find the Combination".

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

problem-instance = {5,10,15} ==> problem-instance-size = 3, total-iterations = 3 * 3 = 9

Probleminstanz = {5,10,15,20,25} ==> Probleminstanzgröße = 5, Gesamtiterationen = 5 * 5 = 25

Für die Eingabe der Größe "n" wächst das Programm mit einer Geschwindigkeit von "n * n" Iterationen im Array. Daher ist Big-O N ^2, ausgedrückt als O (n ² )

Die Big O-Notation beschreibt die Obergrenze eines Algorithmus in Bezug auf Raum oder Laufzeit. Das n ist die Anzahl der Elemente im Problem (dh die Größe eines Arrays, die Anzahl der Knoten in einem Baum usw.). Wir sind daran interessiert, die Laufzeit zu beschreiben, wenn n groß wird.

Wenn wir sagen, dass ein Algorithmus O (f (n)) ist, sagen wir, dass die Laufzeit (oder der Platzbedarf) dieses Algorithmus immer niedriger ist als einige konstante Zeiten f (n).

Zu sagen, dass die binäre Suche eine Laufzeit von O (logn) hat, bedeutet, dass es eine Konstante c gibt, mit der Sie log (n) multiplizieren können, die immer größer ist als die Laufzeit der binären Suche. In diesem Fall haben Sie immer einen konstanten Faktor für log (n) -Vergleiche.

Mit anderen Worten, wobei g (n) die Laufzeit Ihres Algorithmus ist, sagen wir, dass g (n) = O (f (n)) ist, wenn g (n) <= c * f (n), wenn n> k ist, wobei c und k sind einige Konstanten.

" Was ist eine einfache englische Erklärung für Big O? Mit so wenig formaler Definition wie möglich und einfacher Mathematik. "

Eine so schön einfache und kurze Frage scheint zumindest eine ebenso kurze Antwort zu verdienen, wie sie ein Schüler während des Nachhilfeunterrichts erhalten könnte.

Die Big O-Notation gibt lediglich an, wie viel Zeit * ein Algorithmus innerhalb nur der Menge der Eingabedaten ** ausführen kann .

(* in einem wunderbaren, einheitsfreien Zeitgefühl!)
(** worauf es ankommt, denn die Menschen werden immer mehr wollen , ob sie heute oder morgen leben)

Was ist so wunderbar an der Big O-Notation, wenn es das ist, was es tut?

• Praktisch gesprochen ist Big O Analyse so nützlich und wichtig , weil Big O den Fokus eindeutig auf dem Algorithmus setzt eigene Komplexität und völlig ignoriert alles , was lediglich eine Proportionalitätskonstante-wie eine JavaScript - Engine ist, die Geschwindigkeit einer CPU, die Internetverbindung, und all die Dinge , die schnell als laughably veraltet als Modell geworden geworden T . Big O konzentriert sich auf Leistung nur in einer Weise, die für Menschen, die in der Gegenwart oder in der Zukunft leben, gleichermaßen wichtig ist.

• Die Big O-Notation beleuchtet auch direkt das wichtigste Prinzip der Computerprogrammierung / -technik, das alle guten Programmierer zum Nachdenken und Träumen anregt: Der einzige Weg, über den langsamen Fortschritt der Technologie hinaus Ergebnisse zu erzielen, besteht darin, ein besseres zu erfinden Algorithmus .

Algorithmusbeispiel (Java):

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Algorithmusbeschreibung:

• Dieser Algorithmus durchsucht eine Liste Element für Element nach einem Schlüssel.

• Wenn es sich bei jedem Element in der Liste um den Schlüssel handelt, wird True zurückgegeben.

• Wenn die Schleife beendet wurde, ohne den Schlüssel zu finden, geben Sie False zurück.

Die Big-O-Notation repräsentiert die Obergrenze der Komplexität (Zeit, Raum, ..)

So finden Sie die Komplexität von Big-O on Time:

• Berechnen Sie, wie viel Zeit (in Bezug auf die Eingabegröße) der schlimmste Fall benötigt:

• Worst-Case: Der Schlüssel ist in der Liste nicht vorhanden.

• Zeit (Worst-Case) = 4n + 1

• Zeit: O (4n + 1) = O (n) | In Big-O werden Konstanten vernachlässigt

• O (n) ~ linear

Es gibt auch Big-Omega, die die Komplexität des Best-Case darstellen:

• Best-Case: Der Schlüssel ist das erste Element.

• Zeit (Best-Case) = 4

• Zeit: Ω (4) = O (1) ~ Instant \ Constant

Big O.

f (x) = O ( g (x)), wenn x zu a geht (zum Beispiel a = + ∞), bedeutet, dass es eine Funktion k gibt, so dass:

1. f (x) = k (x) g (x)

2. k ist in einer Nachbarschaft von a begrenzt (wenn a = + ∞, bedeutet dies, dass es Zahlen N und M gibt, so dass für jedes x> N | k (x) | <M).

Mit anderen Worten, im Klartext: f (x) = O ( g (x)) bedeutet x → a, dass sich f in einer Nachbarschaft von a in das Produkt von g und einer begrenzten Funktion zerlegt .

Klein o

Übrigens ist hier zum Vergleich die Definition von kleinem o.

f (x) = o ( g (x)), wenn x zu a geht, bedeutet, dass es eine Funktion k gibt, so dass:

1. f (x) = k (x) g (x)

2. k (x) geht auf 0, wenn x auf a geht.

Beispiele

• sin x = O (x) wenn x → 0.

• sin x = O (1) wenn x → + ∞,

• x ² + x = O (x) wenn x → 0,

• x ² + x = O (x ² ) wenn x → + ∞,

• ln (x) = o (x) = O (x) wenn x → + ∞.

Beachtung! Die Notation mit dem Gleichheitszeichen "=" verwendet eine "falsche Gleichheit": Es ist wahr, dass o (g (x)) = O (g (x)), aber falsch, dass O (g (x)) = o (g (x)). Ebenso ist es in Ordnung, "ln (x) = o (x) zu schreiben, wenn x → + ∞", aber die Formel "o (x) = ln (x)" würde keinen Sinn ergeben.

Mehr Beispiele

• O (1) = O (n) = O (n ² ) wenn n → + ∞ (aber nicht umgekehrt ist die Gleichheit "falsch"),

• O (n) + O (n ² ) = O (n ² ), wenn n → + ∞

• O (O (n ² )) = O (n ² ), wenn n → + ∞

• O (n ² ) O (n ³ ) = O (n ⁵ ), wenn n → + ∞

Hier ist der Wikipedia-Artikel: https://en.wikipedia.org/wiki/Big_O_notation

Die Big O-Notation beschreibt, wie schnell ein Algorithmus bei einer beliebigen Anzahl von Eingabeparametern ausgeführt wird, die wir "n" nennen. In der Informatik ist dies nützlich, da verschiedene Maschinen mit unterschiedlichen Geschwindigkeiten arbeiten und die Aussage, dass ein Algorithmus 5 Sekunden dauert, nicht viel aussagt, da ich möglicherweise ein System mit einem 4,5-GHz-Octo-Core-Prozessor ausführe Ein 15 Jahre altes 800-MHz-System, das unabhängig vom Algorithmus länger dauern kann. Anstatt anzugeben, wie schnell ein Algorithmus in Bezug auf die Zeit ausgeführt wird, geben wir an, wie schnell er in Bezug auf die Anzahl der Eingabeparameter oder "n" ausgeführt wird. Indem wir Algorithmen auf diese Weise beschreiben, können wir die Geschwindigkeiten von Algorithmen vergleichen, ohne die Geschwindigkeit des Computers selbst berücksichtigen zu müssen.

Ich bin mir nicht sicher, ob ich weiter zu diesem Thema beitrage, dachte aber trotzdem, ich würde es teilen: Ich habe einmal festgestellt, dass dieser Blog-Beitrag einige recht hilfreiche (wenn auch sehr grundlegende) Erklärungen und Beispiele zu Big O enthält:

Anhand von Beispielen hat dies dazu beigetragen, die Grundlagen in meinen schildpattartigen Schädel zu bringen. Ich denke, es ist eine ziemlich 10-minütige Ablesung, um Sie in die richtige Richtung zu bringen.

Sie möchten alles wissen, was Sie über Big O wissen müssen? Ich auch.

Um von Big O zu sprechen, werde ich Wörter verwenden, die nur einen Schlag enthalten. Ein Ton pro Wort. Kleine Wörter sind schnell. Sie kennen diese Wörter und ich auch. Wir werden Wörter mit einem Ton verwenden. Sie sind klein. Ich bin sicher, Sie werden alle Wörter kennen, die wir verwenden werden!

Lassen Sie uns und ich jetzt über die Arbeit sprechen. Meistens mag ich keine Arbeit. Arbeitest du gern Es mag sein, dass Sie es tun, aber ich bin sicher, dass ich es nicht tue.

Ich gehe nicht gern zur Arbeit. Ich verbringe keine Zeit gerne bei der Arbeit. Wenn es nach mir ginge, würde ich gerne nur spielen und lustige Dinge tun. Fühlst du dich genauso wie ich?

Jetzt muss ich manchmal zur Arbeit gehen. Es ist traurig, aber wahr. Wenn ich bei der Arbeit bin, habe ich eine Regel: Ich versuche, weniger zu arbeiten. So nah wie möglich an keiner Arbeit. Dann gehe ich spielen!

Hier ist die große Neuigkeit: Das große O kann mir helfen, keine Arbeit zu machen! Ich kann die meiste Zeit spielen, wenn ich Big O kenne. Weniger Arbeit, mehr Spiel! Das ist es, was mir das große O hilft.

Jetzt habe ich etwas Arbeit. Ich habe diese Liste: eins, zwei, drei, vier, fünf, sechs. Ich muss alle Dinge in diese Liste aufnehmen.

Wow, ich hasse Arbeit. Aber na ja, ich muss das machen. Also los geht's.

Eins plus zwei ist drei ... plus drei ist sechs ... und vier ist ... ich weiß es nicht. Ich habe mich verlaufen. Es ist zu schwer für mich, es in meinem Kopf zu tun. Ich mag diese Art von Arbeit nicht sehr.

Also machen wir die Arbeit nicht. Lassen Sie uns und ich nur darüber nachdenken, wie schwer es ist. Wie viel Arbeit müsste ich tun, um sechs Zahlen hinzuzufügen?

Okay, lass uns nachsehen. Ich muss eins und zwei hinzufügen und dann das zu drei und dann das zu vier ... Alles in allem zähle ich sechs addiert. Ich muss sechs Adds machen, um das zu lösen.

Hier kommt großes O, um uns zu sagen, wie schwer diese Mathematik ist.

Big O sagt: Wir müssen sechs Adds machen, um dies zu lösen. Ein Add für jede Sache von eins bis sechs. Sechs kleine Arbeiten ... jede Arbeit ist eine Ergänzung.

Nun, ich werde nicht die Arbeit machen, um sie jetzt hinzuzufügen. Aber ich weiß, wie schwer es sein würde. Es wären sechs Adds.

Oh nein, jetzt habe ich mehr Arbeit. Meine Güte. Wer macht so was?!

Jetzt bitten sie mich, eins bis zehn hinzuzufügen! Warum sollte ich das tun? Ich wollte nicht eins zu sechs hinzufügen. Von eins bis zehn hinzuzufügen… na ja… das wäre noch schwieriger!

Wie viel schwerer wäre es? Wie viel mehr Arbeit müsste ich tun? Benötige ich mehr oder weniger Schritte?

Nun, ich denke, ich müsste zehn Adds machen ... eins für jede Sache von eins bis zehn. Zehn ist mehr als sechs. Ich müsste so viel mehr arbeiten, um eins bis zehn hinzuzufügen, als eins bis sechs!

Ich möchte jetzt nicht hinzufügen. Ich möchte nur darüber nachdenken, wie schwierig es sein könnte, so viel hinzuzufügen. Und ich hoffe, so schnell wie möglich zu spielen.

Von eins bis sechs hinzuzufügen, das ist etwas Arbeit. Aber sehen Sie, von eins bis zehn hinzuzufügen, das ist mehr Arbeit?

Big O ist dein Freund und mein. Big O hilft uns darüber nachzudenken, wie viel Arbeit wir tun müssen, damit wir planen können. Und wenn wir mit Big O befreundet sind, kann er uns helfen, eine Arbeit zu wählen, die nicht so schwer ist!

Jetzt müssen wir neue Arbeit leisten. Ach nein. Ich mag diese Arbeitssache überhaupt nicht.

Die neue Arbeit ist: Addiere alle Dinge von eins bis n.

Warten! Was ist n? Habe ich das vermisst Wie kann ich von eins zu n hinzufügen, wenn Sie mir nicht sagen, was n ist?

Nun, ich weiß nicht was n ist. Mir wurde nicht gesagt. Warst du? Nein? Naja. Wir können die Arbeit also nicht machen. Wütend.

Aber obwohl wir die Arbeit jetzt nicht machen werden, können wir erraten, wie schwer es wäre, wenn wir n wüssten. Wir müssten n Dinge zusammenzählen, oder? Na sicher!

Jetzt kommt großes O, und er wird uns sagen, wie schwer diese Arbeit ist. Er sagt: Alle Dinge von eins zu N eins nach dem anderen hinzuzufügen, ist O (n). Um all diese Dinge hinzuzufügen, [ich weiß, ich muss n-mal hinzufügen.] [1] Das ist groß O! Er sagt uns, wie schwer es ist, irgendeine Art von Arbeit zu erledigen.

Für mich ist Big O wie ein großer, langsamer Boss. Er denkt an die Arbeit, aber er tut es nicht. Er könnte sagen: "Diese Arbeit ist schnell." Oder er könnte sagen: "Diese Arbeit ist so langsam und hart!" Aber er macht die Arbeit nicht. Er schaut sich nur die Arbeit an und sagt uns dann, wie viel Zeit es dauern könnte.

Ich interessiere mich sehr für große O. Warum? Ich arbeite nicht gern! Niemand arbeitet gern. Deshalb lieben wir alle großes O! Er sagt uns, wie schnell wir arbeiten können. Er hilft uns darüber nachzudenken, wie harte Arbeit ist.

Oh oh, mehr Arbeit. Lassen Sie uns jetzt nicht die Arbeit machen. Aber machen wir einen Plan, um dies Schritt für Schritt zu tun.

Sie gaben uns ein Kartenspiel mit zehn Karten. Sie sind alle durcheinander: sieben, vier, zwei, sechs ... überhaupt nicht gerade. Und jetzt ... ist es unsere Aufgabe, sie zu sortieren.

Ergh. Das klingt nach viel Arbeit!

Wie können wir dieses Deck sortieren? Ich habe einen Plan.

Ich werde jedes Kartenpaar Paar für Paar durch das Deck von Anfang bis Ende betrachten. Wenn die erste Karte in einem Paar groß und die nächste Karte in diesem Paar klein ist, tausche ich sie aus. Sonst gehe ich zum nächsten Paar und so weiter und so fort ... und bald ist das Deck fertig.

Wenn das Deck fertig ist, frage ich: Habe ich in diesem Pass Karten getauscht? Wenn ja, muss ich alles noch einmal von oben machen.

Irgendwann, irgendwann wird es keine Swaps mehr geben und unsere Art von Deck würde fertig sein. So viel Arbeit!

Nun, wie viel Arbeit wäre das, die Karten nach diesen Regeln zu sortieren?

Ich habe zehn Karten. Und die meiste Zeit - das heißt, wenn ich nicht viel Glück habe - muss ich das gesamte Deck bis zu zehn Mal durchlaufen, wobei jedes Mal bis zu zehn Kartenwechsel durch das Deck erfolgen.

Big O, hilf mir!

Big O kommt herein und sagt: Für ein Kartenspiel mit n Karten erfolgt die Sortierung auf diese Weise in der Zeit O (N Quadrat).

Warum sagt er n im Quadrat?

Nun, Sie wissen, dass n Quadrat n mal n ist. Jetzt verstehe ich es: n Karten geprüft, bis zu n Mal durch das Deck. Das sind zwei Schleifen mit jeweils n Schritten. Das ist nicht viel Arbeit. Sicher viel Arbeit!

Wenn nun das große O sagt, dass es O (n Quadrat) Arbeit braucht, bedeutet das nicht, dass n Quadrat auf der Nase hinzugefügt wird. In einigen Fällen kann es ein bisschen weniger sein. Im schlimmsten Fall sind es jedoch fast n quadratische Arbeitsschritte, um das Deck zu sortieren.

Hier ist Big O unser Freund.

Big O weist darauf hin: Wenn n groß wird und Karten sortiert werden, wird der Job VIEL SCHWERER als der alte Job, bei dem nur diese Dinge hinzugefügt werden. Woher wissen wir das?

Nun, wenn n wirklich groß wird, ist es uns egal, was wir zu n oder n im Quadrat hinzufügen könnten.

Für großes n ist n im Quadrat größer als n.

Big O sagt uns, dass es schwieriger ist, Dinge zu sortieren, als Dinge hinzuzufügen. O (n im Quadrat) ist mehr als O (n) für großes n. Das bedeutet: Wenn n wirklich groß wird, MUSS das Sortieren eines gemischten Decks von n Dingen mehr Zeit in Anspruch nehmen, als nur n gemischte Dinge hinzuzufügen.

Big O löst die Arbeit für uns nicht. Big O sagt uns, wie schwer die Arbeit ist.

Ich habe ein Kartenspiel. Ich habe sie sortiert. Du hast geholfen. Vielen Dank.

Gibt es eine schnellere Möglichkeit, die Karten zu sortieren? Kann Big O uns helfen?

Ja, es gibt einen schnelleren Weg! Das Lernen dauert einige Zeit, aber es funktioniert ... und es funktioniert ziemlich schnell. Sie können es auch versuchen, aber nehmen Sie sich Zeit für jeden Schritt und verlieren Sie nicht Ihren Platz.

Auf diese neue Art, ein Deck zu sortieren, überprüfen wir Kartenpaare nicht mehr so ​​wie vor einiger Zeit. Hier sind deine neuen Regeln zum Sortieren dieses Decks:

Erstens: Ich wähle eine Karte in dem Teil des Decks, an dem wir gerade arbeiten. Sie können eine für mich auswählen, wenn Sie möchten. (Das erste Mal, wenn wir dies tun, ist „der Teil des Decks, an dem wir gerade arbeiten“ natürlich das gesamte Deck.)

Zweitens: Ich spreize das Deck auf die Karte, die du gewählt hast. Was ist das für eine Spreizung? Wie spreize ich? Nun, ich gehe von der Startkarte nach unten und suche nach einer Karte, die höher ist als die Spreizkarte.

Drei: Ich gehe von der Endkarte nach oben und suche nach einer Karte, die niedriger ist als die Spreizkarte.

Sobald ich diese beiden Karten gefunden habe, tausche ich sie aus und suche nach weiteren Karten zum Tauschen. Das heißt, ich gehe zurück zu Schritt Zwei und spreize auf der Karte, die Sie noch ausgewählt haben.

Irgendwann endet diese Schleife (von zwei bis drei). Es endet, wenn sich beide Hälften dieser Suche auf der Spreizkarte treffen. Dann haben wir gerade das Deck mit der Karte gespreizt, die Sie in Schritt 1 ausgewählt haben. Jetzt sind alle Karten in der Nähe des Starts niedriger als die Spreizkarte. und die Karten am Ende sind höher als die Spreizkarte. Cooler Trick!

Vier (und das ist der lustige Teil): Ich habe jetzt zwei kleine Decks, eines niedriger als die Spreizkarte und eines höher. Jetzt gehe ich zu Schritt eins auf jedem kleinen Deck! Das heißt, ich beginne mit Schritt Eins auf dem ersten kleinen Deck, und wenn diese Arbeit erledigt ist, beginne ich mit Schritt Eins auf dem nächsten kleinen Deck.

Ich zerlege das Deck in Teile und sortiere jedes Teil, immer kleiner, und irgendwann habe ich keine Arbeit mehr zu erledigen. Nun mag dies mit allen Regeln langsam erscheinen. Aber glauben Sie mir, es ist überhaupt nicht langsam. Es ist viel weniger Arbeit als der erste Weg, Dinge zu sortieren!

Wie heißt diese Sorte? Es heißt Quick Sort! Diese Sorte wurde von einem Mann namens CAR Hoare hergestellt und er nannte sie Quick Sort. Jetzt wird Quick Sort ständig verwendet!

Quick Sort zerlegt große Decks in kleine. Das heißt, es teilt große Aufgaben in kleine auf.

Hmmm. Es könnte eine Regel geben, denke ich. Um große Aufgaben klein zu machen, brechen Sie sie auf.

Diese Art ist ziemlich schnell. Wie schnell? Big O sagt uns: Diese Sortierung erfordert im Mittel O (n log n) Arbeit.

Ist es mehr oder weniger schnell als die erste Sorte? Big O, bitte hilf!

Die erste Sorte war O (n im Quadrat). Die schnelle Sortierung ist jedoch O (n log n). Sie wissen, dass n log n kleiner als n im Quadrat ist, für großes n, richtig? So wissen wir, dass Quick Sort schnell ist!

Was ist der beste Weg, wenn Sie ein Deck sortieren müssen? Nun, Sie können tun, was Sie wollen, aber ich würde Quick Sort wählen.

Warum wähle ich Schnellsortierung? Ich arbeite natürlich nicht gern! Ich möchte, dass die Arbeit erledigt wird, sobald ich sie erledigen kann.

Woher weiß ich, dass Quick Sort weniger Arbeit ist? Ich weiß, dass O (n log n) kleiner als O (n im Quadrat) ist. Die O's sind kleiner, so dass Quick Sort weniger Arbeit ist!

Jetzt kennen Sie meinen Freund Big O. Er hilft uns, weniger zu arbeiten. Und wenn Sie Big O kennen, können Sie auch weniger arbeiten!

Das alles hast du bei mir gelernt! Du bist so schlau! Ich danke dir sehr!

Jetzt, wo die Arbeit erledigt ist, lass uns spielen gehen!

[1]: Es gibt eine Möglichkeit, alle Dinge gleichzeitig von eins bis n zu betrügen und hinzuzufügen. Ein Kind namens Gauß fand das heraus, als er acht Jahre alt war. Ich bin zwar nicht so schlau, also frag mich nicht, wie er es gemacht hat .

Ich habe einen einfacheren Weg, um die Zeitkomplexität zu verstehen. Die häufigste Metrik zur Berechnung der Zeitkomplexität ist die Big O-Notation. Dies entfernt alle konstanten Faktoren, so dass die Laufzeit in Bezug auf N geschätzt werden kann, wenn N gegen unendlich geht. Im Allgemeinen kann man sich das so vorstellen:

statement;

Ist konstant. Die Laufzeit der Anweisung ändert sich nicht in Bezug auf 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, erhöht sich 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 Häufigkeit, mit der N durch 2 geteilt werden kann. Dies liegt daran, dass der Algorithmus den Arbeitsbereich bei jeder Iteration in zwei Hälften teilt.

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 logarithmischen Schleifen (iterativ oder rekursiv), daher ist der Algorithmus eine Kombination aus linear und logarithmisch.

Im Allgemeinen ist es linear, mit jedem Element in einer Dimension etwas zu tun, mit jedem Element in zwei Dimensionen etwas zu tun, und der Arbeitsbereich in zwei Hälften zu teilen, ist logarithmisch. Es gibt andere Big O-Kennzahlen wie Kubik, Exponential und Quadratwurzel, aber sie sind bei weitem nicht so häufig. Die Big O-Notation wird als O () beschrieben, wobei das Maß ist. Der Quicksort-Algorithmus würde als O (N * log (N)) beschrieben.

Hinweis: Bei alledem wurden die besten, durchschnittlichen und schlechtesten Maßnahmen nicht berücksichtigt. Jeder hätte seine eigene Big O-Notation. Beachten Sie auch, dass dies eine SEHR vereinfachende Erklärung ist. Big O ist am häufigsten, aber es ist auch komplexer, als ich gezeigt habe. Es gibt auch andere Notationen wie Big Omega, Little O und Big Theta. Sie werden ihnen wahrscheinlich nicht außerhalb eines Kurses zur Algorithmusanalyse begegnen.

• Weitere Informationen finden Sie unter: Hier

Angenommen, Sie bestellen Harry Potter: Schließen Sie die 8-Film-Sammlung [Blu-ray] bei Amazon ab und laden Sie dieselbe Filmsammlung gleichzeitig online herunter. Sie möchten testen, welche Methode schneller ist. Die Lieferung dauert fast einen Tag und der Download ist etwa 30 Minuten früher abgeschlossen. Großartig! Es ist also ein enges 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? Diesmal dauert die Lieferung noch einen Tag, der Online-Download dauert jedoch 3 Tage. Beim Online-Einkauf hat die Anzahl der gekauften Artikel (Eingabe) keinen Einfluss auf die Lieferzeit. Die Ausgabe ist konstant. Wir nennen das O (1) .

Beim Online-Download ist die Downloadzeit direkt proportional zur Größe der Filmdatei (Eingabe). Wir nennen das O (n) .

Aus den Experimenten wissen wir, dass Online-Shopping besser skaliert als Online-Download. Es ist sehr wichtig, die Big-O-Notation zu verstehen, da Sie damit die Skalierbarkeit und Effizienz von Algorithmen analysieren können .

Hinweis: Die Big O-Notation repräsentiert das Worst-Case-Szenario eines Algorithmus. Nehmen wir an, dass O (1) und O (n) die Worst-Case-Szenarien des obigen Beispiels sind.

Referenz : http://carlcheo.com/compsci

Angenommen, wir sprechen von einem Algorithmus A , der etwas mit einem Datensatz der Größe n tun sollte .

Dann O( <some expression X involving n> )heißt es in einfachem Englisch:

Wenn Sie bei der Ausführung von A Pech haben, sind möglicherweise bis zu X (n) Operationen erforderlich.

Zufällig gibt es bestimmte Funktionen (stellen Sie sich diese als Implementierungen von X (n) vor ), die häufig auftreten. Diese sind gut bekannt und leicht im Vergleich (Beispiele: 1, Log N, N, N^2, N!, etc ..)

Wenn Sie diese vergleichen, wenn Sie über A und andere Algorithmen sprechen , ist es einfach, die Algorithmen nach der Anzahl der Operationen zu ordnen, die sie möglicherweise (im schlimmsten Fall) ausführen müssen .

Im Allgemeinen besteht unser Ziel darin, einen Algorithmus A so zu finden oder zu strukturieren , dass er eine Funktion hat X(n), die eine möglichst niedrige Zahl zurückgibt.

Wenn Sie einen geeigneten Begriff von Unendlichkeit in Ihrem Kopf haben, gibt es eine sehr kurze Beschreibung:

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

Und außerdem

Konstante Faktoren sind vernachlässigbar

Wenn Sie auf einen Computer aktualisieren, auf dem Ihr Algorithmus doppelt so schnell ausgeführt werden kann, merkt die große O-Notation dies nicht. Konstante Faktorverbesserungen sind zu klein, um in der Skala, mit der die große O-Notation arbeitet, überhaupt bemerkt zu werden. Beachten Sie, dass dies ein absichtlicher Teil des Entwurfs der Big O-Notation ist.

Es kann zwar alles "Größere" als ein konstanter Faktor festgestellt werden.

Wenn Sie Berechnungen durchführen möchten, deren Größe "groß" genug ist, um als ungefähr unendlich betrachtet zu werden, ist die große O-Notation ungefähr die Kosten für die Lösung Ihres Problems.

Wenn das oben Gesagte keinen Sinn ergibt, haben Sie keinen kompatiblen intuitiven Begriff der Unendlichkeit in Ihrem Kopf, und Sie sollten wahrscheinlich alle oben genannten Punkte ignorieren. Die einzige Möglichkeit, diese Ideen rigoros zu machen oder zu erklären, wenn sie nicht bereits intuitiv nützlich sind, besteht darin, Ihnen zuerst die große O-Notation oder ähnliches beizubringen. (obwohl es sich lohnen kann, diese Ideen noch einmal zu überdenken, wenn Sie die große O-Notation in Zukunft gut verstanden haben)

Was ist eine einfache englische Erklärung für die „Big O“ -Notation?

Sehr schneller Hinweis:

Das O in "Big O" wird als "Reihenfolge" (oder genau als "Reihenfolge von") bezeichnet,
sodass Sie sich buchstäblich vorstellen können, dass es verwendet wird, um etwas zu bestellen, um sie zu vergleichen.

• "Big O" macht zwei Dinge:

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

• Es gibt sieben am häufigsten verwendete Notationen

  1. O (1) bedeutet, dass Ihr Computer eine Aufgabe mit 1Schritt erledigt . Es ist ausgezeichnet, Bestellt Nr. 1
  2. O (logN) bedeutet, dass Ihr Computer eine Aufgabe mit logNSchritten abschließt. Es ist gut, Bestellt Nr. 2
  3. O (N), beende eine Aufgabe mit NSchritten, ihrer Messe, Order No.3
  4. O (NlogN), beendet eine Aufgabe mit O(NlogN)Schritten, es ist nicht gut, Bestellnummer 4
  5. O (N ^ 2), erledige eine Aufgabe mit N^2Schritten, es ist schlecht, Befehl Nr. 5
  6. O (2 ^ N), erledige eine Aufgabe mit 2^NSchritten, es ist schrecklich, Befehl Nr. 6
  7. O (N!), Erledige eine Aufgabe mit N!Schritten, es ist schrecklich, Befehl Nr. 7

Angenommen, Sie erhalten eine Notation. Sie wissen O(N^2)nicht nur, dass die Methode N * N Schritte benötigt, um eine Aufgabe auszuführen, sondern Sie sehen auch, dass sie nicht gut ist, wie O(NlogN)aus ihrer Rangfolge hervorgeht.

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

In CS werden die Schritte zum Ausführen 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 ermittelt Big O den Worst-Case oder misst die Upper-Bound-Schritte.
Sie können sich für den besten Fall auf Big-Ω (Big-Omega) beziehen.

Big-Ω (Big-Omega) -Notation (Artikel) | Khan Akademie

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

  oder formell ansprechen, "Big O" klassifiziert die Algorithmen und standardisiert den Vergleichsprozess.

Einfachste Art, es zu betrachten (in einfachem Englisch)

Wir versuchen herauszufinden, wie sich die Anzahl der Eingabeparameter auf die Laufzeit eines Algorithmus auswirkt. Wenn die Laufzeit Ihrer Anwendung proportional zur Anzahl der Eingabeparameter ist, wird sie als Big O von n bezeichnet.

Die obige Aussage ist ein guter Anfang, aber nicht ganz richtig.

Eine genauere Erklärung (mathematisch)

Annehmen

n = Anzahl der Eingabeparameter

T (n) = Die tatsächliche Funktion, die die Laufzeit des Algorithmus als Funktion von n ausdrückt

c = eine Konstante

f (n) = Eine ungefähre Funktion, die die Laufzeit des Algorithmus als Funktion von n ausdrückt

Dann wird für Big O die Näherung f (n) als gut genug angesehen, solange die folgende Bedingung erfüllt ist.

lim     T(n) ≤ c×f(n)
n→∞

Die Gleichung wird gelesen, wenn sich n der Unendlichkeit nähert, ist T von n kleiner oder gleich c mal f von n.

In der großen O-Notation wird dies geschrieben als

T(n)∈O(n)

Dies wird gelesen, wenn T von n in großem O von n ist.

Zurück zu Englisch

Wenn Sie basierend auf der obigen mathematischen Definition sagen, dass Ihr Algorithmus ein großes O von n ist, bedeutet dies, dass er eine Funktion von n (Anzahl der Eingabeparameter) oder schneller ist . Wenn Ihr Algorithmus Big O von n ist, ist er automatisch auch das Big O von n Quadrat.

Ein großes O von n bedeutet, dass mein Algorithmus mindestens so schnell läuft. Sie können die Big O-Notation Ihres Algorithmus nicht betrachten und sagen, dass er langsam ist. Man kann nur sagen, es ist schnell.

In diesem Video finden Sie ein Video-Tutorial zu Big O von UC Berkley. Es ist eigentlich ein einfaches Konzept. Wenn Sie Professor Shewchuck (auch bekannt als Lehrer auf Gottesniveau) erklären hören, werden Sie sagen: "Oh, das ist alles, was es ist!".

Ich habe eine wirklich gute Erklärung für die große O-Notation gefunden, besonders für jemanden, der nicht viel mit Mathematik zu tun hat.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Die Big O-Notation wird in der Informatik verwendet, um die Leistung oder Komplexität eines Algorithmus zu beschreiben. Big O beschreibt speziell das Worst-Case-Szenario und kann verwendet werden, um die erforderliche Ausführungszeit oder den von einem Algorithmus verwendeten Speicherplatz (z. B. im Speicher oder auf der Festplatte) zu beschreiben.

Jeder, der Programming Pearls oder andere Informatikbücher gelesen hat und keine mathematischen Kenntnisse hat, wird an eine Wand gestoßen sein, wenn er Kapitel erreicht hat, in denen O (N log N) oder eine andere scheinbar verrückte Syntax erwähnt wird. Hoffentlich hilft Ihnen dieser Artikel dabei, die Grundlagen von Big O und Logarithmen zu verstehen.

Als erster Programmierer und zweiter Mathematiker (oder vielleicht dritter oder vierter) fand ich den besten Weg, Big O gründlich zu verstehen, darin, einige Beispiele in Code zu erstellen. Im Folgenden finden Sie einige gängige Wachstumsordnungen sowie nach Möglichkeit Beschreibungen und Beispiele.

O (1)

O (1) beschreibt einen Algorithmus, der unabhängig von der Größe des Eingabedatensatzes immer zur gleichen Zeit (oder im gleichen Raum) ausgeführt wird.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

AUF)

O (N) beschreibt einen Algorithmus, dessen Leistung linear und direkt proportional zur Größe des Eingabedatensatzes wächst. Das folgende Beispiel zeigt auch, wie Big O das Worst-Case-Leistungsszenario bevorzugt. Während jeder Iteration der for-Schleife konnte eine übereinstimmende Zeichenfolge gefunden werden, und die Funktion würde früh zurückkehren, aber die Big O-Notation nimmt immer die Obergrenze an, an der der Algorithmus die maximale Anzahl von Iterationen ausführt.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N ² )

O (N ² ) stellt einen Algorithmus dar, dessen Leistung direkt proportional zum Quadrat der Größe des Eingabedatensatzes ist. Dies ist bei Algorithmen üblich, die verschachtelte Iterationen über den Datensatz beinhalten. Tiefere verschachtelte Iterationen führen zu O (N ³ ), O (N ⁴ ) usw.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O (2 ^N )

O (2 ^N ) bezeichnet einen Algorithmus, dessen Wachstum sich mit jeder Addition zum Eingabedatensatz verdoppelt. Die Wachstumskurve einer O (2 ^N ) -Funktion ist exponentiell - sie beginnt sehr flach und steigt dann meteorisch an. Ein Beispiel für eine O (2 ^N ) -Funktion ist die rekursive Berechnung von Fibonacci-Zahlen:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logarithmen

Logarithmen sind etwas schwieriger zu erklären, daher verwende ich ein allgemeines Beispiel:

Die binäre Suche ist eine Technik zum Durchsuchen sortierter Datensätze. Dabei wird das mittlere Element des Datensatzes, im Wesentlichen der Median, ausgewählt und mit einem Zielwert verglichen. Wenn die Werte übereinstimmen, wird der Erfolg zurückgegeben. Wenn der Zielwert höher als der Wert des Sondenelements ist, nimmt er die obere Hälfte des Datensatzes und führt dieselbe Operation dagegen aus. Wenn der Zielwert niedriger als der Wert des Sondenelements ist, wird die Operation ebenfalls gegen die untere Hälfte ausgeführt. Der Datensatz wird bei jeder Iteration weiter halbiert, bis der Wert gefunden wurde oder der Datensatz nicht mehr aufgeteilt werden kann.

Diese Art von Algorithmus wird als O (log N) beschrieben. Die im Beispiel der binären Suche beschriebene iterative Halbierung von Datensätzen erzeugt eine Wachstumskurve, die am Anfang ihren Höhepunkt erreicht und sich langsam abflacht, wenn die Größe der Datensätze zunimmt, z. B. dauert es eine Sekunde, bis ein Eingabedatensatz mit 10 Elementen fertiggestellt ist, ein Datensatz Das Enthalten von 100 Elementen dauert zwei Sekunden, und ein Datensatz mit 1000 Elementen dauert drei Sekunden. Das Verdoppeln der Größe des Eingabedatensatzes hat nur geringe Auswirkungen auf sein Wachstum, da der Datensatz nach einer einzelnen Iteration des Algorithmus halbiert wird und daher einem Eingabedatensatz entspricht, der halb so groß ist. Dies macht Algorithmen wie die binäre Suche beim Umgang mit großen Datenmengen äußerst effizient.

Dies ist eine sehr vereinfachte Erklärung, aber ich hoffe, sie deckt die wichtigsten Details ab.

Angenommen, Ihr Algorithmus, der sich mit dem Problem befasst, hängt von einigen 'Faktoren' ab, z. B. N und X.

Abhängig von N und X erfordert Ihr Algorithmus einige Operationen, zum Beispiel im schlimmsten Fall 3(N^2) + log(X).

Da Big-O den konstanten Faktor (auch bekannt als 3) nicht sonderlich interessiert, ist das Big-O Ihres Algorithmus O(N^2 + log(X)). Grundsätzlich wird übersetzt, wie viele Operationen Ihr Algorithmus für die Worst-Case-Skalen benötigt.

Vorwort

Algorithmus : Verfahren / Formel zur Lösung eines Problems

Wie analysieren Algorithmen und wie können wir Algorithmen miteinander vergleichen?

Beispiel: Sie und ein Freund werden gebeten, eine Funktion zum Summieren der Zahlen von 0 bis N zu erstellen. Sie haben f (x) und Ihr Freund hat g (x). Beide Funktionen haben das gleiche Ergebnis, aber einen anderen Algorithmus. Um die Effizienz der Algorithmen objektiv zu vergleichen, verwenden wir die Big-O-Notation .

Big-O-Notation: Beschreibt, wie schnell die Laufzeit im Verhältnis zur Eingabe wächst, wenn die Eingabe beliebig groß wird.

3 wichtige Imbissbuden:

1. Vergleichen Sie, wie schnell die Laufzeit wächst. Vergleichen Sie NICHT die genauen Laufzeiten (abhängig von der Hardware).
2. Nur die Laufzeit wächst relativ zur Eingabe (n)
3. Wenn n beliebig groß wird, konzentrieren Sie sich auf die Begriffe, die am schnellsten wachsen, wenn n groß wird (denken Sie an unendlich). Die asymptotische AKA- Analyse

Raumkomplexität: Neben der Zeitkomplexität kümmern wir uns auch um die Raumkomplexität (wie viel Speicher / Raum ein Algorithmus verwendet). Anstatt die Betriebszeit zu überprüfen, überprüfen wir die Größe der Speicherzuweisung.