Was ist eine einfache englische Erklärung der „Big O“-Notation?

https://stackoverflow.com/questions/487258

20-08-2019
|

Frage

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

Lösung

Kurze Notiz, das ist fast sicher verwirrend Big O-Notation (die eine obere Schranke ist) mit Theta-Notation „Θ“ (das ist eine zweiseitige gebunden). Meiner Erfahrung nach ist dies eigentlich typisch für Diskussionen in nicht-akademischen Umfeld. Entschuldigen uns für die Verwirrung verursacht.

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

Big O-Analyse

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

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

Es gibt einige wichtige und bewusst gewählte Worte in diesem Satz:

relativ: Sie können nur Äpfel mit Äpfeln vergleichen. Sie können nicht einen Algorithmus zu tun arithmetische Multiplikation zu einem Algorithmus vergleichen, die eine Liste von ganzen Zahlen sortiert. Aber ein Vergleich von zwei Algorithmen arithmetische Operationen zu tun (eine Multiplikation, eine Addition) wird Ihnen sagen, etwas Sinnvolles;

Darstellung: Big-O (in ihrer einfachsten Form) reduziert den Vergleich zwischen den Algorithmen zu einer einzigen Variablen. Diese Variable basiert auf Beobachtungen oder Annahmen gewählt. Zum Beispiel werden typischerweise verglichenen Sortieralgorithmen, basierend auf Vergleichsoperationen (Vergleich von zwei Knoten ihre relative Reihenfolge zu bestimmen). Dies setzt voraus, dass der Vergleich ist teuer. Aber was, wenn Vergleich ist billig, aber Swapping ist teuer? Sie ändert den Vergleich; und

Komplexität: , wenn es mir 1 Sekunde dauert 10.000 Elemente zu sortieren, wie lange es dauert eine Million zu sortieren? Komplexität in diesem Fall ist ein relatives Maß auf etwas anderes.

Kommen Sie zurück und wieder gelesen, die oben, wenn Sie den Rest gelesen haben.

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

Zusatz;

Subtraktion;

Multiplikation; und

Division.

Jeder von ihnen ist eine Operation oder ein Problem. Verfahren diese zu lösen, ist ein Algorithmus genannt.

Die Zugabe ist die einfachste. Sie säumen die Zahlen nach oben (rechts) und den Ziffern in einer Spalte fügen Sie die letzte Nummer des Zusatzes im Ergebnis zu schreiben. Der ‚Zehner‘ Teil dieser Nummer wird in der nächsten Spalte übertragen.

Nehmen wir an, dass die Zugabe von diesen Zahlen ist die teuerste Operation in diesem Algorithmus. Es liegt nahe, dass diese zwei Zahlen addieren zusammen müssen wir zusammen 6 Ziffern addieren (und möglicherweise ein siebtes tragen). Wenn wir zwei 100 stellige Zahlen addieren zusammen haben wir 100 Ergänzungen zu tun. Wenn wir zwei 10.000 stellige Zahlen addieren haben wir 10.000 Ergänzungen zu tun.

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

Subtraction ist ähnlich (außer Sie benötigen statt Trag zu leihen).

Die Multiplikation ist unterschiedlich. Sie säumen die Zahlen nach oben, um die ersten Ziffer in der unteren Reihe nehmen und es wiederum gegen jede Ziffer in der oberen Zahl multipliziert und so weiter durch jede Ziffer. Also unsere zwei 6-stellige Zahlen multiplizieren wir 36 Multiplikationen tun müssen. Wir müssen so viele wie 10 oder 11 Spalte tun, fügt auch das Endergebnis zu erhalten.

Wenn wir zwei 100-stelligen Zahlen benötigen wir 10.000 Multiplikationen tun und 200 hinzufügt. Für zwei eine Million stelligen Zahlen brauchen wir eine Billion (10 ¹²) Multiplikationen und zwei Millionen fügt zu tun.

als Algorithmus skaliert mit n- quadrierte , ist dies O (n ²) oder quadratischenKomplexität . Dies ist eine gute Zeit, ein weiteres wichtiges Konzept vorstellen zu können:

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

Der aufmerksame haben erkannt, dass wir die Anzahl der Operationen, wie zum Ausdruck bringen konnte: n ² + 2n. Aber wie Sie aus unserem Beispiel gesehen mit zwei Zahlen von einer Million Ziffern pro Kopf, das zweite Glied (2n) unbedeutend (Anteil von 0,0002% der gesamten Tätigkeiten von dieser Stufe).

Man kann feststellen, dass wir im schlimmsten Fall hier angenommen haben. Während Multiplikation 6-stellige Zahlen, wenn einer von ihnen 4 Ziffer ist und das andere ist 6-stellige, dann haben wir nur 24 Multiplikationen. Noch berechnen wir den schlimmsten Fall für die ‚n‘, das heißt, wenn die beiden 6-stellige Zahlen sind. Daher Big-O-Notation ist über das Worst-Case-Szenario eines Algorithmus

Das Telefonbuch

Das nächste beste Beispiel, das ich denken kann, ist das Telefonbuch, in der Regel des White Pages oder ähnlich genannt, aber es wird von Land zu Land variiert. Aber ich spreche über die eine, die Menschen nach Namen auflistet und dann Initialen oder Vornamen, möglicherweise adressiert und dann Telefonnummern.

Nun, wenn Sie einen Computer wurden anweist, die Telefonnummer für „John Smith“ in einem Telefonbuch zu suchen, die eine Million Namen enthalten, so was würden Sie tun? Das Ignorieren der Tatsache, dass Sie sich vorstellen könnte, wie weit in den Ss gestartet (nehmen wir an, Sie können nicht), was würden Sie tun?

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 passiert, „Smith, John“ zu sein, wir haben nur echtes Glück. Weit wahrscheinlicher ist, dass „John Smith“ vor sein oder nach diesem Namen. Wenn es nach dem wir dann die letzte Hälfte des Telefonbuchs in die Hälfte, und wiederholen Sie unterteilen. Wenn es vor, dann ist teilen wir die erste Hälfte des Telefonbuchs in die Hälfte und zu wiederholen. Und so weiter.

Dies ist eine binäre Suche bezeichnet und wird jeden Tag in der Programmierung verwendet, ob Sie es wahrhaben will oder nicht.

Wenn Sie also einen Namen in einem Telefonbuch von einer Million Namen finden, wollen Sie tatsächlich einen beliebigen Namen, indem Sie diese höchstens 20 mal finden. Suchalgorithmen im Vergleich wir entscheiden, dass dieser Vergleich ist unser ‚n‘.

Für ein Telefonbuch von 3 Namen es dauert 2 Vergleiche (höchstens).

Für 7 es höchstens 3 nimmt.

Für 15 dauert es 4.

...

Für 1.000.000 dauert es 20.

Das ist erstaunlich gut, nicht wahr?

In Big-O Bedingungen ist dies O (log n) oder logarithmische Komplexität . Nun könnte der Logarithmus in Frage ln (Basis e) log ₁₀, log ₂ oder eine andere Basis. Es spielt keine Rolle, es ist immer noch O (log n) wie O (2n ²) und O (100n ²) sind nach wie vor beide O (n ²).

Es ist an dieser Stelle lohnt sich zu erklären, dass Big O drei Fälle mit einem Algorithmus zur Bestimmung verwendet werden können:

Best Case: Im Telefonbuch suchen, ist der beste Fall ist, dass wir den Namen in einem Vergleich finden. Dies ist O (1) oder konstante Komplexität ,

Erwartete Fall: Wie oben beschrieben wird diese O (log n); und

Worst Case:. Dies ist auch O (log n)

Normalerweise nicht kümmern wir uns um die besten Fall. Wir interessieren uns für den erwarteten und schlimmsten Fall. Manchmal eine oder die andere von ihnen wird wichtiger.

Zurück zum Telefonbuch.

Was passiert, wenn Sie eine Telefonnummer haben und wollen einen Namen finden? Die Polizei hat ein Reverse-Telefonbuch aber solche Look-ups sind für die breite Öffentlichkeit verweigert. Oder sind Sie? Technisch gesehen können Sie umkehren eine Nummer in einem gewöhnlichen Telefonbuch Suche. Wie?

Starten Sie beim ersten Namen und die Nummer vergleichen. Wenn es ein Spiel ist, groß, wenn nicht, gehen Sie zum nächsten auf. Sie haben es auf diese Weise beca zu tunverwenden Sie das Telefonbuch ist ungeordnete (durch Telefonnummer sowieso).

So einen Namen der Telefonnummer (Reverse-Lookup) gegeben zu finden:

Best Case: O (1);

Erwartete Fall: O (n) (500.000); und

Sie Worst Case:. O (n) (für 1.000.000)

Handlungsreisende

Dies ist ein sehr bekannt Problem in der Informatik und eine Erwähnung verdient. In diesem Problem haben Sie N Städte. Jede dieser Städte ist mit 1 oder mehreren anderen Städten durch eine Straße von einer gewissen Distanz. Das Reiseproblem ist die kürzeste Tour zu finden, das jede Stadt besucht.

Klingt einfach? Falsch gedacht.

Wenn Sie 3 Städte A, B und C mit Straßen von allen Paaren dann könnte man gehen:

A → B → C

A → C → B

B → C → A

B → A → C

C → A → B

C → B → A

Naja, eigentlich gibt es weniger als das, weil einige von ihnen gleichwertig sind (A → B → C und C → B → A äquivalent sind, zum Beispiel, weil sie die gleichen Straßen benutzen, nur in umgekehrter Reihenfolge).

In Wirklichkeit gibt es 3 Möglichkeiten.

Nehmen Sie dies bis 4 Städten und Sie haben (IIRC) 12 Möglichkeiten.

Mit 5 ist es 60.

6 wird 360.

Dies ist eine Funktion einer mathematischen Operation eines genannt faktorielles . Grundsätzlich gilt:

5! = 5 x 4 x 3 x 2 x 1 = 120

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040

...

25! = 25 × 24 × ... × 2 × 1 = 15,511,210,043,330,985,984,000,000

...

50! = 50 × 49 × ... × 2 × 1 = 3,04140932 × 10 ⁶⁴

So ist das Big-O des Reiseproblems ist O (n!) oder Fakultäts oder kombinatorische Komplexität .

Zu der Zeit, Sie dort zu 200 Städten bekommen, ist nicht genug Zeit im Universum verließ das Problem mit herkömmlichen Computern zu lösen.

Etwas zu denken.

Polynomzeit

Ein weiterer Abschnitt I schnelle Erwähnung machen wollte ist, dass jeder Algorithmus, der eine Komplexität von O hat (n ^a) wird gesagt, haben Polynom Komplexität oder ist auflösbar in Polynomzeit .

O (n), O (n ²) etc. sind alle Polynomzeit. Einige Probleme können nicht in polynomialer Zeit gelöst werden. Bestimmte Dinge sind in der Welt, weil dieser verwendet. Public Key Cryptography ist ein gutes Beispiel. Es ist rechnerisch schwer zwei Primfaktoren einer sehr großen Zahl zu finden. Wenn es nicht war, konnten wir nicht die Public-Key-Systeme verwenden wir verwenden.

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

Andere Tipps

Es zeigt, wie ein Algorithmus Skalen.

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

1 Artikel: 1 Sekunde
10 Stück: 100 Sekunden
100 Artikel: 10000 Sekunden

Beachten Sie, dass die Anzahl der Elemente erhöht sich um den Faktor 10, aber die Zeit erhöht sich um den Faktor 10 ². Im Grunde genommen, n = 10 und so O (n ²) gibt uns den Skalierungsfaktor n ², die 10 ².

O (n) : bekannt als Lineare Komplexität

1 Artikel: 1 Sekunde
10 Stück: 10 Sekunden
100 Artikel: 100 Sekunden

Dieses Mal ist die Anzahl der Elemente erhöht sich um den Faktor 10, und damit auch die Zeit. n = 10 und so O (n) 's Skalierungsfaktor 10.

O (1) : bekannt als Konstante Komplexität

1 Artikel: 1 Sekunde
10 Stück: 1 Sekunde
100 Artikel: 1 Sekunde

Die Anzahl der Elemente immer noch um den Faktor 10 zu erhöhen, aber der Skalierungsfaktor von O (1) ist immer 1.

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

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

Die Anzahl der Berechnungen wird nur von einem Protokoll des Eingangswertes erhöht. Also in diesem Fall jede Berechnung unter der Annahme, 1 Sekunde dauert, ist das Protokoll des Eingang n die erforderliche Zeit, damit log n.

Das ist der Kern von ihm. Sie reduzieren die Mathematik nach unten, so dass es nicht gerade sein könnte n ² oder was auch immer sie sagen, es ist, aber das wird der dominierende Faktor in der Skalierung sein.

Die Big-O-Notation (auch „asymptotische Wachstums“-Notation genannt) ist wie Funktionen „aussehen“, wenn man konstante Faktoren und Dinge in der Nähe des Ursprungs ignoriert.Wir nutzen es, um darüber zu reden wie das Ding skaliert.

Grundlagen

für „ausreichend“ große Eingaben...

f(x) ∈ O(upperbound) bedeutet f „wächst nicht schneller als“ upperbound
f(x) ∈ Ɵ(justlikethis) bedeuten 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“ 10x².Big-O auch nicht asymptotisch Notation wichtig nicht asymptotisch Sachen („Sachen 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?Weil sie von den großen Teilen der Gleichung völlig in den Schatten gestellt werden, wenn man immer größere Maßstäbe betrachtet;Ihr Beitrag wird unbedeutend und irrelevant.(Siehe Beispielabschnitt.)

Anders ausgedrückt: Es geht nur um das Verhältnis wie du in die Unendlichkeit gehst. Wenn man die tatsächlich benötigte Zeit durch die dividiert O(...), erhalten Sie einen konstanten Faktor für die Grenze großer Eingaben. Intuitiv macht das Sinn:Funktionen „skalieren“ einander, wenn man eine multiplizieren kann, um die andere zu erhalten.Das heißt, wenn wir sagen...

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), gibt es eine Konstante (z. B.2.5, komplett zusammengesetzt) so dass:

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

Es gibt viele Auswahlmöglichkeiten für Konstanten;Oft wird die „beste“ Wahl als „konstanter Faktor“ des Algorithmus bezeichnet ...aber wir ignorieren es oft, so wie wir nicht-größte Terme ignorieren (im Abschnitt „Konstante Faktoren“ erfahren Sie, warum sie normalerweise keine Rolle spielen).Sie können sich die obige Gleichung auch als eine Grenze vorstellen und sagen: „Im schlimmsten Fall wird die benötigte Zeit nie schlechter als ungefähr sein N*log(N), innerhalb eines Faktors von 2,5 (ein konstanter Faktor, der uns nicht besonders interessiert)".

Allgemein, O(...) ist am nützlichsten, da wir uns oft um das Worst-Case-Verhalten kümmern.Wenn f(x) stellt etwas „Schlechtes“ wie Prozessor- oder Speicherauslastung dar, dann „f(x) ∈ O(upperbound)" bedeutet "upperbound ist das Worst-Case-Szenario der Prozessor-/Speicherauslastung.“

Anwendungen

Als rein mathematisches Konstrukt beschränkt sich die Big-O-Notation nicht nur auf die Verarbeitungszeit und den Speicher.Sie können es verwenden, um die Asymptotik von allem zu diskutieren, wo Skalierung sinnvoll ist, wie zum Beispiel:

die Anzahl der möglichen Handshakes untereinander N Leute auf einer Party (Ɵ(N²), konkret N(N-1)/2, aber was zählt, ist, dass es „skaliert“ N²)
probabilistisch erwartete Anzahl von Personen, die virales Marketing gesehen haben, als Funktion der Zeit
wie sich die Website-Latenz mit der Anzahl der Verarbeitungseinheiten in einer CPU, GPU oder einem Computercluster skaliert
wie sich die Wärmeabgabe auf CPU-Störungen als Funktion der Transistoranzahl, Spannung usw. skaliert.
wie viel Zeit ein Algorithmus als Funktion der Eingabegröße zum Ausführen benötigt
wie viel Speicherplatz ein Algorithmus als Funktion der Eingabegröße zum Ausführen benötigt

Beispiel

Im obigen Handschlag-Beispiel schüttelt jeder in einem Raum jedem anderen die Hand.In diesem Beispiel, #handshakes ∈ Ɵ(N²).Warum?

Etwas zurücknehmen:die Anzahl der Handshakes beträgt genau n-choose-2 oder N*(N-1)/2 (Jede von N Personen schüttelt N-1 anderen Personen die Hand, aber dadurch werden Handschläge doppelt gezählt, also dividiere durch 2):

Für sehr viele Menschen gilt jedoch der lineare Begriff N ist in den Schatten gestellt und trägt effektiv 0 zum Verhältnis bei (im Diagramm:der Anteil der leeren Kästchen auf der Diagonale an der Gesamtzahl der Kästchen wird kleiner, je größer die Teilnehmerzahl ist).Daher ist das Skalierungsverhalten order N², oder die Anzahl der Handshakes „wächst wie N²“.

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

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

(vorübergehender Exkurs von „plain English“:) Wenn Sie dies selbst beweisen möchten, könnten Sie eine einfache Algebra mit dem Verhältnis durchführen, um es in mehrere Terme aufzuteilen (lim bedeutet „im Rahmen von betrachtet“, ignorieren Sie es einfach, wenn Sie es nicht gesehen haben, es ist nur die 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 sehr nach x² aus, dass wir, wenn wir das Verhältnis #handshakes/x² aufschreiben würden, die Tatsache nicht benötigen genau x²-Handshakes würden für eine beliebig lange Zeit nicht einmal im Dezimalformat angezeigt.

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

Intuition aufbauen

Dadurch können wir Aussagen treffen wie...

„Für eine ausreichend große Eingabegröße=N, unabhängig vom konstanten Faktor, wenn I doppelt die Eingabegröße...

...Ich verdoppele 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, verdoppelt (vervierfacht).“ (z.B.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, verdoppelt (achtfach). (z.B.Ein Problem, das 100x so groß ist, dauert 100³=1000000x so lange ...sehr unhaltbar)

cN³ → c(2N)³ = 8(cN³)
...Ich füge einen festen Betrag zur Zeit hinzu, 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.“ (das günstigste!)

c*1 → c*1
...Ich „verdopple“ (im Grunde) die Zeit, die ein O(N log(N))-Algorithmus benötigt.“ (ziemlich häufig)

es ist kleiner als O(N^1.000001), was man vielleicht grundsätzlich als linear bezeichnen könnte
...Ich erhöhe lächerlicherweise die Zeit eines O(2^N) („exponentielle Zeit“)-Algorithmus dauert.“ (Sie würden die Zeit verdoppeln (oder verdreifachen usw.), wenn Sie das Problem einfach um eine einzige Einheit erhöhen würden.)

2^N → 2^2N = (4^N)............Anders ausgedrückt...... 2^N → 2^N+1 = 2^N2¹ = 2 2^N

[Für Matheinteressierte: Sie können mit der Maus über die Spoiler fahren, um kleinere Nebenbemerkungen zu sehen]

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

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

Dies sind die grundlegenden Wachstumsordnungen, die Programmierern und angewandten Informatikern als Bezugspunkte dienen.Sie sehen diese ständig.(Während man also technisch denken könnte: „Eine Verdoppelung der Eingabe macht einen O(√N)-Algorithmus 1,414-mal langsamer“, ist es besser, sich das so vorzustellen: „Das ist schlechter als logarithmisch, aber besser als linear“.)

Konstante Faktoren

Normalerweise ist es uns egal, was die spezifischen konstanten Faktoren sind, da sie keinen Einfluss auf die Art und Weise haben, wie die Funktion wächst.Beispielsweise können zwei Algorithmen beide verwenden O(N) Zeit bis zur Fertigstellung, aber einer kann doppelt so langsam sein wie der andere.Normalerweise ist es uns egal, es sei denn, der Faktor ist sehr groß, da die Optimierung eine heikle Angelegenheit ist ( Wann ist eine Optimierung verfrüht? );Auch die bloße Auswahl eines Algorithmus mit einem besseren Big-O führt oft zu einer Leistungssteigerung um Größenordnungen.

Einige asymptotisch überlegene Algorithmen (z. B.ein Nichtvergleich O(N log(log(N))) sort) kann einen so großen konstanten Faktor haben (z.B. 100000*N log(log(N))) oder Overhead, der relativ groß ist O(N log(log(N))) mit einem versteckten + 100*N, dass sie sich selbst bei „Big Data“ selten lohnen.

Warum O(N) manchmal das Beste ist, was man tun kann, d.h.Warum wir Datenstrukturen brauchen

O(N) Algorithmen sind in gewisser Weise die „besten“ Algorithmen, wenn Sie alle Ihre Daten lesen müssen.Der sehr Akt des Lesens Eine Menge Daten ist ein O(N) Betrieb.Das Laden in den Speicher erfolgt normalerweise O(N) (oder schneller, wenn Sie Hardware-Unterstützung haben, oder gar keine Zeit, wenn Sie die Daten bereits gelesen haben).Wenn Sie jedoch berühren oder sogar sehen Bei jedem Datenelement (oder sogar bei jedem anderen Datenelement) wird Ihr Algorithmus berücksichtigen O(N) Zeit, diese Suche durchzuführen.Egal wie lange Ihr eigentlicher Algorithmus dauert, es wird mindestens sein O(N) weil es diese Zeit damit verbracht hat, sich alle Daten anzusehen.

Das Gleiche gilt für die sehr Akt des Schreibens.Alle Algorithmen, die N Dinge ausdrucken, benötigen N Zeit, weil 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 den Einsatz von Datenstrukturen:Eine Datenstruktur erfordert nur ein einmaliges Lesen der Daten (normalerweise). O(N) Zeit) plus eine beliebige Menge an Vorverarbeitung (z. B. O(N) oder O(N log(N)) oder O(N²)), die wir versuchen, klein zu halten.Danach nimmt das Ändern der Datenstruktur (Einfügungen/Löschungen usw.) und das Durchführen von Abfragen der Daten nur sehr wenig Zeit in Anspruch, z O(1) oder O(log(N)).Sie stellen dann eine große Anzahl an Abfragen!Im Allgemeinen gilt: Je mehr Arbeit Sie im Voraus leisten möchten, desto weniger Arbeit müssen Sie später erledigen.

Angenommen, Sie verfügen über die Breiten- und Längenkoordinaten von Millionen von Straßensegmenten und möchten alle Straßenkreuzungen finden.

Naive Methode:Wenn Sie die Koordinaten einer Straßenkreuzung hätten und nahegelegene Straßen untersuchen wollten, müssten Sie jedes Mal Millionen von Segmenten durchgehen und jedes einzelne auf Nachbarschaft prüfen.
Wenn Sie dies nur einmal tun müssten, wäre es kein Problem, die naive Methode anwenden zu müssen O(N) Arbeiten Sie nur einmal, aber wenn Sie es mehrmals tun möchten (in diesem Fall, N Mal, einmal für jedes Segment), müssten wir tun O(N²) Arbeit, oder 1000000²=1000000000000 Operationen.Nicht gut (ein moderner Computer kann etwa eine Milliarde Operationen pro Sekunde ausführen).
Wenn wir eine einfache Struktur namens Hash-Tabelle (eine Instant-Speed-Lookup-Tabelle, auch Hashmap oder Wörterbuch genannt) verwenden, zahlen wir einen geringen Preis, indem wir alles vorverarbeiten O(N) Zeit.Danach dauert es im Durchschnitt nur noch eine konstante Zeit, etwas anhand seines Schlüssels nachzuschlagen (in diesem Fall sind unser Schlüssel die Breiten- und Längenkoordinaten, gerundet in ein Gitter);wir durchsuchen die angrenzenden Gitterräume, von denen es nur 9 gibt, was eine Konstante ist).
Unsere Aufgabe ging von einem Undurchführbaren aus O(N²) zu einem überschaubaren O(N), und alles, was wir tun mussten, war, einen geringen Preis zu zahlen, um eine Hash-Tabelle zu erstellen.
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 passender Farbe und Muster.Wir nutzen dies dann aus, um später keine zusätzliche Arbeit zu leisten (den Vergleich von Puzzleteilen gleicher Farbe untereinander und nicht mit jedem anderen einzelnen Puzzleteil).

Die Moral der Geschichte:Mit einer Datenstruktur können wir Abläufe beschleunigen.Mit noch komplexeren Datenstrukturen können Sie Vorgänge auf unglaublich clevere Weise kombinieren, verzögern oder sogar ignorieren.Unterschiedliche Probleme würden unterschiedliche Analogien haben, aber sie alle würden die Organisation der Daten auf eine Weise beinhalten, die eine Struktur ausnutzt, die uns wichtig ist oder die wir ihnen für die Buchhaltung künstlich auferlegt haben.Wir arbeiten im Voraus (im Wesentlichen planen und organisieren), und jetzt sind sich wiederholende Aufgaben viel einfacher!

Praxisbeispiel:Visualisieren von Wachstumsordnungen beim Codieren

Die asymptotische Notation ist im Kern völlig unabhängig von der Programmierung.Die asymptotische Notation ist ein mathematischer Rahmen zum Nachdenken über die Skalierung von Dingen und kann in vielen verschiedenen Bereichen verwendet werden.Das gesagt...So geht es dir anwenden Asymptotische Notation zur Codierung.

Die Grundlagen:Immer wenn wir mit jedem Element in einer Sammlung der Größe A interagieren (z. B. einem Array, einer Menge, allen Schlüsseln einer Karte usw.) oder A-Iterationen einer Schleife durchführen, handelt es sich um einen multiplkativen 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, mal die in der Schleife geleistete Arbeit (oder für Funktionen:die Häufigkeit, mit der Sie die Funktion aufrufen, die Anzahl der in der Funktion geleisteten Arbeit).(Dies gilt, wenn wir nichts Ausgefallenes tun, wie zum Beispiel Schleifen überspringen oder die Schleife vorzeitig verlassen oder den Kontrollfluss in der Funktion basierend auf Argumenten ändern, was sehr häufig vorkommt.) Hier sind einige Beispiele für Visualisierungstechniken mit begleitendem Pseudocode.

(Hier das xs repräsentieren 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 etwas Kompliziertes machen, können Sie sich vielleicht immer 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 dieser Technik, auf die ich hier nicht näher eingehe;es kann dich irreführen.)

Das 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 erkennen, dass die Art und Weise, wie wir Schleifen, Funktionen und Bedingungen mit unseren Daten verknüpfen (Kontrollfluss usw.), die Zeit- und Raumnutzung unseres Programms nachahmt!Wenn die Zeit- und Raumnutzung zu einem Problem wird, dann greifen wir auf Cleverness zurück und finden einen einfachen Algorithmus oder eine Datenstruktur, die wir nicht in Betracht gezogen haben, um die Wachstumsordnung irgendwie zu reduzieren.Dennoch können diese Visualisierungstechniken (obwohl sie nicht immer funktionieren) Ihnen eine naive Vermutung über die Laufzeit im ungünstigsten Fall liefern.

Hier ist noch etwas, was wir visuell erkennen können:

<----------------------------- 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 vielleicht führen Sie log(N) Durchläufe der Daten durch, für O(N*log(N)) Gesamtzeit:

   <----------------------------- 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 davon, aber noch einmal erwähnenswert:Wenn wir einen Hash durchführen (z.B.eine Wörterbuch-/Hashtabellensuche), das ist ein Faktor von O(1).Das ist ziemlich schnell.

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

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

Wenn wir etwas sehr Kompliziertes tun, beispielsweise mit einer rekursiven Funktion oder einem Divide-and-Conquer-Algorithmus, ~~du kannst den ... benutzen Master-Theorem (funktioniert normalerweise), oder in lächerlichen Fällen das Akra-Bazzi-Theorem (funktioniert fast immer)~~ Sie suchen auf Wikipedia nach der Laufzeit Ihres Algorithmus.

Aber Programmierer denken nicht so, denn irgendwann wird die Intuition von Algorithmen einfach zur zweiten Natur.Sie beginnen, etwas Ineffizientes zu programmieren, und denken sofort: „Tue ich etwas?“ völlig ineffizient?".Wenn die Antwort „Ja“ lautet UND Sie davon ausgehen, dass es tatsächlich wichtig ist, können Sie einen Schritt zurücktreten und sich verschiedene Tricks ausdenken, 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 komplizierteres).

Amortisierte und durchschnittliche Fallkomplexität

Es gibt auch die Konzepte „amortisiert“ und/oder „durchschnittlicher Fall“ (beachten Sie, dass diese unterschiedlich sind).

Durchschnittlicher Fall:Dabei handelt es sich lediglich um die Verwendung der Big-O-Notation für den erwarteten Wert einer Funktion und nicht für die Funktion selbst.Im Normalfall, bei dem Sie alle Eingaben als gleich wahrscheinlich betrachten, ist der Durchschnittsfall nur der Durchschnitt der Laufzeit.Zum Beispiel mit Quicksort, auch wenn der Worst-Case der Fall ist O(N^2) Bei einigen wirklich schlechten Eingaben ist der Durchschnittsfall der übliche O(N log(N)) (Die wirklich schlechten Eingaben sind in ihrer Zahl sehr gering, so wenige, dass wir sie im Durchschnitt nicht bemerken.)

Amortisierter Worst-Case:Einige Datenstrukturen können im ungünstigsten Fall eine große Komplexität aufweisen. Wenn Sie jedoch viele dieser Vorgänge ausführen, ist der durchschnittliche Arbeitsaufwand höher als im ungünstigsten Fall.Beispielsweise verfügen Sie möglicherweise über eine Datenstruktur, die normalerweise eine Konstante annimmt O(1) Zeit.Gelegentlich kommt es jedoch zu Schluckauf und dauert O(N) Zeit für eine zufällige Operation, weil vielleicht etwas Buchhaltung oder Müllsammlung oder so etwas nötig ist ...aber es verspricht Ihnen, dass, wenn es zu einem Schluckauf kommt, dieser für N weitere Vorgänge nicht noch einmal auftreten wird.Die Worst-Case-Kosten betragen immer noch O(N) pro Vorgang, sondern die amortisierten Kosten über viele Läufe Ist O(N)/N = O(1) pro Operation.Da die großen Operationen hinreichend selten sind, kann man davon ausgehen, dass die große Menge an Gelegenheitsarbeiten als konstanter Faktor mit dem Rest der Arbeit übereinstimmt.Wir sagen, dass sich die Arbeit über eine ausreichend große Anzahl von Aufrufen „amortisiert“, sodass sie asymptotisch verschwindet.

Die Analogie zur amortisierten Analyse:

Du fährst ein Auto.Gelegentlich müssen Sie 10 Minuten zur Tankstelle verbringen und dann 1 Minute lang den Tank mit Gas nachfüllen.Wenn Sie dies jedes Mal getan haben, wenn Sie mit Ihrem Auto überall hin gingen (10 Minuten lang zur Tankstelle fahren, verbringen Sie ein paar Sekunden damit, einen Bruchteil einer Gallone zu füllen), dies wäre sehr ineffizient.Aber wenn du füllst alle paar Tage den Tank aufzufüllen, die 11 Minuten, die mit der Fahrt zum Tankstelle über eine ausreichend große Anzahl von Fahrten "amortisiert" wird, dass du es ignorieren und so tun kannst, als wären alle deine Fahrten vielleicht 5% länger gewesen.

Vergleich zwischen Durchschnittsfall und amortisiertem Worst-Case:

Durchschnittsfall:Wir treffen einige Annahmen über unsere Eingaben;d.h.Wenn unsere Eingaben unterschiedliche Wahrscheinlichkeiten haben, dann haben unsere Ausgaben/Laufzeiten unterschiedliche Wahrscheinlichkeiten (von denen wir den Durchschnitt bilden).Normalerweise gehen wir davon aus, dass unsere Eingaben alle gleich wahrscheinlich sind (einheitliche Wahrscheinlichkeit), aber wenn die realen Eingaben nicht unseren Annahmen einer „durchschnittlichen Eingabe“ entsprechen, sind die Berechnungen der durchschnittlichen Ausgabe/Laufzeit möglicherweise bedeutungslos.Wenn Sie jedoch mit gleichmäßig zufälligen Eingaben rechnen, ist es sinnvoll, darüber nachzudenken!
Amortisierter Worst-Case:Wenn Sie eine amortisierte Worst-Case-Datenstruktur verwenden, liegt die Leistung garantiert innerhalb des amortisierten Worst-Case-Bereichs ...irgendwann (auch wenn die Eingaben von einem bösen Dämon ausgewählt werden, der alles weiß und versucht, dich zu verarschen).Normalerweise verwenden wir dies, um Algorithmen zu analysieren, deren Leistung mit unerwartet großen Einbußen sehr „abgehackt“ sein kann, die aber im Laufe der Zeit genauso gut funktionieren wie andere Algorithmen.(Solange Ihre Datenstruktur jedoch keine Obergrenzen für viele ausstehende Arbeiten aufweist, die sie gerne aufschieben würde, könnte ein böser Angreifer Sie möglicherweise dazu zwingen, die maximale Menge an aufgeschobener Arbeit auf einmal nachzuholen.

Allerdings, wenn ja einigermaßen besorgt Wenn es um einen Angreifer geht, gibt es neben Amortisation und Average-Case noch viele andere algorithmische Angriffsvektoren, über die man sich Sorgen machen muss.)

Sowohl die Durchschnittsrechnung als auch die Amortisation sind äußerst nützliche Werkzeuge zum Nachdenken und Entwerfen unter Berücksichtigung der Skalierung.

(Sehen Unterschied zwischen Durchschnittsfall und amortisierter Analyse bei Interesse an diesem Unterthema.)

Mehrdimensionales Big-O

Meistens ist den Menschen nicht bewusst, dass mehr als eine Variable am Werk ist.Beispielsweise kann Ihr Algorithmus bei einem String-Suchalgorithmus einige Zeit in Anspruch nehmen O([length of text] + [length of query]), d.h.es ist linear in zwei Variablen wie O(N+M).Andere, naivere Algorithmen könnten es sein O([length of text]*[length of query]) oder O(N*M).Das Ignorieren mehrerer Variablen ist eines der häufigsten Versäumnisse, 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 Cache-unabhängig machen, Engpässe vermeiden, indem Sie mit RAM statt mit Festplatte arbeiten, Parallelisierung verwenden oder Arbeiten im Voraus erledigen – diese Techniken sind häufig unabhängig der „Big-O“-Notation der Reihenfolge des Wachstums, obwohl Sie häufig die Anzahl der Kerne in der Big-O-Notation paralleler Algorithmen sehen werden.

Bedenken Sie auch, dass Ihnen asymptotisches Verhalten aufgrund versteckter Einschränkungen Ihres Programms möglicherweise nicht wirklich wichtig ist.Möglicherweise arbeiten Sie mit einer begrenzten Anzahl von Werten, zum Beispiel:

Wenn Sie etwa 5 Elemente sortieren, sollten Sie nicht die schnelle Methode verwenden O(N log(N)) schnelle Sorte;Sie möchten die Einfügungssortierung 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, beispielsweise bei rekursiver Sortierung, schnellen Fourier-Transformationen oder Matrixmultiplikation.
Wenn einige Werte aufgrund einer verborgenen Tatsache effektiv begrenzt sind (z. B.Der durchschnittliche menschliche Name ist auf etwa 40 Buchstaben begrenzt, und das Alter des Menschen liegt bei etwa 150.Sie können Ihrer Eingabe auch Grenzen setzen, um Terme effektiv konstant zu halten.

Selbst bei Algorithmen mit gleicher oder ähnlicher asymptotischer Leistung kann ihr relativer Wert in der Praxis tatsächlich von anderen Dingen bestimmt werden, wie zum Beispiel:andere Leistungsfaktoren (Quicksort und Mergesort sind beides). O(N log(N)), aber Quicksort nutzt CPU-Caches aus);Nichterfüllungsaspekte, wie z. B. einfache Implementierung;ob eine Bibliothek verfügbar ist und wie seriös und gepflegt die Bibliothek ist.

Außerdem laufen Programme 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 im Hinblick auf Maschinenressourcen (z. B.pro Taktzyklus), nicht pro realer Sekunde.Es gibt jedoch ähnliche Dinge, die sich „heimlich“ auf die Leistung auswirken können, z. B. ob Sie unter Emulation arbeiten oder ob der Compiler den Code optimiert hat oder nicht.Dies kann dazu führen, dass einige Grundoperationen länger dauern (sogar relativ zueinander) oder dass einige Operationen sogar asymptotisch beschleunigt oder verlangsamt werden (sogar relativ zueinander).Der Effekt kann je nach Implementierung und/oder Umgebung klein oder groß sein.Wechseln Sie die Sprache oder die Maschine, um die kleine zusätzliche Arbeit zu erledigen?Das hängt von hundert anderen Gründen ab (Notwendigkeit, Fähigkeiten, Kollegen, Programmierproduktivität, Geldwert Ihrer Zeit, Vertrautheit, Problemumgehungen, warum nicht Montage oder GPU usw.), die möglicherweise wichtiger sind als die Leistung.

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

(bearbeiten:Die Erklärung in „einfachem Englisch“ 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 nach oben durch const*g begrenzt ist“:Ignoriert man alles unterhalb eines endlichen Werts von x, gibt es eine solche Konstante |f(x)| ≤ const * |g(x)|.(Die anderen Symbole lauten wie folgt:so wie O bedeutet ≤, Ω bedeutet ≥.Es gibt Kleinbuchstabenvarianten: o bedeutet <, und ω bedeutet >.) 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 immer im „Band“ dazwischen liegt const1*g(x) Und const2*g(x).Es ist die stärkste asymptotische Aussage, die Sie machen können, und entspricht in etwa dieser ==.(Aus Gründen der Klarheit habe ich mich entschieden, die Erwähnung der Absolutwertsymbole bis jetzt zu verschieben.)vor allem, weil ich im Informatikkontext noch nie negative Werte gesehen habe.)

Die Leute werden es oft benutzen = O(...), was vielleicht die korrektere „comp-sci“-Notation ist und deren Verwendung völlig legitim ist;„f = O(...)“ lautet „f ist Ordnung ...“/ f ist xxx-begrenzt durch ...“ und wird als „f ist ein Ausdruck, dessen Asymptotik ...“ ist, betrachtet.Mir wurde beigebracht, das strengere anzuwenden ∈ O(...). ∈ bedeutet „ist ein Element von“ (immer noch wie zuvor gelesen). O(N²) ist eigentlich ein Äquivalenzklasse, Das heißt, es handelt sich um eine Menge von Dingen, die wir für gleich halten.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 dennoch eine Menge.Der = Die Notation dürfte die gebräuchlichere sein und wird sogar in Arbeiten weltbekannter Informatiker verwendet.Darüber hinaus kommt es oft vor, dass die Leute in einer ungezwungenen Atmosphäre sagen O(...) wenn sie meinen Ɵ(...);Dies ist technisch gesehen seit der Reihe der Dinge wahr Ɵ(exactlyThis) ist eine Teilmenge von O(noGreaterThanThis)...und es ist einfacher zu tippen.;-)

EDIT: Kurze Notiz, das ist fast sicher verwirrend Big O-Notation (die eine obere ist gebunden ist) mit Theta-Notation (das ist sowohl eine obere und untere Grenze). Nach meiner Erfahrung ist dies eigentlich typisch für Diskussionen in nicht-akademischem Umfeld. Entschuldigen uns für die Verwirrung verursacht.

In einem Satz: Da die Größe Ihrer Arbeit nach oben geht, wie lange dauert es, um es zu vervollständigen

Natürlich nur das ist mit „Größe“ als Eingang und „Zeit genommen“ als Ausgabe -. Die gleiche Idee gilt, wenn Sie über die Speichernutzung sprechen wollen etc

Hier ist ein Beispiel, wo wir N T-Shirts haben, die wir trocknen wollen. Wir werden übernehmen es ist unglaublich schnell sie in der Trocknungsposition zu erhalten (das heißt die menschliche Interaktion vernachlässigbar ist). Das ist nicht der Fall, im wirklichen Leben, natürlich ...

eine Wäscheleine außerhalb verwenden: vorausgesetzt, Sie einen unendlich großen Hinterhof haben, Waschen trocknet in O (1) Zeit. Doch viel Sie davon haben, wird es die gleiche Sonne und frische Luft, so dass die Größe nicht die Trocknungszeit nicht beeinträchtigt wird.
einen Wäschetrockner verwenden: Sie setzen 10 Hemden in jeder Last, und dann sind sie eine Stunde später fertig. (Ignorieren Sie die tatsächlichen Zahlen hier -. Sie sind irrelevant). So Trocknen 50 Shirts nimmt über 5 mal so lang wie Trocknen 10 Shirts
alles in einem Trockenschrank Putting: Wenn wir alles in einem großen Haufen gelegt und lassen Sie nur allgemeine Wärme es tut, wird es eine lange Zeit für die mittleren Shirts zu bekommen trocken nehmen. Ich würde nicht im Detail zu erraten, wie, aber ich vermute, das ist zumindest O (N ^ 2) -., Wie Sie die Waschladung zu erhöhen, schneller die Trocknungszeit erhöht

Ein wichtiger Aspekt der „großes O“ Notation ist, dass es nicht sagen, welcher Algorithmus schneller für eine bestimmte Größe sein wird. Nehmen Sie eine Hash-Tabelle (String key, ganzzahligen Wert) vs einem Array von Paaren (string, integer). Ist es schneller einen Schlüssel in der Hash-Tabelle oder ein Element in dem Array zu finden, basierend auf einer Schnur? (Dh für das Array „das erste Element finden, wo der Zeichenfolge Teil des angegebenen Schlüssel übereinstimmt.“) Hashtables werden in der Regel amortisieren (~ = „im Durchschnitt“) O (1) - sobald sie eingerichtet hat, soll es nehmen die gleichzeitig einen Eintrag in einer 100-Eintragstabelle wie in einer Million Eintragstabelle zu finden. ein Element in einem Array zu finden (basierend auf dem Inhalt und nicht Index) ist linear, das heißt O (N) -. im Schnitt wirst du bei der Hälfte der Einträge suchen müssen

Ist dies eine Hash-Tabelle macht schneller als ein Array für Lookups? Nicht unbedingt. Wenn Sie eine sehr kleine Sammlung von Einträgen haben, kann ein Array auch schneller sein - Sie in der Lage sein können, alle Fäden in der Zeit zu prüfen, die es braucht, um nur den Hash-Code des einen zu berechnen, bei der Sie suchen. Da die Datenmenge größer wird, jedoch wird die Hash-Tabelle schließlich das Array schlagen.

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

Beispiele:

O (n): Wenn ich die Eingangsgröße der Laufzeit verdoppelt verdoppeln
O (n ²): Wenn die Eingangsgröße verdoppelt sich die Laufzeit vervierfacht
O (log n): Wenn die Eingangsgröße die Laufzeit erhöht sich um eins verdoppelt
O (2 ⁿ): Wenn die Eingangsgröße erhöht sich um eine, die Laufzeit verdoppelt

Die Eingangsgröße ist in der Regel der Raum in Bits erforderlich, um die Eingabe zu repräsentieren.

Big O-Notation wird am häufigsten von den Programmierern als ungefähres Maß dafür, wie lange eine Berechnung (Algorithmus) in Abhängigkeit von der Größe des Eingangs eingestellt wird, um abzuschließen, ausgedrückt.

Big O ist nützlich, um zu vergleichen, wie gut zwei Algorithmen skalieren als die Anzahl der Eingänge erhöht.

Genauer gesagt Big O-Notation verwendet wird, um das asymptotische Verhalten einer Funktion zum Ausdruck bringen. Das bedeutet, dass, wie die Funktion verhält, wie es unendlich geht.

In vielen Fällen sind das „O“ einen Algorithmus fällt in einer der folgenden Fälle:

O (1) - Zeit zu vervollständigen ist die gleiche, unabhängig von der Größe der Eingabe gesetzt. Ein Beispiel ist ein Array-Element durch den Index zugreift.
O (Log N) - Zeit erhöht abzuschließen etwa im Einklang mit dem log2 (n). Zum Beispiel 1024 Artikel dauern etwa doppelt so lang wie 32 Elemente, weil Log2 (1024) = 10 und Log2 (32) = 5. Ein Beispiel findet ein Element in einem binärer Suchbaum (BST).
O (N) - Zeit zu vervollständigen, die linear mit der Größe des Eingangsskala eingestellt. Mit anderen Worten, wenn Sie die Anzahl der Elemente in dem Eingabesatz verdoppeln, nimmt der Algorithmus etwa doppelt so lang. Ein Beispiel ist das Zählen der Anzahl von Elementen in einer verknüpften Liste.
O (N log N) - Zeit erhöht sich die Anzahl der Elemente mal das Ergebnis von Log2 (N) in Anspruch nehmen. Ein Beispiel hierfür ist Haufen sortieren und schnell sortieren .
O (N ^ 2) - Zeit abzuschließen etwa gleich dem Quadrat der Anzahl der Elemente ist. Ein Beispiel hierfür ist Blase sortieren .
O (N!) - Zeit zu vollenden ist die Fakultäts des Eingangs eingestellt. Ein Beispiel hierfür ist die Verkäufer Problem Brute-Force-Lösung reisen.

Big O ignoriert Faktoren, die sich nicht auf die Wachstumskurve einer Funktion als Eingangsgröße steigt ins Unendliche in einer sinnvollen Art und Weise beitragen. Dies bedeutet, dass Konstanten, die addiert oder multipliziert mit der Funktion werden einfach ignoriert.

Big O ist nur eine Möglichkeit, „Express“, sich in einem gemeinsamen Weg: „Wie viel Zeit / Raum dauert es meinen Code ausführen?“.

Sie können oft sehen, O (n), O (n ²), O (n log n) und so weiter, all dies sind nur Wege zu zeigen; Wie funktioniert ein Algorithmus ändern?

O (n) bedeutet, Big O n ist, und jetzt werden Sie vielleicht denken: "Was n !?" Well „n“ ist die Menge der Elemente. Imaging Sie nach einem Element in einem Array gesucht werden soll. Sie würden auf jedem Element suchen und als „Sind Sie das richtige Element / Element?“ im schlimmsten Fall ist der Punkt auf dem letzten Index, was bedeutet, dass es so viel Zeit in Anspruch nahm, da es Elemente in der Liste sind, so generisch sein, sagen wir: „Oh hey, n ist eine faire gegebene Menge von Werten!“ .

Also dann könnten Sie verstehen, was „n ²“ bedeutet, aber noch spezifischere, spielt mit dem Gedanken, Sie haben eine einfache, die einfachste der Sortieralgorithmen zu sein; Bubblesort. Dieser Algorithmus muss durch die gesamte Liste suchen, für jedes Element.

Meine Liste

Die Strömung hier wäre:

Vergleichen Sie die 1 und 6, die größte? Ok 6 ist in der richtigen Position, bewegt sich vorwärts!
Vergleichen 6 und 3, oh, 3 weniger! Lassen Sie uns das bewegen, Ok die Liste geändert haben, müssen wir nun von Anfang an beginnen!

Das ist O n ², da müssen Sie auf alle Elemente in der Liste zu sehen gibt es "n" Elemente. Für jedes Element, schauen Sie auf alle Artikel noch einmal, zum Vergleich, ist dies auch "n", so dass für jedes Einzelteil, Sie schauen "n" mal n * bedeutet, n = n ²

Ich hoffe, das so einfach ist, wie Sie es wollen.

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

Big O beschreibt die grundlegende Skalierungsnatur eines Algorithmus.

Es gibt viele Informationen, die Ihnen Big O über einen bestimmten Algorithmus nicht mitteilt.Es geht auf den Punkt und liefert nur Informationen über die Skalierungsart eines Algorithmus, insbesondere darüber, wie sich die Ressourcennutzung (Denkzeit oder Speicher) eines Algorithmus als Reaktion auf die „Eingabegröße“ skaliert.

Bedenken Sie den Unterschied zwischen einer Dampfmaschine und einer Rakete.Es handelt sich dabei nicht lediglich um unterschiedliche Varianten derselben Sache (wie beispielsweise ein Prius-Motor vs.ein Lamborghini-Motor), aber im Kern handelt es sich um völlig unterschiedliche Arten von Antriebssystemen.Eine Dampfmaschine mag schneller sein als eine Spielzeugrakete, aber keine Dampfkolbenmaschine wird die Geschwindigkeiten einer Orbitalrakete erreichen können.Dies liegt daran, dass diese Systeme unterschiedliche Skalierungseigenschaften hinsichtlich des Verhältnisses des erforderlichen Kraftstoffs („Ressourcenverbrauch“) zum Erreichen einer bestimmten Geschwindigkeit („Eingabegröße“) aufweisen.

Warum ist das so wichtig?Denn Software befasst sich mit Problemen, deren Größe sich um Faktoren bis zu einer Billion unterscheiden kann.Denken Sie einen Moment darüber nach.Das Verhältnis zwischen der Geschwindigkeit, die für die Reise zum Mond erforderlich ist, und der Gehgeschwindigkeit des Menschen beträgt weniger als 10.000:1, und das ist absolut winzig im Vergleich zu den Eingabegrößen, denen Software ausgesetzt sein kann.Und weil Software mit einer astronomischen Bandbreite an Eingabegrößen konfrontiert sein kann, besteht das Potenzial, dass die Big-O-Komplexität eines Algorithmus, seine grundlegende Skalierungsnatur, alle Implementierungsdetails übertrifft.

Betrachten Sie das kanonische Sortierbeispiel.Blasensortierung ist O(n²), während Merge-Sort O(n log n) ist.Nehmen wir an, Sie haben zwei Sortieranwendungen, Anwendung A, die Bubble-Sort verwendet, und Anwendung B, die Merge-Sort verwendet, und nehmen wir an, dass Anwendung A bei Eingabegrößen von etwa 30 Elementen 1.000-mal schneller sortiert als Anwendung B.Wenn Sie nie viel mehr als 30 Elemente sortieren müssen, ist es offensichtlich, dass Sie Anwendung A bevorzugen sollten, da diese bei diesen Eingabegrößen viel schneller ist.Wenn Sie jedoch feststellen, dass Sie möglicherweise zehn Millionen Elemente sortieren müssen, erwarten Sie, dass Anwendung B in diesem Fall tatsächlich Tausende Male schneller ist als Anwendung A, was ausschließlich auf die Art und Weise zurückzuführen ist, wie jeder Algorithmus skaliert.

Hier ist die plain English Bestiarium ich verwenden neigen, wenn die gemeinsame Sorten von Big-O erklärt

In allen Fällen bevorzugen Algorithmen höher auf der Liste zu denen weiter unten auf der Liste. Allerdings variiert erheblich die Kosten für ein teureres Komplexitätsklasse zu bewegen.

O (1):

Kein Wachstum. Unabhängig davon, wie groß, wie das Problem ist, können Sie es in der gleichen Menge an Zeit lösen. Dies ist etwas analog zu Rundfunk, wo es die gleiche Menge an Energie nimmt einen bestimmten Abstand zur Ausstrahlung über, und zwar unabhängig von der Anzahl der Menschen, die innerhalb des Sendebereichs liegen.

O (log n ):

Diese Komplexität ist die gleiche wie O (1) , außer, dass es nur ein wenig schlechter. Für alle praktischen Zwecke, können Sie dies als eine sehr große Konstante Skalierung berücksichtigen. Der Unterschied in der Arbeit zwischen den Verarbeitungs 1000 und 1 Milliarde Artikeln ist nur ein Faktor sechs.

O ( n ):

Die Kosten für das Problem zu lösen, sind auf die Größe des Problems proportional. Wenn Ihr Problem in der Größe verdoppelt, dann die Kosten der Lösung verdoppelt. Da die meisten Probleme in irgendeine Weise in den Computer gescannt haben, wie Dateneingabe, Datenträger lesen oder den Netzwerkverkehr, dies ist in der Regel ein kostengünstiger Skalierungsfaktor ist.

O ( n log n ):

Diese Komplexität ist sehr ähnlich wie O ( n ) . Für alle praktischen Zwecke sind die beiden gleichwertig. Dieser Grad an Komplexität der Regel noch skalierbar angesehen werden würde. Durch Tweaking Annahmen etwas O ( n log n ) Algorithmen können in umgewandelt werden O ( n ) Algorithmen. Zum Beispiel Begrenzung der Größe der Tasten reduziert Sortier von O ( n log n ) O ( n ) .

O ( n ²):

wächst als Quadrat, wobei n ist die Länge der Seite eines Quadrats. Dies ist die gleiche Wachstumsrate wie der „Netzwerk-Effekt“, wo jeder in einem Netzwerk könnte all andere im Netzwerk kennen. Das Wachstum ist teuer. Die meisten skalierbare Lösungen können nicht mit dieser Komplexität nutzen Algorithmen ohne signifikante turnen. Dies gilt generell für alle anderen Polynom Komplexitäten - O ( n ^k) -. Auch

O (2 ⁿ):

nicht skaliert wird. Sie haben keine Hoffnung auf jedes nicht-triviale Größe Problem zu lösen. Nützlich zu wissen, was zu vermeiden und für Experten ungefähre Algorithmen zu finden, die in sind O ( n ^k) .

Big O ist ein Maß dafür, wie viel Zeit / Raum ein Algorithmus auf die Größe seiner Eingabe relativ verwendet.

Wenn ein Algorithmus ist O (n), dann ist die Zeit / Raum wird mit der gleichen Geschwindigkeit wie sein Eingang erhöhen.

Wenn ein Algorithmus ist O (n ²), wird die Zeit / Raum Erhöhung bei der Rate von seinem Eingang zum Quadrat.

und so weiter.

Es ist sehr schwierig, die Geschwindigkeit von Softwareprogrammen zu messen, und wenn wir versuchen, können die Antworten sehr komplex und mit Ausnahmen und Sonderfällen gefüllt. Dies ist ein großes Problem, denn all diese Ausnahmen und Sonderfälle sind störend und nicht hilfreich, wenn wir zwei verschiedene Programme miteinander, um herauszufinden, vergleichen wollen, die „schnellste“.

Als Ergebnis all diesen nicht hilfreich Komplexität, die Menschen versuchen, die Geschwindigkeit der Software-Programme zu beschreiben Ausdrücke mit den kleinsten und am wenigsten komplexen (mathematischen) möglich. Diese Ausdrücke sind sehr sehr grobe Annäherungen. Obwohl, mit etwas Glück, werden sie das „Wesen“ der Erfassung, ob ein Stück Software ist schnell oder langsam

Weil sie Annäherungen sind, verwenden wir die Buchstaben „O“ (Big Oh) im Ausdruck, als Konvention für den Leser zu signalisieren, dass wir eine grobe Vereinfachung machen. (Und um sicherzustellen, dass niemand fälschlicherweise glaubt, dass der Ausdruck in keiner Weise korrekt sind).

Wenn Sie den „Oh“ im Sinne von „in der Größenordnung von“ oder „ungefähr“ lesen gehen Sie nicht zu viel falsch. (Ich glaube, die Wahl des Big-Oh könnte ein Versuch, Humor gewesen).

Das einzige, was diese „Big-Oh“ Ausdrücke versuchen zu tun ist, zu beschreiben, wie sehr die Software verlangsamt, wie wir die Datenmenge zu erhöhen, dass die Software zu verarbeiten hat. Wenn wir die Datenmenge verdoppelt, die verarbeitet werden muss, wird die Software zweimal braucht so lange zu beenden es Arbeit ist? Zehn Mal so lange? In der Praxis gibt es eine sehr begrenzte Anzahl von Big-Oh Ausdrücke, die auftreten und benötigen zur Sorge:

Die gute:

O(1) Konstante . Das Programm nimmt die gleiche Zeit, egal zu laufen, wie groß die Eingabe
O(log n) logarithmisch . Das Programm-Laufzeit erhöht sich nur langsam, auch mit großen Steigerungen der Größe der Eingabe

Die schlechte:

O(n) Linear . Das Programm-Laufzeit erhöht sich proportional zur Größe des Eingangs
O(n^k) Polynomial : -. Bearbeitungszeit wächst schneller und schneller - als Polynom-Funktion - wie die Größe des Eingangs verlängert

... und das hässliche:

O(k^n) Exponential Das Programm-Laufzeit erhöht sich sehr schnell mit noch moderaten Anstieg der Größe des Problems -. Es nur praktisch ist, kleine Datenmengen mit exponentiellen Algorithmen zu verarbeiten
O(n!) Factorial Die Programm-Laufzeit wird länger, als Sie für alles anderes als die sehr kleinsten und trivial anmutende Datensätze warten leisten können.

Was ist eine einfache englische Erklärung von Big O? Mit so wenig formalen Definition wie möglich und einfache Mathematik.

A Plain English Erklärung der Need für Big-O-Notation:

Wenn wir programmieren, wir versuchen, ein Problem zu lösen. Was wir Code ist ein Algorithmus genannt. O-Notation erlaubt es uns, die ungünstigste Leistung unserer Algorithmen in standardisierter Weise zu vergleichen. Hardware-Spezifikationen variieren im Laufe der Zeit und Verbesserungen bei der Hardware reduzieren die Zeit kann es eine Algorithmen auszuführen dauert. Aber die Hardware zu ersetzen, bedeutet nicht, unseren Algorithmus ist besser oder im Laufe der Zeit verbessert, da der Algorithmus immer noch das gleiche ist. Also, um uns zu erlauben, verschiedene Algorithmen zu vergleichen, um zu bestimmen, wenn man besser ist oder nicht, verwenden wir Big O-Notation.

A Plain English Erklärung von Was Big O Notation ist:

Nicht alle Algorithmen laufen in der gleichen Menge an Zeit und können sich auf die Anzahl der Elemente in der Eingabe variieren, die wir nennen wollen n . Auf dieser Grundlage betrachten wir die Worst-Case-Analyse oder eine Obergrenze der Laufzeit als n erhält größer und größer. Wir müssen wissen, was n ist, weil viele der Big O Bezeichnungen verweisen sie.

Eine einfache, klare Antwort kann sein:

Big O steht für die denkbar schlechteste Zeit / Raum für diesen Algorithmus. Der Algorithmus nimmt nie mehr Raum / Zeit oberhalb dieser Grenze. Big O steht für Zeit / Raum-Komplexität im Extremfall.

Ok, mein 2cents.

Big-O ist Steigerungsrate der Ressource durch das Programm verbraucht, w.r.t. Problem-Instanz-size

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

sagen, das Problem ist "Finden Sie die Summe",

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

      return sum;
}

Problem instance = {5,10,15} ==> Probleminstanz size = 3, Iterationen-in-loop = 3

Problem instance = {5,10,15,20,25} ==> Probleminstanz size = 5 Iterationen-in-loop = 5

Für die Eingabe der Größe „n“ Das Programm wird bei einer Geschwindigkeit von „n“ Iterationen in Array wächst. Daher Big-O ist N als O ausgedrückt (n)

sagen, das Problem ist "Finden Sie die Kombination",

    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} ==> Probleminstanz size = 3, Gesamt-Iterationen = 3 * 3 = 9

Problem instance = {5,10,15,20,25} ==> Problem Instanz-size = 5, Gesamt-Iterationen = 5 * 5 = 25

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

Big O-Notation ist eine Möglichkeit, die obere Grenze eines Algorithmus der Beschreibung in Bezug auf Raum oder Zeit. Die n die Anzahl der Elemente in dem das Problem (das heißt Größe eines Arrays, die Anzahl der Knoten in einem Baum, etc.) Wir sind daran interessiert, bei der Beschreibung die Laufzeit als n wird groß.

Wenn wir sagen, einige Algorithmus O (f (n)) sagen wir, dass die Laufzeit (oder Raum), ausgestellt von diesem Algorithmus ist immer niedriger als einige konstante Zeiten f (n).

sagen, dass binäre Suche eine Laufzeit von O (log n) hat, ist zu sagen, dass es eine Konstante c existiert, die Sie log (n) durch, dass sich vermehren kann, wird immer größer sein als die Laufzeit der binären Suche. In diesem Fall werden Sie immer einen konstanten Faktor von log (n) Vergleiche haben.

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

" Was ist eine einfache englische Erklärung von Big O? Mit so wenig formalen Definition wie möglich und einfache Mathematik. "

Eine solche wunderschön einfache und kurze Frage scheint zumindest eine ebenso kurze Antwort zu verdienen, wie ein Student während Nachhilfe erhalten könnten.

Big O-Notation einfach sagt, wie viel Zeit * ein Algorithmus innerhalb laufen kann, in Bezug auf die nur die Menge der Eingangsdaten **.

(* in einem wunderbaren, unit frei Zeitgefühl!)
(**, das ist, worauf es ankommt, weil die Leute werden immer wollen mehr , ob sie leben heute oder morgen)

Nun, was ist so wunderbar Notation Big O, wenn das ist, was es tut

Praktisch gesprochen, Big O-Analyse ist so nützlich und wichtig , weil Big O den Fokus eindeutig auf den Algorithmus setzt eigene Komplexität und vollständig ignoriert alles, was lediglich eine Proportionalitätskonstante artig ein JavaScript-Engine, die Geschwindigkeit einer CPU, die Internetverbindung, und all die Dinge, die sich schnell zu werden, wie lächerlich veraltet als Modell T ist. Big O auf Leistung konzentriert sie nur in der Art und Weise, die ebenso so viele Menschen zählt, leben in der Gegenwart oder in der Zukunft.
Big O-Notation scheint auch ein Schlaglicht direkt auf dem wichtigsten Prinzip der Computer-Programmierung / Engineering, die Tatsache, die alle guten Programmierer inspiriert Denken zu halten und zu träumen: den einzigen Weg, um Ergebnisse über das langsame Voranschreiten erreichen von Technologie ist zu erfinden einen besseren Algorithmus .

Algorithm Beispiel (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;
}

Programmbeschreibung:

Dieser Algorithmus eine Liste suchen, Stück für Stück, nach einem Schlüssel suchen,
Iterieren auf jedes Element in der Liste, wenn es der Schlüssel dann true zurück,
Wenn die Schleife ohne Suche nach dem Schlüssel beendet ist, kehrt Falsch.

Big-O-Notation repräsentiert die obere Schranke für die Komplexität (Zeit, Raum, ..)

zu dem Big-O auf Zeitkomplexität zu finden:

Berechnen Sie, wie viel Zeit (in Bezug auf Eingangsgröße) im schlimmsten Fall nimmt:
Worst Case:. Der Schlüssel existiert nicht in der Liste
Time (Worst Case) = 4 n + 1
Zeit: O (4 n + 1) = O (n) | in Big-O, sind Konstanten vernachlässigt
O (n) ~ Linear

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

Best-Case. Der Schlüssel ist das erste Element
Time (Best-Case) = 4
Zeit: Ω (4) = O (1) ~ Sofort \ Konstante

Big O

f (x) = O ( g (x)), wenn x geht zu einem (beispielsweise a = + ∞) bedeutet, dass es eine Funktion ist, < em> k , so dass:

f (x) = k (x) g (x)
k ist in einer Umgebung von a begrenzt (wenn a = + ∞, bedeutet dies, dass es Zahlen N und M, so dass für jeden x> N, | k (x) |

Mit anderen Worten, in einfachem Englisch: f (x) = O ( g (x)), x → a, bedeutet, dass in einer Umgebung von a, f zerfällt in das Produkt von g und einige beschränkte Funktion.

Kleines o

übrigens, hier ist zum Vergleich der Definition des kleinen os.

f (x) = o ( g (x)), wenn x zu einer Einrichtung geht, dass es eine Funktion k, so dass:

f (x) = k (x) g (x)
k (x) geht auf 0, wenn x 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 → + ∞.

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

Weitere Beispiele

O (1) = O (n) = O (n ²), wenn n → + ∞ (aber nicht umgekehrt, die Gleichheit ist "fake"),
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

Big O-Notation ist eine Art und Weise zu beschreiben, wie schnell ein Algorithmus, eine beliebige Anzahl von Eingabeparametern gegeben laufen, was wir „n“ nennen. Es ist in der Informatik sinnvoll, da unterschiedliche Maschinen mit unterschiedlichen Geschwindigkeiten arbeiten und einfach zu sagen, dass ein Algorithmus 5 Sekunden dauern Ihnen nicht viel sagen, weil, während Sie ein System mit einem 4,5 Ghz octo-Core-Prozessor ausgeführt werden können, kann ich laufen ein 15 Jahre alt, 800 Mhz-System, das länger unabhängig vom Algorithmus nehmen könnte. Anstatt also die Angabe, wie schnell ein Algorithmus in Bezug auf die Zeit abläuft, sagen wir, wie schnell läuft es in Bezug auf die Anzahl von Eingabeparametern, oder „n“. Durch die Beschreibung Algorithmen auf diese Weise sind wir in der Lage, die Geschwindigkeiten von Algorithmen zu vergleichen, ohne zu berücksichtigen, die die Geschwindigkeit des Computers selbst.

Nicht sicher, ob ich weiter bin zu dem Thema beitragen, aber immer noch dachte, ich würde Aktie: Ich habe mal dieses Blog-Post einige sehr hilfreich haben (wenn auch sehr einfach) Erklärungen und Beispiele auf Big O:

Via Beispielen, half dies die nackten Grundlagen in mein Schildpatt-ähnlichen Schädel zu bekommen, so dass ich denke, es ist eine ziemlich Abstieg 10 Minuten lesen Sie in der richtigen Richtung zu gehen.

Sie möchten wissen, alles, was man von großen O wissen? Also tue ich.

So zu reden von großen O, werde ich Wörter, die in ihnen nur einen Schlag haben. Ein Ton pro Wort. Kleine Worte sind schnell. Sie kennen diese Worte, und ich so tun wir Wörter mit einem Sound verwenden. Sie sind klein. Ich bin sicher, dass Sie alle die Worte wissen wir verwenden werden!

Jetzt wollen wir dich und mich von der Arbeit sprechen. Die meiste Zeit, ich weiß nicht wie Arbeit. Mögen Sie Arbeit? Es kann der Fall sein, die Sie tun, aber ich bin sicher, dass ich dies nicht tun.

Ich mag gehen nicht zur Arbeit. Ich mag keine Zeit bei der Arbeit verbringen. Wenn es nach mir ginge, würde Ich mag zu spielen, nur um, und Spaß Dinge tun. Fühlen Sie das gleiche wie ich tun?

Jetzt manchmal, ich gehen müssen, um zu arbeiten. Es ist traurig, aber wahr. Also, wenn ich bei der Arbeit bin, habe ich eine Regel: Ich versuche, weniger Arbeit zu tun. Da in der Nähe keine Arbeit, wie ich kann. Dann gehe ich spielen!

So, hier ist die große Neuigkeit: die große O mir nicht tun helfen können! Ich kann mehr der Zeit spielen, wenn ich große O. Weniger Arbeit weiß, mehr spielen! Das ist, was großes O hilft mir zu tun.

Nun habe ich einige Arbeit. Ich habe diese Liste: eins, zwei, drei, vier, fünf, sechs. Ich muss alle Dinge in dieser Liste hinzuzufügen.

Wow, ich hasse Arbeit. Aber na ja, ich habe dies zu tun. Also hier gehe ich.

Ein plus zwei ist drei ... plus drei ist sechs ... und vier ... Ich weiß es nicht. Ich habe mich verlaufen. Es ist zu schwer für mich in meinem Kopf zu tun. Ich weiß nicht viel Sorgfalt für diese Art von Arbeit.

Lassen Sie sich also nicht die Arbeit machen. Lassen Sie uns Sie und ich denke nur, wie schwer es ist. Wie viel Arbeit würde ich tun müssen, um sechs Zahlen hinzufügen?

Nun, mal sehen. Ich muss eins und zwei addieren und dann das auf drei addieren und dann, dass in allen vier ... Alle hinzufügen, ich zähle sechs hinzufügt. Ich habe zu tun, sechs fügt diese zu lösen.

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

Big O sagt: wir tun müssen, sechs, diese zu lösen hinzufügt. Eine hinzufügen, für jede Sache von eins bis sechs. Sechs kleine Stücke von der Arbeit ... jedes Stück Arbeit ist ein zus.

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

Oh nein, jetzt habe ich mehr Arbeit. Meine Güte. Wer macht diese Art von Sachen?!

Nun fragen sie mich von eins bis zehn hinzuzufügen! Warum sollte ich das tun? Ich wollte nicht, 05.59 hinzuzufügen. Um von eins bis zehn hinzuzufügen ... na ja ... das wäre noch hart!

Wie viel mehr schwer es sein würde? Wie viel mehr Arbeit würde ich tun? Muss ich mehr oder weniger Schritte müssen?

Nun, ich denke, würde ich tun, zehn fügt ... ein für jede Sache von eins bis zehn. Zehn ist mehr als sechs. Das würde ich arbeiten habe viel mehr von eins bis zehn hinzuzufügen, als 5.59!

Ich will nicht jetzt hinzuzufügen. Ich möchte nur auf denken, wie schwer es sein könnte, dass viel hinzuzufügen. Und ich hoffe, zu spielen, sobald ich kann.

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

Big O ist dein Freund und ich. Big O hilft uns zu denken, wie viel Arbeit, die wir tun müssen, damit wir planen. Und wenn wir Freunde mit großen OS sind, kann er uns helfen wählen Arbeit, die nicht so schwer!

Jetzt müssen wir neue Arbeit tun. Ach nein. Ich mag es nicht, diese Arbeit etwas überhaupt.

Das neue Werk ist: in alle Dinge von einem zum n

Bitte warten! Was ist n? Habe ich das? Wie kann ich von einem zum n hinzufügen, wenn Sie mir nicht sagen, was n?

Nun, ich weiß nicht, was n. Mir wurde nicht gesagt. Warst du? Nein? Naja. So können wir die Arbeit nicht machen. Puh.

Aber wenn wir die Arbeit jetzt nicht tun, können wir erahnen, wie schwer es wäre, wenn wir n wissen. Wir müssten n Dinge summieren sich, nicht wahr? Natürlich!

Jetzt kommt großes O, und er wird uns sagen, wie schwer diese Arbeit ist. Er sagt: alles von einem bis N, eins nach dem anderen zu schreiben, ist O (n). Um all diese Dinge hinzufügen, [Ich weiß, ich muss mal n hinzufügen.] [1] Das ist ein großes O! Er sagt uns, wie schwer es ist, eine Art von Arbeit zu tun.

Für mich, denke ich an großen OS wie ein großer, langsam, Chef des Mensch. Er denkt an Arbeit, aber er tut es nicht. Er könnte sagen: „THut Arbeit ist schnell.“Oder er könnte sagen:‚Diese Arbeit ist so langsam und schwer!‘Aber er die Arbeit nicht tun. Er schaut nur auf die Arbeit, und dann sagt er uns, wie viel Zeit es könnte dauern.

Ich interessiere viel für große O. Warum? Ich arbeite nicht gern! Niemand mag es zu arbeiten. Deshalb haben wir alle großen O Liebe! Er sagt uns, wie schnell können wir arbeiten. Er hilft uns, denke daran, wie harte Arbeit ist.

Uh oh, mehr Arbeit. Nun lassen Sie uns nicht die Arbeit machen. Aber lassen Sie sich einen Plan machen, es zu tun, Schritt für Schritt.

Sie gaben uns ein Deck von zehn Karten. Sie sind alle durcheinander: sieben, vier, zwei, sechs ... nicht gerade überhaupt nicht. Und jetzt ... Unsere Aufgabe ist es, sich zu sortieren.

Ergh. Das klingt nach einer Menge Arbeit!

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

Ich werde bei jedem Paar von Karten schauen, paar, durch das Deck, von Anfang bis Ende. Wenn die erste Karte in einem Paar groß ist und die nächste Karte in diesem Paar ist klein, tausche ich sie. Else, gehe ich zum nächsten Paar, und so weiter und so weiter ... und bald wird das Deck getan.

Wenn das Deck fertig ist, ich frage: hast tauschen I-Karten in das passieren? Wenn ja, muss ich es tun alles noch einmal, von oben.

Zu einem bestimmten Zeitpunkt zu einem bestimmten Zeitpunkt, wird es keine Swaps sein, und unsere Art des Decks würde geschehen. So viel Arbeit!

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

Ich habe zehn Karten. Und die meiste Zeit - das ist, wenn ich nicht viel Glück -. Ich durch das ganze Deck bis zu zehnmal gehen muss, mit bis zu zehn Karten Swaps jedes Mal durch das Deck

Big O, hilf mir!

Big O kommt herein und sagt:. Für ein Deck von n-Karten, es zu sortieren, auf diese Weise in O geschehen wird (N zum Quadrat) Zeit

Warum er sagt n squared?

Nun, wissen Sie, n quadriert n n-mal. Nun, ich verstehe: n-Karten geprüft, bis zu dem, was sein könnte, n-mal durch das Deck. Das heißt zwei Schleifen, die jeweils mit n Stufen. Das ist n squared viel Arbeit zu tun. Viel Arbeit, aber sicher!

Nun, wenn große O sagt O nehmen (n quadriert) Arbeit, er bedeutet nicht, n fügt quadriert, auf die Nase. Es könnte einig klein bisschen weniger, für einigen Fall sein. Aber im schlimmsten Fall wird es sein, in der Nähe von n Arbeitsschritte quadrierten das Deck zu sortieren.

Jetzt ist hier, wo großes O unser Freund ist.

Big O weist darauf hin, dies: wie n groß wird, wenn wir Karten sortieren, wird die Arbeit viel viel mehr hart als der alte just-Add-diese-Dinge Job. Woher wissen wir das?

Nun, wenn n wirklich groß wird, ist es uns egal, was wir n oder n squared hinzufügen könnte.

Für große n, n Quadrat ist mehr groß als n ist.

Big O sagt uns, dass die Dinge zu sortieren, ist mehr als hart Dinge hinzuzufügen. O (n quadriert) mehr als O (n) für große n. Das bedeutet:. Wenn n echten groß wird, ein gemischtes Deck n Dinge zu sortieren, muss mehr Zeit in Anspruch nehmen, als nur hinzufügen, n gemischte Dinge

Big O, um die Arbeit für uns nicht lösen. Big O sagt uns, wie hart die Arbeit ist.

Ich habe ein Kartenspiel. Ich habe sie sortieren. Du hast geholfen. Danke.

Gibt es eine schnelle Möglichkeit, die Karten zu sortieren? Kann großes O uns helfen?

Ja, es ist eine schnelle Art und Weise! Es dauert einige Zeit zu lernen, aber es funktioniert ... und es funktioniert recht schnell. Sie können es versuchen, aber Ihre Zeit mit jedem Schritt und verlieren Sie nicht Platz.

In diesem neuen Weg, um ein Deck zu sortieren, wir nicht überprüfen Paare von Karten, wie wir vor einer Weile taten. Hier sind Ihre neue Regeln dieses Deck zu sortieren:

One: Ich wähle eine Karte in dem Teil des Decks wir jetzt arbeiten. Sie können eine für mich wählen, wenn Sie mögen. (Das erste Mal, dass wir dies tun „das Teil des Decks wir jetzt arbeiten“ ist das ganze Deck, natürlich.)

Zwei: Ich spreizen das Deck auf dieser Karte, die Sie gewählt haben. Was ist das spreizen; Wie spreizen ich? Nun, ich gehe von der Startkarte nach unten, eins nach dem anderen, und ich suche eine Karte, die mehr hoch als die Spreizung-Karte ist.

Drei: Ich gehe von der End-Karte, und ich suche nach einer Karte, das niedriger ist als die Spreizung-Karte ist.

Wenn ich diese beiden Karten gefunden haben, ich tauschen sie, und gehen Sie auf, um weitere Karten zu schauen zu tauschen.Das heißt, ich gehe zurück zu Schritt zwei und spreizt auf der Karte, die Sie etwas mehr gewählt haben.

An einem gewissen Punkt, diese Schleife (von zwei bis drei) endet. Sie endet, wenn beide Hälften dieser Suche auf der Karte spreizen erfüllen. Dann haben wir gespreizt nur das Deck mit der Karte, die Sie im ersten Schritt gewählt haben. Nun, alle Karten in der Nähe des Starts sind niedriger als die Spreizung-Karte; und die Karten am Ende sind hoch als die Spreizung-Karte. Cooler Trick!

Vier (und dies ist der spaßige Teil): Ich habe zwei kleine Decks jetzt, ein niedriger als die Spreizung-Karte und eine weitere hoch. Jetzt gehe ich einen Schritt, auf jedes kleines Deck! Das heißt, ich von Schritt eins auf dem ersten kleine Deck beginnen, und wenn die Arbeit getan ist, beginne ich von Schritt Eins auf dem nächsten kleine Deck.

Ich breche das Deck in Teile, und jedes Teil sortieren, mehr kleine und mehr kleine und irgendwann habe ich keine Arbeit mehr zu tun. Nun, das mag langsam erscheinen, mit allen Regeln. Aber glauben Sie mir, ist es überhaupt nicht langsam. Es ist viel weniger Arbeit als die erste Art, die Dinge zu sortieren!

Was ist diese Art genannt? Es ist Quicksort genannt! Diese Art wurde von einem Mann gemacht C. genannt A. R. Hoare und er nannte es Quicksort. Nun wird Quicksort benutzt die ganze Zeit!

Quicksort bricht große Decks in kleinen bis. Das heißt, es große Aufgaben in kleiner aufbricht.

Hmmm. Es in eine Regel sein kann, denke ich. Um große Aufgaben klein zu machen, brechen sie auf.

Diese Art ist ziemlich schnell. Wie schnell? Big O sagt uns: diese Art braucht O (n log n) Arbeit getan werden, im mittleren Fall.

Ist es mehr oder weniger schnell als die erste Art? Big O, bitte helfen Sie!

Die erste Art war O (n quadriert). Aber Quicksort ist O (n log n). Sie wissen, dass n log n kleiner als n quadriert, für große n, nicht wahr? Nun, das ist, wie wir wissen, dass Quicksort ist schnell!

Wenn Sie ein Deck sortieren haben, was ist der beste Weg? Nun, können Sie tun, was Sie wollen, aber ich würde Quicksort wählen.

Warum muss ich Quicksort wählen? Ich mag es nicht, natürlich arbeiten! Ich will Arbeit so bald getan, wie ich es getan.

Wie kann ich weiß Quicksort ist weniger Arbeit? Ich weiß, dass O (n log n) weniger als O (n quadriert). Die O sind klein, so dass Quicksort ist weniger Arbeit!

Jetzt wissen Sie, mein Freund, Big O. er uns weniger Arbeit tun hilft. Und wenn Sie große O bekannt, können Sie weniger Arbeit tun!

Sie haben gelernt, alles, was mit mir! Du bist so schlau! Vielen Dank!

Jetzt ist die Arbeit getan, geht sie spielen!

[1]: Es gibt einen Weg, um all die Dinge, von eins bis n zu betrügen und hinzufügen, die alle auf einmal. Einige Jungen namens Gauss fand dies heraus, als er mit acht Jahren. Ich bin nicht so schlau obwohl, so fragen Sie mich nicht, wie er es getan hat .

Angenommen, wir reden über einen Algorithmus A , die etwas mit einem Datensatz von Größe tun sollte n .

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

Wenn Sie Pech haben, wenn A ausgeführt wird, könnte es dauern, X (n) Operationen abgeschlossen.

Wie es passiert, gibt es bestimmte Funktionen (man denke an sich als Implementierungen X (n) ), die recht häufig auftreten neigen. Diese sind gut bekannt und leicht im Vergleich (Beispiele: 1, Log N, N, N^2, N!, etc ..)

Durch diese zu vergleichen, wenn man über A und andere Algorithmen, ist es einfach, die Algorithmen Rang nach der Anzahl der Operationen, die sie können (worst-case) erfordern, Komplett.

In der Regel unser Ziel wird es sein, einen Algorithmus zu finden oder zu strukturieren A in einer solchen Art und Weise, dass sie eine Funktion X(n) haben, die so niedrig wie möglich eine Reihe zurückgibt.

Ich habe mehr einfachen Weg, um die Zeit Komplexität zu verstehen, er am häufigsten metrischen Zeitkomplexität für die Berechnung ist Big O-Notation. Dadurch werden alle konstanten Faktoren, so dass die Laufzeit kann in Bezug auf N geschätzt werden als N gegen unendlich geht. Im Allgemeinen kann man darüber nachdenkt wie folgt aus:

statement;

Ist konstant. Die Laufzeit der Anweisung wird nicht in Bezug auf N ändern

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

Ist linear. Die Laufzeit der Schleife ist direkt proportional zu N. Wenn N verdoppelt, so 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 der N. Wenn N verdoppelt, die Laufzeit erhöht sich 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 es, die Anzahl von Malen proportional N durch 2 geteilt werden kann, hierfür ist, dass der Algorithmus den Arbeitsbereich in der Hälfte mit jeder Iteration trennt.

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 (iterativen oder rekursiven) Schleifen, die logarithmisch sind, so dass der Algorithmus eine Kombination aus linearen und logarithmischen.

In der Regel in einer Dimension mit jedem Punkt etwas zu tun, linear ist, mit jedem Punkt etwas zu tun, in zwei Dimensionen ist quadratisch, und in der Hälfte den Arbeitsbereiches Teilung ist logarithmisch. Es gibt noch andere Big O Maßnahmen, wie eine kubische, exponentiell, und Quadratwurzel, aber sie sind nicht annähernd so verbreitet. O-Notation als O () beschrieben, wo das Maß. Der quicksort Algorithmus würde als O (N * log (N)) beschrieben werden.

Hinweis: Nichts von alldem berücksichtigt hat am besten, Durchschnitts- und Worst-Case-Maßnahmen. Jeder würde seine eigene Big O-Notation hat. Beachten Sie auch, dass dies eine sehr einfache Erklärung. Big O ist die häufigste, aber es ist auch komplexere, die ich gezeigt habe. Es gibt auch andere Bezeichnungen wie große Omega, wenig o und große Theta. Sie wahrscheinlich werden sie nicht außerhalb eines Algorithmus Analyse natürlich begegnen.

Mehr unter: hier

Sagen Sie Harry Potter bestellen: kompletter 8-Film Collection [Blu-ray] von Amazon und laden Sie die gleiche Filmsammlung online zur gleichen Zeit. Sie wollen prüfen, welche Methode schneller ist. Die Lieferung dauert fast einen Tag ankommen und der Download etwa 30 Minuten früher abgeschlossen. Toll! So ist es ein enges Rennen.

Was passiert, wenn ich mehrere Blu-ray-Filme wie Der Herr der Ringe, Dämmerung, The Dark Knight Trilogy etc. und laden Sie alle Filme online zur gleichen Zeit bestellen? Diesmal nimmt die Auslieferung noch am Tag abzuschließen, aber die online herunterladen dauert 3 Tage bis zum Ende. Für Online-Shopping, die Anzahl der Kaufsache (Eingang) hat keinen Einfluss auf die Lieferzeit. Der Ausgang ist konstant. Wir nennen das O (1) .

Für die Online-Download, ist die Download-Zeit zu den Filmdateigrößen (Eingang) direkt proportional. Wir nennen das O (n) .

Von den Experimenten wissen wir, dass Online-Shopping besser skaliert als Online-Download. Es ist sehr wichtig O-Notation zu verstehen, weil es hilft Ihnen, die Skalierbarkeit und Effizienz von Algorithmen zu analysieren.

Hinweis: Big O-Notation stellt das Worst-Case-Szenario einen Algorithmus. Nehmen wir an, dass O (1) und O (n) sind die Worst-Case-Szenarien von dem obigen Beispiel.

Referenz : http://carlcheo.com/compsci

Wenn Sie einen geeigneten Begriff der Unendlichkeit im Kopf haben, dann gibt es eine sehr kurze Beschreibung:

Big O-Notation sagt Ihnen, die Kosten für ein unendlich großes Problem zu lösen.

Und weiter

Konstante Faktoren sind vernachlässigbar

Wenn Sie einen Computer aktualisieren, Ihren Algorithmus doppelt so schnell laufen kann, O-Notation wird das nicht bemerken. Konstante Verbesserungen sind zu klein, um auch in der Skala festgestellt werden, die O-Notation arbeitet. Beachten Sie, dass dies ein beabsichtigter Teil der Gestaltung von O-Notation ist.

Obwohl etwas „größer“ als ein konstanter Faktor nachgewiesen werden kann, jedoch.

Wenn interessiert Berechnungen zu tun, deren Größe „groß“ genug, um als etwa unendlich betrachtet wird, dann O-Notation ist etwa die Kosten für Ihr Problem zu lösen.

Wenn die oben nicht sinnvoll ist, dann haben Sie nicht eine kompatible intuitive Vorstellung der Unendlichkeit im Kopf, und Sie sollten wahrscheinlich alle der oben genannten außer Acht lassen; der einzige Weg, ich weiß, dass diese Ideen streng zu machen, oder sie zu erklären, wenn sie nicht schon intuitiv nützlich sind, ist es, zuerst Sie O-Notation oder etwas ähnliches zu lehren. (Obwohl, wenn Sie gut O-Notation in die Zukunft verstehen, kann es sich lohnen, diese Ideen zu überdenken)

Was ist eine einfache englische Erklärung von „Big O“ Notation?

Sehr schnell Hinweis:

Die O in "Big O" bezeichnet als "Order" (oder eben "Reihenfolge")
so könnte man seine Idee buchstäblich bekommen, dass es verwendet wird, etwas zu bestellen, sie zu vergleichen.

"Big O" macht zwei Dinge:
1. Schätzungen, wie viele Schritte des Verfahrens Ihr Computer gilt eine Aufgabe zu erfüllen.
2. Erleichterung des Prozesses mit anderen zu vergleichen, um zu bestimmen, ob es gut ist oder nicht?
3. "Big O‘ erreicht, über zwei mit standardisierten Notations.
Es gibt sieben am häufigsten verwendeten Notationen
1. O (1), bedeutet, dass Ihr Computer eine Task mit 1 Schritt getan erhält, es ist ausgezeichnet, bestellt No.1
2. O (log N), bedeutet, dass Ihr Computer eine Aufgabe mit logN Schritte abgeschlossen haben, seine gute, Bestellte No.2
3. O (N), eine Aufgabe mit N Schritten beenden, seine Messe, Ordnung No.3
4. O (NlogN), endet eine Aufgabe mit O(NlogN) Schritte, es ist nicht gut, Ordnung No.4
5. O (N ^ 2), eine Aufgabe mit N^2 Schritte getan, es ist schlecht, Ordnung No.5
6. O (2 ^ N), eine Aufgabe mit 2^N Schritte getan, es ist schrecklich, Ordnung No.6
7. O (N!), Eine Aufgabe mit N! Schritte getan, es ist schrecklich, Ordnung No.7

Angenommen, Sie Notation O(N^2) bekommen, nicht nur klar das Verfahren dauert N * N Schritte, um eine Aufgabe zu erfüllen, auch Sie sehen, dass es als O(NlogN) aus ihrem Ranking nicht gut ist.

Bitte beachten Sie die Reihenfolge am Zeilenende, nur für Ihre bessere understanding.There ist mehr als 7 Notationen, wenn alle Möglichkeiten in Betracht gezogen.

In CS, der Satz von Schritten, um eine Aufgabe zu erreichen, wird Algorithmen genannt.
In Terminologie wird Big O-Notation verwendet, um die Leistung oder die Komplexität eines Algorithmus zu beschreiben.

Darüber hinaus stellt Big O, um die Worst-Case oder die obere Grenze Schritte messen.
Sie Big-Ω (Big-Omega) für die besten Fall beziehen könnten.

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

Zusammenfassung
„Big O“ beschreibt die Leistung ist der Algorithmus und wertet sie aus.

oder es formal adressieren „Big O“ klassifiziert die Algorithmen und den Vergleichsprozess standardisieren.

einfachste Weg, um es zu betrachten (in einfachem Englisch)

Wir versuchen, zu sehen, wie die Anzahl der Eingabeparameter, die Laufzeit eines Algorithmus beeinflusst. Wenn die Laufzeit Ihrer Anwendung auf die Anzahl der Eingabeparameter proportional ist, dann wird gesagt, in Big O von n sein.

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

Eine genauere Erklärung (mathematische)

Angenommen

n = die Anzahl der Eingabeparameter

T (n) = Die eigentliche Funktion, die die Laufzeit des Algorithmus in Abhängigkeit von n drückt

c = eine Konstante

f (n) = eine Näherungsfunktion, die die Laufzeit des Algorithmus in Abhängigkeit von n ausdrückt

Dann so weit wie Big O betrifft, so ist die Näherung f (n) als gut genug, solange die unter Bedingung erfüllt ist.

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

Die Gleichung wird gelesen als Als n gegen unendlich geht, T n, kleiner oder gleich c Zeiten f n.

O-Notation wird dies als

geschrieben

T(n)∈O(n)

Dies wird gelesen als T von n in großen OS von n ist.

Zurück zu Englisch

Auf der Grundlage der mathematischen Definition oben, wenn Sie sagen, Sie Algorithmus ein Big O von n ist, bedeutet es, es eine Funktion von n (Anzahl der Eingangsparameter) ist oder schneller . Wenn Ihr Algorithmus Big O von n ist, dann ist es auch automatisch die Big O n Platz.

Big O von n bedeutet mein Algorithmus mindestens so schnell wie das läuft. Sie können nicht bei Big O-Notation Ihres Algorithmus schauen und sagen seine langsam. Sie können nur die schnelle sagen.

Überprüfen Sie dies für ein Video-Tutorial heraus Big O von UC Berkley. Es ist eigentlich ein einfaches Konzept. Wenn Sie Professor Shewchuck (aka Gott Ebene Lehrer) zu erläutern, es zu hören, werden Sie sagen „Oh, das ist alles, es ist!“.

ich eine wirklich große Erklärung über O-Notation gefunden besonders für ein jemanden, der nicht viel in der Mathematik ist.

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

Big O-Notation wird in der Informatik verwendet, um die Leistung zu beschreiben,   oder Komplexität eines Algorithmus. Big O beschreibt speziell die   Worst-Case-Szenario, und kann die Ausführungszeit zu beschreiben, verwendet werden,   erforderlich ist oder der Raum verwendet (beispielsweise im Speicher oder auf der Festplatte) durch eine   Algorithmus.

Wer Programming Pearls oder andere Informatik gelesen hat   Bücher und eine Erdung in Mathematik nicht haben eine Wand geschlagen haben   wenn sie Kapiteln erreicht, die O erwähnen (N log N) oder andere scheinbar   verrückt Syntax. Hoffentlich wird dieser Artikel Ihnen helfen, ein gewinnen   Verständnis der Grundlagen der Big O und Logarithmen.

Als Programmierer ersten und einem Mathematiker zweiten (oder vielleicht dritte oder   Vierter) fand ich den besten Weg Big O gründlich zu verstehen war,   einige Beispiele in Code erzeugen. So sind einige Aufträge von   Wachstum zusammen mit Beschreibungen und Beispielen, wo möglich.

O (1)

O (1) beschreibt einen Algorithmus, der in der gleichen Zeit immer ausgeführt wird   (Oder Zwischenraum) unabhängig von der Größe des Eingangsdatensatzes.
bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
O (N)

O (N) beschreibt einen Algorithmus, deren Leistung wächst linear und   in direktem Verhältnis zu der Größe des Eingangsdatensatzes. Das Beispiel   unten zeigt auch, wie Big O, um die Worst-Case-Leistung begünstigt   Szenario; eine passende String könnte bei jeder Iteration der gefunden werden   for-Schleife und die Funktion wäre zu früh, aber Big O-Notation zurückkehren wird   immer davon ausgehen, die obere Grenze, wo der Algorithmus die ausführt   maximale Anzahl von Iterationen.
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, dessen Leistung unmittelbar   proportional der Größe des Eingabedatensatzes auf den Platz. Das ist   gemeinsam mit Algorithmen, die Iterationen über die Daten verschachtelt beinhalten   einstellen. Tiefere verschachtelte Iterationen in O (N ³), O (N ⁴) etc.
Ergebnis werden
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) zeigt einen Algorithmus, deren Wachstum verdoppelt mit jedem additon   die Eingangsdaten eingestellt. Die Wachstumskurve von einem O (2 ^N) Funktion ist   exponentieller - beginnend sehr flach, dann meteorically off steigen. Ein   Beispiel für eine O (2 ^N) Funktion ist die rekursive Berechnung der 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, damit ich eine gemeinsame verwenden   Beispiel:

Binäre Suche ist eine Technik verwendet, sortiert Datensätze zu suchen. Es klappt   durch das mittlere Element des Datensatz der Auswahl, die im wesentlichen   Medianwert, und vergleicht sie mit einem Sollwert. Wenn die Werte übereinstimmen es   wird wieder Erfolg. Wenn der Sollwert höher ist als der Wert von   das Tastelement es wird die obere Hälfte des Datensatzes übernehmen und   führen die gleiche Operation dagegen. Ebenso, wenn der Zielwert   der Wert des Tastelements niedriger ist als es der durchführen wird   Operation gegen die untere Hälfte. Es wird auch weiterhin die Daten halbieren   mit jeder Iteration gesetzt bis der Wert, den er oder bis festgestellt wurde, kann   Split nicht mehr den Datensatz.

Diese Art von Algorithmus wird als O (log N) beschrieben. Die iterative Halbierung   von Datensatz in dem binären Suche beschriebenen Beispiel erzeugt ein Wachstum   Kurve, die zu Beginn Spitzen und flacht langsam wie die Größe aus   Sätze der Daten zu erhöhen z.B. ein Eingabedatensatz, der 10 Elemente   dauert 1 Sekunde ein Datensatz, der 100 Elemente abgeschlossen ist, nimmt   zwei Sekunden und ein Datensatz mit 1000 Einzelteile werden drei nehmen   Sekunden. Machst dudie Größe des Eingangsdatensatzes bling hat wenig Einfluss auf   ihr Wachstum als nach einer einzigen Iteration des Algorithmus des Datensatz   halbiert und somit mit einer Eingangsdaten auf eine Stufe eingestellt werden halbe   Größe. Dies macht Algorithmen wie binäre Suche äußerst effizient   wenn mit großen Datenmengen zu tun.

Dies ist eine sehr vereinfachte Erklärung, aber ich hoffe, es deckt die meisten wichtigen Details.

Angenommen, Ihr Algorithmus mit dem Problem zu tun, hängt von einigen ‚Faktoren‘, zum Beispiel wollen sie es macht N und X.

In Abhängigkeit von N und X, Ihr Algorithmus wird einige Operationen erfordern, zum Beispiel im schlimmsten Fall ist es 3(N^2) + log(X) Operationen.

Da Big-O nicht zu viel kümmert sich um konstanten Faktor (aka 3), das Big-O Ihres Algorithmus ist O(N^2 + log(X)). Er übersetzt im Grunde ‚die Menge an Operationen Ihr Algorithmus für den schlimmsten Fall muss skaliert mit diesem‘.

Vorwort

Algorithmus : procedure / Formel für die Lösung eines Problems

Wie Algorithmen analysiere und wie können wir vergleichen Algorithmen gegeneinander?

Beispiel: Sie und ein Freund werden gebeten, eine Funktion zu erstellen, um die Zahlen von 0 bis N. Sie mit f kommen bis Summe (x) und Ihr Freund kommt mit g (x). Beide Funktionen haben das gleiche Ergebnis, aber ein anderer Algorithmus. Um objektiv die Effizienz der Algorithmen vergleichen wir mit Big-O-Notation .

Big-O-Notation:. beschreibt , wie schnell die Laufzeit die Eingabe relativ wachsen als der Eingang beliebig groß werden

3 SCHLUSSELERKENNTNISSE:

Vergleichen wie schnell Laufzeit wächst nicht vergleichen genaue Runtimes (abhängig von der Hardware)
nur mit Laufzeit wächst relativ zum Eingang (n)
Wie n wird beliebig groß, auf die Bedingungen konzentrieren, die am schnellsten wachsen wie n groß wird (man denke unendlich) AKA asymptotische Analyse

Space Komplexität: abgesehen von Zeitkomplexität, wir Raum Komplexität auch kümmern (wie viel Speicher / Raum ein Algorithmus verwendet). Statt die Zeit der Operationen der Kontrolle übernehmen wir die Größe der Zuordnung von Speicher überprüfen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow

Was ist eine einfache englische Erklärung der „Big O“-Notation?

Das Telefonbuch

Handlungsreisende

Polynomzeit

O (1)

O (N)

O (N 2 )

O (2 N )

Logarithmen

Vorwort

O (N ²)

O (2 ^N)