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

Question

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

Answer 1

Kurze Anmerkung: Meine Antwort ist mit Sicherheit verwirrend Big Oh-Notation (was eine obere Grenze ist) mit der Big-Theta-Schreibweise "" (was eine zweiseitige Grenze ist). Meiner Erfahrung nach ist dies jedoch typisch für Diskussionen in einem nicht-akademischen Umfeld. Ich entschuldige mich für die entstandene Verwirrung.

---

Die Komplexität von BigOh lässt sich mit dieser Grafik veranschaulichen:

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

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

In diesem Satz sind einige wichtige und bewusst gewählte Worte enthalten:

• relativ: Sie können nur Äpfel mit Äpfeln vergleichen. Man kann einen Algorithmus, der eine arithmetische Multiplikation durchführt, nicht mit einem Algorithmus vergleichen, der eine Liste von ganzen Zahlen sortiert. Aber ein Vergleich von zwei Algorithmen, die arithmetische Operationen durchführen (eine Multiplikation, eine Addition), wird Ihnen etwas Sinnvolles sagen;
• Vertretung: BigOh (in seiner einfachsten Form) reduziert den Vergleich zwischen Algorithmen auf eine einzige Variable. Diese Variable wird aufgrund von Beobachtungen oder Annahmen ausgewählt. So werden beispielsweise Sortieralgorithmen in der Regel auf der Grundlage von Vergleichsoperationen (Vergleich zweier Knoten zur Bestimmung ihrer relativen Reihenfolge) verglichen. Dabei wird davon ausgegangen, dass der Vergleich teuer ist. Was aber, wenn der Vergleich billig ist, aber die Vertauschung teuer ist? Dann wird der Vergleich geändert; und
• Komplexität: Wenn ich eine Sekunde brauche, um 10.000 Elemente zu sortieren, wie lange brauche ich dann, um eine Million zu sortieren? Komplexität ist in diesem Fall ein relatives Maß zu etwas anderem.

Kommen Sie zurück und lesen Sie das oben Gesagte noch einmal, wenn Sie den Rest gelesen haben.

Das beste Beispiel für BigOh, das mir einfällt, ist die Arithmetik. Nehmen Sie zwei Zahlen (123456 und 789012). Die grundlegenden arithmetischen Operationen, die wir in der Schule gelernt haben, waren:

• Zusatz;
• Subtraktion;
• Multiplikation; und
• Abteilung.

Jedes dieser Elemente ist ein Vorgang oder ein Problem. Eine Methode, diese zu lösen, wird als Algorithmus .

Die Addition ist die einfachste. Man reiht die Zahlen in einer Spalte aneinander (nach rechts) und schreibt die letzte Zahl der Addition in das Ergebnis. Der "Zehner"-Teil dieser Zahl wird in die nächste Spalte übertragen.

Nehmen wir an, dass die Addition dieser Zahlen die teuerste Operation in diesem Algorithmus ist. Es liegt auf der Hand, dass wir für die Addition dieser beiden Zahlen 6 Ziffern addieren müssen (und möglicherweise eine 7. Ziffer übertragen). Wenn wir zwei 100-stellige Zahlen addieren, müssen wir 100 Additionen durchführen. Wenn wir addieren zwei Bei 10.000 Ziffern müssen wir 10.000 Additionen durchführen.

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

Die Subtraktion ist ähnlich (außer dass man sich eventuell etwas leihen muss, anstatt zu übertragen).

Die Multiplikation ist anders. Man reiht die Zahlen aneinander, nimmt die erste Ziffer der unteren Zahl und multipliziert sie der Reihe nach mit jeder Ziffer der oberen Zahl und so weiter. Um unsere beiden 6-stelligen Zahlen zu multiplizieren, müssen wir also 36 Multiplikationen durchführen. Möglicherweise müssen wir sogar 10 oder 11 Spaltenadditionen durchführen, um das Endergebnis zu erhalten.

Bei zwei 100-stelligen Zahlen müssen wir 10.000 Multiplikationen und 200 Additionen durchführen. Für zwei einmillionenstellige Zahlen müssen wir eine Billion (10 12 ) Multiplikationen und zwei Millionen Additionen.

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

Wir interessieren uns nur für den größten Teil der Komplexität.

Der Scharfsinnige hat vielleicht erkannt, dass man die Anzahl der Operationen wie folgt ausdrücken kann: n 2 + 2n. Aber wie Sie in unserem Beispiel mit zwei Zahlen mit jeweils einer Million Ziffern gesehen haben, wird der zweite Term (2n) unbedeutend (er macht 0,0002 % der gesamten Operationen in diesem Stadium aus).

Man kann feststellen, dass wir hier vom schlimmsten Fall ausgegangen sind. Wenn bei der Multiplikation von 6-stelligen Zahlen eine davon 4-stellig und die andere 6-stellig ist, haben wir nur 24 Multiplikationen. Dennoch berechnen wir das Worst-Case-Szenario für dieses "n", d. h. wenn beide Zahlen 6-stellig sind. Bei der Big-Oh-Notation geht es also um das Worst-Case-Szenario eines Algorithmus.

Das Telefonbuch

Das nächstbeste Beispiel, das mir einfällt, ist das Telefonbuch, das normalerweise "Weiße Seiten" oder ähnlich heißt, aber von Land zu Land unterschiedlich ist. Aber ich spreche von dem Buch, in dem die Personen nach dem Nachnamen und dann den Initialen oder dem Vornamen, möglicherweise der Adresse und dann den Telefonnummern aufgeführt sind.

Wenn Sie nun einen Computer anweisen würden, die Telefonnummer von "John Smith" in einem Telefonbuch mit 1.000.000 Namen zu suchen, was würden Sie tun? Was würden Sie tun, wenn Sie nicht wüssten, wie weit das "S" reicht (nehmen wir an, Sie könnten es nicht)?

Eine typische Umsetzung könnte darin bestehen, dass man sich zur Mitte hin öffnet, die 500.000 th und vergleichen Sie es mit "Smith". Wenn es "Smith, John" ist, haben wir wirklich Glück gehabt. Viel wahrscheinlicher ist, dass "John Smith" vor oder nach diesem Namen steht. Wenn er danach steht, teilen wir die letzte Hälfte des Telefonbuchs in zwei Hälften und wiederholen den Vorgang. Wenn er davor steht, teilen wir die erste Hälfte des Telefonbuchs in zwei Hälften und wiederholen den Vorgang. Und so weiter.

Dies wird als binäre Suche und wird jeden Tag beim Programmieren verwendet, ob man sich dessen bewusst ist oder nicht.

Wenn Sie also einen Namen in einem Telefonbuch mit einer Million Namen finden wollen, können Sie jeden Namen finden, indem Sie dies höchstens 20 Mal tun. Beim Vergleich von Suchalgorithmen entscheiden wir, dass dieser Vergleich unser "n" ist.

• Für ein Telefonbuch mit 3 Namen sind (höchstens) 2 Vergleiche erforderlich.

• Für 7 braucht es höchstens 3.

• Für 15 braucht es 4.

• Für 1.000.000 braucht es 20.

Das ist umwerfend gut, nicht wahr?

In BigOh-Begriffen bedeutet dies O(log n) o logarithmische Komplexität . Der betreffende Logarithmus könnte nun ln (Basis e), log ₁₀ , Protokoll ₂ oder eine andere Basis. Es spielt keine Rolle, es ist immer noch O(log n) genau wie O(2n 2 ) und O(100n 2 ) sind immer noch beide O(n 2 ).

Es lohnt sich, an dieser Stelle zu erklären, dass BigOh dazu verwendet werden kann, drei Fälle mit einem Algorithmus zu bestimmen:

• Bester Fall: Bei der Telefonbuchsuche finden wir den Namen im besten Fall durch einen Vergleich. Das ist O(1) o konstante Komplexität ;
• Erwarteter Fall: Wie oben beschrieben ist dies O(log n); und
• Schlimmster Fall: Auch dies ist O(log n).

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

Zurück zum Telefonbuch.

Was ist, wenn Sie eine Telefonnummer haben und einen Namen finden wollen? Die Polizei verfügt über ein umgekehrtes Telefonbuch, aber solche Abfragen sind der Allgemeinheit verwehrt. Oder doch? Technisch gesehen kann man eine Nummer in einem normalen Telefonbuch rückwärts suchen. Aber wie?

Sie beginnen mit dem ersten Namen und vergleichen die Zahl. Wenn sie übereinstimmt, gut, wenn nicht, gehen Sie zum nächsten. Das muss man so machen, weil das Telefonbuch ungeordnet (jedenfalls nach Telefonnummern).

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

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

Der Handelsreisende

Dies ist ein ziemlich berühmtes Problem in der Informatik und verdient eine Erwähnung. Bei diesem Problem haben Sie N Städte. Jede dieser Städte ist mit 1 oder mehreren anderen Städten durch eine Straße mit einer bestimmten Entfernung verbunden. Beim Traveling-Salesman-Problem geht es darum, die kürzeste Tour zu finden, die jede Stadt besucht.

Klingt einfach? Falsch gedacht.

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

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

Nun, eigentlich sind es weniger, denn einige sind gleichwertig (A B C und C B A sind zum Beispiel gleichwertig, weil sie dieselben Straßen benutzen, nur in umgekehrter Richtung).

In Wirklichkeit gibt es 3 Möglichkeiten.

• Wenn man dies auf 4 Städte ausdehnt, hat man (iirc) 12 Möglichkeiten.
• Bei 5 sind es 60.
• Aus 6 werden 360.

Dies ist eine Funktion einer mathematischen Operation namens faktoriell . Im Grunde genommen:

• 5! = 5 × 4 × 3 × 2 × 1 = 120

• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040

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

• 50! = 50 × 49 × × 2 × 1 = 3.04140932 × 10 64

Das BigOh des Traveling-Salesman-Problems lautet also O(n!) o faktorielle oder kombinatorische Komplexität .

Wenn man bei 200 Städten angelangt ist, bleibt nicht mehr genug Zeit im Universum, um das Problem mit herkömmlichen Computern zu lösen.

Das sollte man bedenken.

Polynomialzeit

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

O(n), O(n 2 ) usw. sind alle polynomiell. Einige Probleme können nicht in polynomieller Zeit gelöst werden. Aus diesem Grund werden bestimmte Dinge in der Welt verwendet. Kryptographie mit öffentlichem Schlüssel ist ein Paradebeispiel. Es ist rechnerisch schwer, zwei Primfaktoren einer sehr großen Zahl zu finden. Wäre dies nicht der Fall, könnten wir die öffentlichen Schlüsselsysteme, die wir verwenden, nicht einsetzen.

So, das war's mit meiner (hoffentlich leicht verständlichen) Erklärung von BigOh (überarbeitet).

Answer 2

Sie zeigt, wie ein Algorithmus je nach Eingabegröße skaliert.

O(n 2 ) : bekannt als Quadratische Komplexität

• 1 Stück: 1 Vorgänge
• 10 Artikel: 100 Vorgänge
• 100 Artikel: 10.000 Vorgänge

Beachten Sie, dass die Anzahl der Artikel um den Faktor 10 zunimmt, die Zeit jedoch um den Faktor 10 2 . Im Grunde genommen ist n=10 und damit O(n 2 ) gibt uns den Skalierungsfaktor n 2 das sind 10 2 .

O(n) : bekannt als Lineare Komplexität

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

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

O(1) : bekannt als Konstante Komplexität

• 1 Posten: 1 Vorgänge
• 10 Artikel: 1 Operationen
• 100 Artikel: 1 Vorgänge

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

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

• 1 Posten: 1 Vorgänge
• 10 Artikel: 2 Vorgänge
• 100 Artikel: 3 Vorgänge
• 1000 Artikel: 4 Vorgänge
• 10.000 Artikel: 5 Vorgänge

Die Anzahl der Berechnungen erhöht sich nur um einen Logarithmus des Eingabewertes. In diesem Fall, wenn jede Berechnung 1 Sekunde dauert, ist der Logarithmus der Eingabe n ist die benötigte Zeit, also log n .

Das ist der Kern der Sache. Sie reduzieren die Mathematik, so dass es vielleicht nicht genau n 2 oder was auch immer es sein soll, aber das wird der dominierende Faktor bei der Skalierung sein.

Answer 3

Die Big-O-Notation (auch "asymptotische Wachstumsnotation" genannt) ist wie Funktionen "aussehen", wenn man konstante Faktoren und Dinge in der Nähe des Ursprungs außer Acht lässt . Wir verwenden es, um über Folgendes zu sprechen wie die Dinge skalieren .

---

Grundlagen

für "ausreichend" große Eingaben...

• f(x) O(upperbound) bedeutet f "wächst nicht schneller als" upperbound
• f(x) (justlikethis) mittlere 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 wie" wachsen 10x² . Ebenso wenig wie Big-O asymptotisch die Notation zu beachten nicht asymptotisch stuff ("stuff near the origin" oder "what happens when the problem size is small"): die Funktion 10x² soll "genau wie" wachsen 10x² - x + 2 .

Warum wollen Sie die kleineren Teile der Gleichung ignorieren? Weil sie von den großen Teilen der Gleichung völlig in den Hintergrund gedrängt werden, wenn man immer größere Maßstäbe anlegt; ihr Beitrag wird in den Hintergrund gedrängt und irrelevant. (Siehe Beispielabschnitt.)

Mit anderen Worten: Es geht um die Verhältnis wenn man ins Unendliche geht. Wenn Sie die tatsächlich benötigte Zeit durch die O(...) erhalten Sie einen konstanten Faktor im Grenzfall großer Eingaben. Intuitiv macht das Sinn: Funktionen "skalieren" miteinander, wenn man die eine multiplizieren kann, um die andere zu erhalten. Das ist, wenn wir sagen...

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

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

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

Es gibt viele Möglichkeiten, die Konstante zu wählen; oft ist die "beste" Wahl als "konstanter Faktor" des Algorithmus bekannt... aber wir ignorieren ihn oft, so wie wir nicht-größte Terme ignorieren (siehe Abschnitt "Konstante Faktoren", warum sie normalerweise keine Rolle spielen). Man kann sich die obige Gleichung auch als Schranke vorstellen und sagen: " Im schlimmsten Fall wird die Zeit, die dafür benötigt wird, nie schlechter sein als etwa N*log(N) innerhalb eines Faktors von 2,5 (ein konstanter Faktor, der uns nicht viel bedeutet) ".

Generell, O(...) ist am nützlichsten, weil wir uns oft für das Verhalten im schlimmsten Fall interessieren. Wenn f(x) etwas "Schlechtes" wie die Prozessor- oder Speichernutzung darstellt, dann " f(x) O(upperbound) " bedeutet " upperbound ist das Worst-Case-Szenario der Prozessor-/Speichernutzung".

---

Anwendungen

Als rein mathematisches Konstrukt ist die Big-O-Notation nicht darauf beschränkt, über Verarbeitungszeit und Speicher zu sprechen. Sie können damit die Asymptotik von allem erörtern, bei dem eine Skalierung sinnvoll ist, z. B.:

• die Anzahl der möglichen Handshakes zwischen N Menschen auf einer Party ( (N²) und zwar N(N-1)/2 aber wichtig ist, dass es "wie" skaliert N² )
• Wahrscheinliche erwartete Anzahl von Personen, die virales Marketing gesehen haben, als Funktion der Zeit
• wie die Latenzzeit einer Website mit der Anzahl der Verarbeitungseinheiten in einer CPU oder GPU oder einem Computer-Cluster skaliert
• wie sich die Wärmeabgabe auf CPU-Chips in Abhängigkeit von der Anzahl der Transistoren, der Spannung usw. entwickelt.
• wie viel Zeit ein Algorithmus für die Ausführung benötigt, in Abhängigkeit von der Größe der Eingabe
• wie viel Platz ein Algorithmus zur Ausführung benötigt, in Abhängigkeit von der Größe der Eingabe

---

Beispiel

Im obigen Beispiel mit dem Händedruck schüttelt jeder in einem Raum die Hand des anderen. In diesem Beispiel, #handshakes (N²) . Warum?

Ein bisschen zurück: Die Anzahl der Handshakes ist genau n-choose-2 oder N*(N-1)/2 (jede von N Personen schüttelt die Hände von N-1 anderen Personen, aber hier werden die Händedrücke doppelt gezählt, also durch 2 teilen):

Für eine sehr große Anzahl von Personen ist der lineare Term jedoch N ist verschwindend klein 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, wenn die Zahl der Teilnehmer größer wird). Daher ist das Skalierungsverhalten order N² oder die Anzahl der Handshakes "wächst wie N²".

#handshakes(N)
  1/2
     N²

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

(Vorübergehende Abschweifung vom "einfachen Englisch":) Wenn Sie sich das selbst beweisen wollten, könnten Sie eine einfache Algebra auf das Verhältnis anwenden, um es in mehrere Terme aufzuteilen ( lim bedeutet "betrachtet im Grenzwert von", ignorieren Sie es einfach, wenn Sie es noch nicht gesehen haben, es ist nur eine Schreibweise für "und N ist wirklich sehr groß"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim  = lim (  -  ) = lim  = 1/2
N     N²       N     N²     N²      N  1

             this is 0 in the limit of N:
             graph it, or plug in a really large number for N

tl;dr: Die Anzahl der Handshakes "ähnelt" x² bei großen Werten so sehr, dass, wenn wir das Verhältnis #handshakes/x² aufschreiben würden, die Tatsache, dass wir keine genau x² Handshakes würden für eine beliebig lange Zeit nicht einmal im Dezimalsystem auftauchen.

z.B. für x=1Million, Verhältnis #Handshakes/x²: 0.499999...

---

Intuition aufbauen

So können wir Aussagen treffen wie...

"Für eine hinreichend große Eingabegröße=N ist es egal, wie hoch der konstante Faktor ist, wenn I doppelt die Eingabegröße ...

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

N (2N) = 2( N )

• ... Ich habe die Zeit, die ein O(N²) ("quadratische Zeit") Algorithmus benötigt, verdoppelt (vervierfacht)." (z.B. ein Problem, das 100x so groß ist, braucht 100²=10000x so lange... möglicherweise unhaltbar)

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

• ... Ich habe die Zeit, die ein O(N³) ("kubische Zeit") Algorithmus benötigt, verdoppelt (verachtfacht)." (z.B. ein Problem, das 100x so groß ist, braucht 100³=1000000x so lange... sehr unhaltbar)

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

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

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

• ... Ich ändere nicht die Zeit, die ein O(1) ("constant ime") Algorithmus benötigt." (das billigste!)

c*1 c*1

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

c 2N log(2N) / c N log(N) (hier dividieren wir f(2n)/f(n), aber wir hätten den Ausdruck wie oben massieren und cNlogN wie oben herausrechnen können)
2 log(2N)/log(N)
2 (log(2) + log(N))/log(N)
2*(1+(log ₂ N) -1 ) (grundsätzlich 2 für große N; eventuell weniger als 2.000001)
(alternativ, sagen wir log(N) wird immer unter wie 17 für Ihre Daten, so dass es O(17 N), die linear ist; das ist nicht rigoros noch sinnvoll though)

• ... Ich erhöhe die Zeit lächerlich um O(2 N ) ("exponentielle Zeit") Algorithmus benötigt." (Sie würden die Zeit verdoppeln (oder verdreifachen usw.), wenn Sie das Problem nur um eine einzige Einheit vergrößern)

2 N 2 2N \= (4 N )............auf andere Weise...... 2 N 2 N+1 \= 2 N 2 1 \= 2 2 N

(für die mathematisch Interessierten: Sie können mit der Maus über die Spoiler fahren, um kleinere Nebenbemerkungen zu erhalten)

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

(technisch gesehen könnte der konstante Faktor in einigen esoterischeren Beispielen eine Rolle spielen, aber ich habe die Dinge oben (z.B. in log(N)) so formuliert, dass er keine Rolle spielt)

Dies sind die üblichen Wachstumsordnungen, die Programmierer und angewandte Informatiker als Bezugspunkte verwenden. Sie sehen sie die ganze Zeit. (Auch wenn man technisch gesehen denken könnte: "Die Verdopplung der Eingabe macht einen O(N)-Algorithmus 1,414 Mal langsamer", ist es besser, sich vorzustellen: "Das ist schlechter als logarithmisch, aber besser als linear").

---

Konstante Faktoren

In der Regel ist es egal, wie die spezifischen konstanten Faktoren lauten, da sie keinen Einfluss auf die Art und Weise haben, wie die Funktion wächst. Zum Beispiel können zwei Algorithmen beide O(N) Zeit für die Fertigstellung, aber eine kann doppelt so langsam sein wie die andere. Normalerweise kümmert uns das nicht allzu sehr, es sei denn, der Faktor ist sehr groß, denn die Optimierung ist eine heikle Angelegenheit ( Wann ist eine Optimierung verfrüht? ); auch die bloße Auswahl eines Algorithmus mit einem besseren Big-O verbessert die Leistung oft um Größenordnungen.

Einige asymptotisch überlegene Algorithmen (z. B. ein Nicht-Vergleichs O(N log(log(N))) sort) kann einen so großen konstanten Faktor haben (z. B. 100000*N log(log(N)) ), oder einen relativ großen Overhead wie O(N log(log(N))) mit einer versteckten + 100*N dass sie sich selbst bei "großen Daten" kaum lohnen.

---

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

O(N) Algorithmen sind in gewissem Sinne die "besten" Algorithmen, wenn Sie alle Ihre Daten lesen müssen. Die der Akt des Lesens selbst ein Bündel von Daten ist ein O(N) Betrieb. Das Laden in den Speicher ist normalerweise O(N) (oder schneller, wenn Sie Hardware-Unterstützung haben, oder überhaupt keine Zeit, wenn Sie die Daten bereits gelesen haben). Wenn Sie jedoch die Daten berühren oder sogar siehe bei jedem Datenelement (oder sogar bei jedem anderen Datenelement), wird Ihr Algorithmus O(N) Zeit, um diese Suche durchzuführen. Unabhängig davon, wie lange Ihr tatsächlicher Algorithmus dauert, wird er mindestens O(N) weil sie diese Zeit damit verbracht hat, sich alle Daten anzusehen.

Dasselbe gilt für die der Akt des Schreibens selbst . Alle Algorithmen, die N Dinge ausgeben, benötigen N Zeit, weil die Ausgabe mindestens so lang ist (z. B. ist das Ausdrucken aller Permutationen (Möglichkeiten der Neuanordnung) eines Satzes von N Spielkarten faktoriell: O(N!) (weshalb gute Programme in diesen Fällen sicherstellen, dass eine Iteration O(1) Speicher verwendet und nicht jeden Zwischenschritt ausgibt oder speichert).

Dies motiviert die Verwendung von Datenstrukturen Datenstruktur: Eine Datenstruktur muss nur einmal gelesen werden (normalerweise O(N) Zeit), plus eine beliebige Menge an Vorverarbeitung (z. B. O(N) o O(N log(N)) o O(N²) ), die wir versuchen, klein zu halten. Danach nehmen Änderungen der Datenstruktur (Einfügungen/Löschungen/etc.) und Abfragen der Daten sehr wenig Zeit in Anspruch, wie z. B. O(1) o O(log(N)) . Dann machen Sie eine große Anzahl von Abfragen! Im Allgemeinen gilt: Je mehr Arbeit Sie im Vorfeld leisten, desto weniger Arbeit müssen Sie später erledigen.

Nehmen wir an, Sie haben die Längen- und Breitengradkoordinaten von Millionen von Straßenabschnitten und möchten alle Straßenkreuzungen finden.

• Naive Methode: Wenn man die Koordinaten einer Straßenkreuzung hätte und die benachbarten Straßen untersuchen wollte, müsste man jedes Mal die 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 der O(N) funktioniert nur einmal, aber wenn Sie es viele Male tun wollen (in diesem Fall, N mal, einmal für jedes Segment), müssten wir O(N²) Arbeit, oder 1000000²=1000000000000 Operationen. Nicht gut (ein moderner Computer kann etwa eine Milliarde Operationen pro Sekunde durchführen).
• Wenn wir eine einfache Struktur verwenden, die Hash-Tabelle genannt wird (eine schnelle Nachschlagetabelle, auch bekannt als Hash-Map oder Dictionary), zahlen wir einen geringen Preis, indem wir alles in O(N) Zeit. Danach dauert es im Durchschnitt nur noch eine konstante Zeit, um etwas nach seinem Schlüssel zu suchen (in diesem Fall ist unser Schlüssel die Koordinaten von Breiten- und Längengrad, gerundet zu einem Raster; wir suchen die angrenzenden Rasterräume, von denen es nur 9 gibt, was eine Konstante ist).
• Unsere Aufgabe wurde von einer undurchführbaren O(N²) auf ein überschaubares O(N) und alles, was wir zu tun hatten, waren geringe Kosten für die Erstellung einer Hashtabelle.
• Analogie : Die Analogie in diesem speziellen Fall ist ein Puzzle: Wir haben eine Datenstruktur erstellt, die eine Eigenschaft der Daten ausnutzt. Wenn unsere Straßenabschnitte wie Puzzleteile sind, gruppieren wir sie nach übereinstimmender Farbe und Muster. Dies machen wir uns zunutze, um später zusätzliche Arbeit zu vermeiden (indem wir Puzzleteile gleicher Farbe miteinander vergleichen, nicht mit jedem einzelnen Puzzleteil).

Die Moral von der Geschicht': Eine Datenstruktur ermöglicht es uns, Operationen zu beschleunigen. Mehr noch: Mit fortgeschrittenen Datenstrukturen können Sie Operationen auf unglaublich clevere Weise kombinieren, verzögern oder sogar ignorieren. Für verschiedene Probleme gibt es unterschiedliche Analogien, aber bei allen geht es darum, die Daten so zu organisieren, dass eine Struktur ausgenutzt wird, die uns wichtig ist oder die wir aus buchhalterischen Gründen künstlich auferlegt haben. Wir erledigen die Arbeit im Voraus (im Grunde planen und organisieren wir), und jetzt sind wiederkehrende Aufgaben viel einfacher!

---

Praktisches Beispiel: Visualisierung von Wachstumsreihenfolgen während der Codierung

Die asymptotische Notation ist in ihrem Kern völlig unabhängig von der Programmierung. Die asymptotische Notation ist ein mathematischer Rahmen für die Betrachtung der Skalierung von Dingen und kann in vielen verschiedenen Bereichen eingesetzt werden. Abgesehen davon... so können Sie anwenden. asymptotische Notation zur Kodierung.

Die Grundlagen: Wann immer wir mit jedem Element in einer Sammlung der Größe A interagieren (z. B. einem Array, einer Menge, allen Schlüsseln einer Map usw.) oder A Iterationen einer Schleife durchführen, ist das ein multiplikativer Faktor der Größe A. Warum sage ich "ein multiplikativer Faktor"? Weil Schleifen und Funktionen (fast per Definition) eine multiplikative Laufzeit haben: die Anzahl der Iterationen mal die in der Schleife geleistete Arbeit (oder bei Funktionen: die Anzahl der Aufrufe der Funktion mal die in der Funktion geleistete Arbeit). (Dies gilt, wenn wir nichts Ausgefallenes tun, wie z. B. Schleifen überspringen oder die Schleife frühzeitig verlassen, oder den Kontrollfluss in der Funktion auf der Grundlage von Argumenten ändern, was sehr häufig vorkommt). Hier sind einige Beispiele für Visualisierungstechniken, mit begleitendem Pseudocode.

(hier: die x s stehen für zeitlich konstante Arbeitseinheiten, Prozessorbefehle, Interpreter-Opcodes, was auch immer)

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 noch visuell vorstellen, was vor sich geht:

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 man zeichnen kann; ein Dreieck ist eine zweidimensionale Form (0,5 A^2), genauso wie ein Quadrat eine zweidimensionale Form (A^2) ist; der konstante Faktor von 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 eingehe; sie kann Sie in die Irre fü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 sehen, dass die Art und Weise, wie wir Schleifen, Funktionen und Bedingungen mit unseren Daten (Kontrollfluss usw.) verweben, die Zeit- und Raumnutzung unseres Programms nachahmt! Wenn der Zeit- und Platzbedarf zu einem Problem wird, greifen wir auf unsere Cleverness zurück und finden einen einfachen Algorithmus oder eine Datenstruktur, die wir nicht in Betracht gezogen hatten, um die Wachstumsrate irgendwie zu reduzieren. Nichtsdestotrotz können diese Visualisierungstechniken (auch wenn sie nicht immer funktionieren) eine naive Schätzung der Worst-Case-Laufzeit liefern.

Hier ist eine weitere Sache, die 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 Sie führen log(N) Durchläufe der Daten durch, was insgesamt O(N*log(N)) dauert:

   <----------------------------- 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

Das hat zwar nichts damit zu tun, ist aber dennoch erwähnenswert: Wenn wir einen Hash durchführen (z. B. eine Wörterbuch-/Hashtabellensuche), ist das 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 machen, z. B. eine rekursive Funktion oder einen Divide-and-Conquer-Algorithmus, können Sie die Master-Theorem (funktioniert normalerweise), oder in lächerlichen Fällen das Akra-Bazzi-Theorem (funktioniert fast immer) schlagen Sie die Laufzeit Ihres Algorithmus auf Wikipedia nach.

Aber Programmierer denken nicht so, denn irgendwann wird die Intuition für Algorithmen zur zweiten Natur. Man fängt an, etwas Ineffizientes zu programmieren und denkt sofort: "Mache ich etwas grob ineffizient? ". Wenn die Antwort "ja" lautet UND Sie vorhersehen, dass es tatsächlich von Bedeutung ist, können Sie einen Schritt zurücktreten und sich verschiedene Tricks ausdenken, um die Dinge schneller ablaufen zu lassen (die Antwort lautet fast immer "eine Hashtabelle verwenden", selten "einen Baum verwenden" und sehr selten etwas Komplizierteres).

---

Amortisierte und durchschnittliche Komplexität

Es gibt auch das Konzept des "amortisierten" und/oder "durchschnittlichen Falles" (beachten Sie, dass es sich dabei um unterschiedliche Begriffe handelt).

Durchschnittlicher Fall : Dies ist nichts anderes als die Verwendung der Big-O-Notation für den Erwartungswert einer Funktion und nicht für die Funktion selbst. In dem üblichen Fall, in dem alle Eingaben als gleich wahrscheinlich angesehen werden, ist der durchschnittliche Fall einfach der Durchschnitt der Laufzeit. Bei der Quicksortierung zum Beispiel ist der schlimmste Fall, auch wenn er O(N^2) für einige wirklich schlechte Eingaben, der durchschnittliche Fall ist der übliche O(N log(N)) (die wirklich schlechten Eingaben sind sehr gering, so gering, dass wir sie im Durchschnitt nicht bemerken).

Abgeschriebener Worst-Case : Einige Datenstrukturen können im schlimmsten Fall eine hohe Komplexität aufweisen, aber sie garantieren, dass der durchschnittliche Arbeitsaufwand besser ist als im schlimmsten Fall, wenn Sie viele dieser Operationen durchführen. Sie können zum Beispiel eine Datenstruktur haben, die normalerweise eine konstante O(1) Zeit. Gelegentlich kommt es jedoch zu "Schluckauf" und O(N) Zeit für eine zufällige Operation, weil er vielleicht etwas Buchhaltung oder Garbage Collection oder so etwas machen muss... aber er verspricht Ihnen, dass er, wenn er einen Schluckauf hat, für N weitere Operationen nicht mehr schluckern wird. Die Kosten im schlimmsten Fall sind immer noch O(N) pro Vorgang, aber die amortisierten Kosten über viele Läufe es O(N)/N = O(1) pro Vorgang. Da die großen Operationen hinreichend selten sind, kann man davon ausgehen, dass sich die große Menge an gelegentlicher Arbeit als konstanter Faktor in den Rest der Arbeit einfügt. Wir sagen, dass die Arbeit über eine ausreichend große Anzahl von Aufrufen "amortisiert" ist, so dass sie asymptotisch verschwindet.

Die Analogie zur amortisierten Analyse:

Sie fahren ein Auto. Gelegentlich müssen Sie 10 Minuten lang zur Tankstelle fahren zur Tankstelle zu fahren und dann 1 Minute lang den Tank aufzufüllen. Wenn Sie dies jedes Mal tun würden, wenn Sie mit Ihrem Auto irgendwo hinfahren (10 (10 Minuten Fahrt zur Tankstelle, ein paar Sekunden zum Tanken Bruchteil einer Gallone), wäre das sehr ineffizient. Wenn Sie aber alle paar Tage tanken, werden die 11 Minuten, die man für die Fahrt zur Tankstelle über eine ausreichend große Anzahl von Fahrten "amortisiert", dass man sie ignorieren und so tun kann, als wären alle Fahrten vielleicht 5 % länger.

Vergleich zwischen durchschnittlichem und amortisiertem Worst-Case-Fall:

• Durchschnittlicher Fall: Wir machen einige Annahmen über unsere Eingaben; d. h. wenn unsere Eingaben unterschiedliche Wahrscheinlichkeiten haben, dann haben auch unsere Ausgaben/Zeiten unterschiedliche Wahrscheinlichkeiten (von denen wir den Durchschnitt nehmen). Normalerweise gehen wir davon aus, dass unsere Eingaben alle gleich wahrscheinlich sind (einheitliche Wahrscheinlichkeit), aber wenn die Eingaben in der Realität nicht zu unseren Annahmen über die "durchschnittliche Eingabe" passen, sind die Berechnungen der durchschnittlichen Ausgaben/Laufzeiten möglicherweise bedeutungslos. Wenn Sie jedoch mit gleichmäßig zufälligen Eingaben rechnen, ist es sinnvoll, darüber nachzudenken!
• Amortisierter Worst-Case-Fall: Wenn Sie eine amortisierte Worst-Case-Datenstruktur verwenden, wird die Leistung garantiert innerhalb des amortisierten Worst-Case liegen... irgendwann (selbst wenn die Eingaben von einem bösen Dämon ausgewählt werden, der alles weiß und versucht, Sie zu bescheißen). Normalerweise verwenden wir diese Methode, um Algorithmen zu analysieren, die in ihrer Leistung sehr "unruhig" sind und unerwartete große Schluckaufs aufweisen, aber im Laufe der Zeit genauso gut funktionieren wie andere Algorithmen. (Wenn Ihre Datenstruktur jedoch keine Obergrenzen für die Menge an ausstehender Arbeit hat, die sie aufschieben kann, könnte ein böser Angreifer Sie vielleicht dazu zwingen, die maximale Menge an aufgeschobener Arbeit auf einmal nachzuholen.

Wenn Sie allerdings einigermaßen besorgt für einen Angreifer gibt es neben der Amortisation und dem Durchschnittsfall noch viele andere algorithmische Angriffsvektoren, über die man sich Gedanken machen muss).

Sowohl der Durchschnittsfall als auch die Amortisierung sind unglaublich nützliche Werkzeuge, um über Skalierung nachzudenken und diese zu planen.

(Siehe Unterschied zwischen Durchschnittsfall und amortisierter Analyse wenn Sie an diesem Unterthema interessiert sind).

---

Multidimensionales Big-O

Meistens sind sich die Menschen nicht bewusst, dass mehr als eine Variable am Werk ist. Bei einem Algorithmus zur Suche nach Zeichenketten kann Ihr Algorithmus zum Beispiel Zeit benötigen O([length of text] + [length of query]) , d.h. sie ist linear in zwei Variablen wie O(N+M) . Andere, naivere Algorithmen können sein O([length of text]*[length of query]) o O(N*M) . Das Ignorieren mehrerer Variablen ist eines der häufigsten Versäumnisse, die ich bei der Algorithmusanalyse sehe, und kann bei der Entwicklung eines Algorithmus zum Nachteil werden.

---

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-oblivious machen, Engpässe vermeiden, indem Sie mit RAM statt mit Festplatten arbeiten, Parallelisierung verwenden oder die Arbeit im Voraus erledigen - diese Techniken sind oft unabhängig der "Big-O"-Notation, obwohl Sie die Anzahl der Kerne oft in der Big-O-Notation von parallelen Algorithmen sehen werden.

Denken Sie auch daran, dass Ihnen das asymptotische Verhalten aufgrund versteckter Beschränkungen Ihres Programms möglicherweise nicht wirklich wichtig ist. Sie können zum Beispiel mit einer begrenzten Anzahl von Werten arbeiten:

• Wenn Sie etwas wie 5 Elemente sortieren, sollten Sie nicht die schnelle O(N log(N)) quicksort; Sie möchten die Einfügesortierung verwenden, die bei kleinen Eingaben gut funktioniert. Diese Situationen treten häufig bei Divide-and-Conquer-Algorithmen auf, bei denen das Problem in immer kleinere Teilprobleme aufgeteilt wird, z. B. bei rekursiver Sortierung, schnellen Fourier-Transformationen oder Matrixmultiplikation.
• Wenn einige Werte aufgrund einer verborgenen Tatsache effektiv begrenzt sind (z. B. ist der durchschnittliche menschliche Name bei vielleicht 40 Buchstaben und das menschliche Alter bei etwa 150 begrenzt). Sie können Ihrer Eingabe auch Grenzen auferlegen, um Begriffe effektiv konstant zu machen.

In der Praxis kann die relative Leistung von Algorithmen mit gleicher oder ähnlicher asymptotischer Leistung von anderen Faktoren abhängen, wie z. B.: andere Leistungsfaktoren (Quicksort und Mergesort sind beide O(N log(N)) aber Quicksort nutzt die Vorteile des CPU-Caches); Überlegungen, die nicht die Leistung betreffen, wie z. B. die Einfachheit der 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 in Bezug auf die Maschinenressourcen (z. B. pro Taktzyklus) und nicht pro echter Sekunde betrachten. 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. Diese Faktoren können dazu führen, dass einige grundlegende Operationen länger dauern (auch im Verhältnis zueinander), oder sogar einige Operationen asymptotisch beschleunigen oder verlangsamen (auch im Verhältnis zueinander). Die Auswirkungen können je nach Implementierung und/oder Umgebung gering oder groß sein. Wechseln Sie die Sprache oder den Rechner, um das bisschen zusätzliche Arbeit herauszuholen? Das hängt von hundert anderen Gründen ab (Notwendigkeit, Fähigkeiten, Kollegen, Produktivität des Programmierers, Geldwert Ihrer Zeit, Vertrautheit, Umgehungsmöglichkeiten, warum nicht Assembler oder GPU, usw.), die vielleicht wichtiger sind als die Leistung.

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

---

( bearbeiten : Die "Klartext"-Erklärung endet hier.)

Mathe-Zusätze

Der Vollständigkeit halber sei hier die genaue Definition der Big-O-Notation angeführt: f(x) O(g(x)) bedeutet, dass "f asymptotisch durch const*g nach oben begrenzt ist": Wenn man alles unterhalb eines endlichen Wertes von x ignoriert, gibt es eine Konstante, so dass |f(x)| const * |g(x)| . (Die anderen Symbole sind wie folgt: genau wie O bedeutet, bedeutet. Es gibt Varianten in Kleinbuchstaben: o bedeutet <, und bedeutet >.) f(x) (g(x)) bedeutet beides f(x) O(g(x)) y f(x) (g(x)) (Ober- und Untergrenze von g): Es gibt einige Konstanten, so dass f immer in dem "Band" liegt, das zwischen const1*g(x) y const2*g(x) . Dies ist die stärkste asymptotische Aussage, die man machen kann und entspricht in etwa == . (Entschuldigung, ich habe mich entschieden, die Erwähnung der Symbole für absolute Werte aus Gründen der Klarheit bis jetzt hinauszuzögern; vor allem, weil ich noch nie gesehen habe, dass negative Werte in einem Informatikkontext auftauchen).

_

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

O und sind nicht symmetrisch (n = O(n²), aber n² ist nicht O(n)), sondern symmetrisch, und (da diese Beziehungen alle transitiv und reflexiv sind), ist daher symmetrisch und transitiv und reflexiv, und teilt daher die Menge aller Funktionen in Äquivalenzklassen . Eine Äquivalenzklasse ist eine Menge von Dingen, die wir als gleich betrachten. Das heißt, dass man für jede denkbare Funktion einen kanonischen/eindeutigen "asymptotischen Vertreter" der Klasse finden kann (indem man im Allgemeinen den Grenzwert... I denken ); genauso wie man alle ganzen Zahlen in ungerade oder gerade gruppieren kann, kann man alle Funktionen mit in x-ish, log(x)^2-ish, etc... gruppieren, indem man im Grunde kleinere Terme ignoriert (aber manchmal könnte man mit komplizierteren Funktionen feststecken, die separate Klassen für sich sind).

_

El = Notation ist vielleicht die gebräuchlichere und wird sogar in Abhandlungen von weltbekannten Informatikern verwendet. Darüber hinaus ist es oft der Fall, dass Leute in einer lockeren Umgebung sagen O(...) wenn sie meinen (...) Dies ist technisch gesehen richtig, da die Menge der Dinge (exactlyThis) ist eine Teilmenge von O(noGreaterThanThis) ... und es ist einfacher zu tippen ;-)

Answer 4

EDIT: Kurze Anmerkung, dies ist mit Sicherheit verwirrend Big-O-Notation (was eine obere Grenze ist) mit der Theta-Schreibweise (was sowohl eine obere als auch eine untere Grenze ist). Meiner Erfahrung nach ist dies typisch für Diskussionen in nicht-akademischen Kreisen. Ich entschuldige mich für die entstandene Verwirrung.

In einem Satz: Wenn der Umfang eines Auftrags zunimmt, wie viel länger dauert es dann, ihn zu erledigen?

Dabei wird natürlich nur die "Größe" als Eingabe und die "benötigte Zeit" als Ausgabe verwendet - das Gleiche gilt, wenn Sie über die Speichernutzung usw. sprechen möchten.

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

• Verwendung einer Wäscheleine im Freien: Angenommen, Sie haben einen unendlich großen Garten, dann trocknet die Wäsche in O(1) Zeit. Unabhängig davon, wie viel Wäsche Sie haben, bekommt sie die gleiche Sonne und Frischluft ab, so dass die Größe keinen Einfluss auf die Trockenzeit hat.

• Wenn Sie einen Wäschetrockner benutzen, geben Sie 10 Hemden in jede Ladung, und eine Stunde später sind sie fertig. (Ignorieren Sie hier die tatsächlichen Zahlen - sie sind irrelevant.) Das Trocknen von 50 Hemden dauert also über 5 Mal so lange wie das Trocknen von 10 Hemden.

• Ich stelle alles in einen Lüftungsschrank: Wenn wir alles auf einen großen Haufen legen und es einfach der allgemeinen Wärme überlassen, wird es sehr lange dauern, bis die mittleren Hemden trocken sind. Ich möchte nicht im Detail raten, aber ich vermute, dass dies mindestens O(N^2) ist - je mehr Wäsche man wäscht, desto schneller wird die Trockenzeit.

Ein wichtiger Aspekt der "Big-O"-Notation ist, dass sie nicht sagen, welcher Algorithmus bei einer bestimmten Größe schneller sein wird. Nehmen wir eine Hashtabelle (String-Schlüssel, Integer-Wert) im Vergleich zu einem Array von Paaren (String, Integer). Ist es schneller, einen Schlüssel in der Hashtabelle oder ein Element im Array zu finden, basierend auf einer Zeichenkette? (d.h. für das Array: "Finde das erste Element, bei dem der String-Teil mit dem angegebenen Schlüssel übereinstimmt.") Hashtabellen werden im Allgemeinen mit O(1) amortisiert (~= "im Durchschnitt") - wenn sie einmal eingerichtet sind, sollte es etwa die gleiche Zeit dauern, einen Eintrag in einer Tabelle mit 100 Einträgen zu finden wie in einer Tabelle mit 1.000.000 Einträgen. Die Suche nach einem Element in einem Array (basierend auf dem Inhalt und nicht auf dem Index) ist linear, d. h. O(N) - im Durchschnitt müssen Sie die Hälfte der Einträge durchsuchen.

Macht dies eine Hashtable schneller als ein Array für Lookups? Nicht unbedingt. Wenn Sie eine sehr kleine Sammlung von Einträgen haben, kann ein Array durchaus schneller sein - Sie können alle Zeichenketten in der Zeit überprüfen, die Sie brauchen, um den Hashcode der gesuchten Zeichenkette zu berechnen. Wenn die Datenmenge jedoch größer wird, wird die Hashtabelle das Array schließlich schlagen.

Answer 5

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

Beispiele:

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

• O(n 2 ): Bei Verdoppelung der Eingabegröße vervierfacht sich die Laufzeit

• O(log n): Bei Verdoppelung der Eingabegröße erhöht sich die Laufzeit um eins

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

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