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

Question

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

Answer 1

" Wie lautet eine einfache englische Erklärung von Big O? Mit möglichst wenig formaler Definition wie möglich und einfacher Mathematik. "

Eine so schön einfache und kurze Frage scheint zumindest eine ebenso kurze Antwort zu verdienen, wie sie ein Schüler in der Nachhilfe erhalten könnte.

Die Big-O-Notation gibt einfach an, in welcher Zeit* ein Algorithmus ablaufen kann, in Form von nur die Menge der Eingabedaten **.

( *in einer wunderbaren, gerätefrei Zeitgefühl!)
(**Darauf kommt es an, denn die Menschen werden immer mehr wollen ob sie heute oder morgen leben)

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

• Praktisch gesehen ist die Big-O-Analyse so nützlich und wichtig weil Big O den Schwerpunkt auf den Algorithmus legt, der eigene Komplexität und vollständig ignoriert alles, was nur eine Proportionalitätskonstante ist, wie eine JavaScript-Engine, die Geschwindigkeit einer CPU, Ihre Internetverbindung und all die Dinge, die schnell so lächerlich veraltet sind wie ein Modell T . Big O konzentriert sich nur auf die Leistung, die für Menschen, die in der Gegenwart oder in der Zukunft leben, genauso wichtig ist.

• Die Big-O-Notation wirft auch ein Schlaglicht auf das wichtigste Prinzip der Computerprogrammierung, das alle guten Programmierer dazu anspornt, weiter zu denken und zu träumen: Die einzige Möglichkeit, Ergebnisse zu erzielen, die über den langsamen Vormarsch der Technologie hinausgehen, besteht darin einen besseren Algorithmus erfinden .

Answer 2

Mit der Big-O-Notation lässt sich beschreiben, wie schnell ein Algorithmus bei einer beliebigen Anzahl von Eingabeparametern, die wir als "n" bezeichnen, ausgeführt wird. Sie ist in der Informatik nützlich, weil verschiedene Maschinen mit unterschiedlichen Geschwindigkeiten arbeiten und die bloße Angabe, dass ein Algorithmus 5 Sekunden benötigt, nicht viel aussagt. Denn während Sie vielleicht ein System mit einem 4,5 GHz-Octo-Core-Prozessor verwenden, verwende ich vielleicht ein 15 Jahre altes System mit 800 MHz, das unabhängig vom Algorithmus länger brauchen könnte. Anstatt also anzugeben, wie schnell ein Algorithmus in Bezug auf die Zeit läuft, sagen wir, wie schnell er in Bezug auf die Anzahl der Eingabeparameter, oder "n", läuft. Indem wir Algorithmen auf diese Weise beschreiben, können wir die Geschwindigkeit von Algorithmen vergleichen, ohne die Geschwindigkeit des Computers selbst berücksichtigen zu müssen.

Answer 3

Big O

f (x) = O( g (x)), wenn x nach a geht (z. B. a = +), bedeutet, dass es eine Funktion gibt k derart, dass:

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

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

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

Klein o

Übrigens, hier zum Vergleich die Definition von small o.

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

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

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

Beispiele

• sin x = O(x), wenn x 0 ist.

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

• x 2 + x = O(x) wenn x 0,

• x 2 + x = O(x 2 ), wenn x +,

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

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

Weitere Beispiele

• O(1) = O(n) = O(n 2 ), wenn n + (aber nicht andersherum, die Gleichheit ist "unecht"),

• O(n) + O(n 2 ) = O(n 2 ), wenn n +

• O(O(n 2 )) = O(n 2 ), wenn n +

• O(n 2 )O(n 3 ) = O(n 5 ), wenn n +

---

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

Answer 4

Sie wollen alles über Big O wissen? Das will ich auch.

Wenn ich also vom großen O spreche, werde ich Wörter verwenden, die nur einen Takt enthalten. Ein Laut pro Wort. Kleine Wörter sind schnell. Du kennst diese Wörter, und ich auch. Wir werden Wörter mit einem Laut verwenden. Sie sind klein. Ich bin sicher, dass du alle Wörter kennst, die wir verwenden werden!

Lassen Sie uns jetzt über die Arbeit sprechen. Die meiste Zeit mag ich die Arbeit nicht. Mögen Sie die Arbeit? Es mag sein, dass Sie es tun, aber ich bin sicher, dass ich es nicht tue.

Ich gehe nicht gerne zur Arbeit. Ich mag es nicht, Zeit bei der Arbeit zu verbringen. Wenn es nach mir ginge, würde ich am liebsten nur spielen und lustige Dinge tun. Geht es Ihnen auch so wie mir?

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

Hier ist also die große Neuigkeit: Das große O kann mir helfen, nicht zu arbeiten! Ich kann mehr spielen, wenn ich das große O kenne. Weniger Arbeit, mehr Spiel! Das ist es, was das große O mir hilft.

Jetzt habe ich etwas Arbeit. Ich habe diese Liste: eins, zwei, drei, vier, fünf, sechs. Ich muss alle Dinge auf dieser Liste hinzufügen.

Wow, ich hasse Arbeit. Aber gut, ich muss das tun. Also, los geht's.

Eins plus zwei ist drei... plus drei ist sechs... und vier ist... Ich weiß es nicht mehr. Ich habe mich verlaufen. Es ist zu schwer für mich, es in meinem Kopf zu machen. Ich mache mir nicht viel aus dieser Art von Arbeit.

Machen wir uns also nicht die Arbeit. Überlegen wir uns einfach, wie schwer das ist. Wie viel Arbeit müsste ich machen, um sechs Zahlen zu addieren?

Nun, mal sehen. Ich muss eins und zwei addieren, und dann addiere ich das zu drei, und dann addiere ich das zu vier Alles in allem zähle ich sechs Additionen. Ich muss sechs Mal addieren, um das Problem zu lösen.

Hier kommt Big O, um uns zu sagen, wie schwer diese Mathematik ist.

Big O sagt: Wir müssen sechs zusätzliche Maßnahmen ergreifen, um dieses Problem zu lösen. Eine Addition, für jede Sache von eins bis sechs. Sechs kleine Stücke Arbeit... jedes Stück Arbeit ist eine Addition.

Nun, ich werde mir nicht die Mühe machen, sie jetzt hinzuzufügen. Aber ich weiß, wie schwer das wäre. Es wären sechs Einträge.

Oh nein, jetzt habe ich noch mehr Arbeit. Puh. Wer macht denn so was?!

Jetzt werde ich aufgefordert, von eins bis zehn zu addieren! Warum sollte ich das tun? Ich wollte nicht von eins bis sechs addieren. Von eins bis zehn zu addieren na ja das wäre ja noch schwieriger!

Wie viel schwieriger würde es werden? Wie viel mehr Arbeit müsste ich leisten? Brauche ich mehr oder weniger Schritte?

Nun, ich denke, ich müsste zehn Einträge machen einen für jede Sache von eins bis zehn. Zehn ist mehr als sechs. Ich müsste also viel mehr arbeiten, um von eins bis zehn zu addieren, als von eins bis sechs!

Ich möchte im Moment nichts hinzufügen. Ich möchte nur darüber nachdenken, wie schwer es sein könnte, so viel hinzuzufügen. Und ich hoffe, dass ich so bald wie möglich spielen kann.

Um von einem auf sechs zu kommen, ist das eine Menge Arbeit. Aber sehen Sie, von eins bis zehn zu addieren, das ist mehr Arbeit?

Big O ist dein und mein Freund. Big O hilft uns zu überlegen, wie viel Arbeit wir zu erledigen haben, damit wir planen können. Und wenn wir mit Big O befreundet sind, kann er uns helfen, eine Arbeit auszuwählen, die nicht so schwer ist!

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

Die neue Arbeit lautet: Alle Dinge von eins bis n addieren.

Moment! Was ist n? Habe ich das verpasst? Wie kann ich von eins zu n addieren, wenn du mir nicht sagst, was n ist?

Nun, ich weiß nicht, was n ist. Das wurde mir nicht gesagt. Wurde es dir gesagt? Nein? Na dann. Also können wir die Arbeit nicht machen. Uff.

Aber auch wenn wir die Arbeit jetzt nicht machen, können wir erahnen, wie schwer es wäre, wenn wir n wüssten. Wir müssten n Dinge zusammenzählen, oder? Ja, natürlich!

Jetzt kommt Big O, und er wird uns sagen, wie schwer diese Arbeit ist. Er sagt: Alle Dinge von eins bis N zu addieren, eins nach dem anderen, ist O(n). Um all diese Dinge zu addieren, [Ich weiß, dass ich n-mal addieren muss.][1] Das ist Big O! Er sagt uns, wie schwer es ist, eine bestimmte Art von Arbeit zu tun.

Für mich ist Big O ein großer, langsamer Mann, der das Sagen hat. Er denkt an die Arbeit, aber er tut sie nicht. Er könnte sagen: "Die Arbeit ist schnell erledigt." Oder er könnte sagen: "Diese Arbeit ist so langsam und schwer!" Aber er tut die Arbeit nicht. Er sieht sich die Arbeit nur an und sagt uns dann, wie viel Zeit sie brauchen könnte.

Ich kümmere mich viel um Big O. Warum? Ich arbeite nicht gerne! Niemand arbeitet gerne. Deshalb lieben wir alle Big O! Er sagt uns, wie schnell wir arbeiten können. Er hilft uns, daran zu denken, wie schwer Arbeit ist.

Oh oh, noch mehr Arbeit. Also, lassen wir die Arbeit liegen. Aber lass uns einen Plan machen, wie wir es Schritt für Schritt machen.

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

Igitt. Das klingt nach einer Menge Arbeit!

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

Ich werde mir jedes Kartenpaar, Paar für Paar, vom ersten bis zum letzten Kartenspiel ansehen. Wenn die erste Karte in einem Paar groß und die nächste Karte in diesem Paar klein ist, tausche ich sie aus. Andernfalls gehe ich zum nächsten Paar über, und so weiter und so fort... und bald ist das Deck fertig.

Wenn das Deck fertig ist, frage ich: Habe ich in diesem Durchgang Karten ausgetauscht? Wenn ja, muss ich das Ganze noch einmal von vorne machen.

Irgendwann wird es keine Tauschaktionen mehr geben, und wir sind mit dem Deck fertig. So viel Arbeit!

Wie viel Arbeit wäre es denn, die Karten nach diesen Regeln zu sortieren?

Ich habe zehn Karten. Und die meiste Zeit - das heißt, wenn ich nicht viel Glück habe - muss ich das ganze Deck bis zu zehnmal durchgehen, wobei ich jedes Mal bis zu zehn Karten austauschen muss.

Big O, hilf mir!

Big O kommt ins Spiel und sagt: Für ein Kartenspiel mit n Karten wird das Sortieren auf diese Weise in O(N quadriert) Zeit erledigt.

Warum sagt er n zum Quadrat?

Nun, Sie wissen, dass n zum Quadrat n mal n ist. Jetzt verstehe ich es: n Karten überprüft, bis zu dem, was n mal durch den Stapel sein könnte. Das sind zwei Schleifen, jede mit n Schritten. Das ist n quadriert viel Arbeit, die getan werden muss. Eine Menge Arbeit, ganz sicher!

Wenn Big O sagt, dass es O(n zum Quadrat) Arbeit erfordert, dann meint er damit nicht n zum Quadrat, sondern mehr. In manchen Fällen könnte es etwas weniger sein. Aber im schlimmsten Fall sind es fast n quadratische Schritte Arbeit, um das Deck zu sortieren.

Und hier ist Big O unser Freund.

Big O weist darauf hin, dass die Arbeit beim Sortieren von Karten, wenn n groß wird, VIEL VIEL SCHWERER wird als die alte Arbeit, bei der man nur diese Dinge hinzufügt. Woher wissen wir das?

Nun, wenn n sehr groß wird, ist es uns egal, was wir zu n oder n zum Quadrat addieren können.

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

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

Big O erledigt die Arbeit nicht für uns. Big O sagt uns, wie schwer die Arbeit ist.

Ich habe ein Kartenspiel. Ich habe sie sortiert. Du hast mir geholfen. Danke!

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

Ja, es gibt einen schnelleren Weg! Man braucht etwas Zeit, um ihn zu lernen, aber er funktioniert... und er funktioniert ziemlich schnell. Du kannst es auch versuchen, aber nimm dir bei jedem Schritt Zeit und verliere nicht deinen Platz.

Bei dieser neuen Art, einen Stapel zu sortieren, werden keine Kartenpaare mehr geprüft, wie wir es vor einiger Zeit getan haben. Hier sind die neuen Regeln zum Sortieren dieses Decks:

Eins: Ich wähle eine Karte aus dem Teil des Decks, an dem wir gerade arbeiten. Du kannst eine für mich wählen, wenn du möchtest. (Wenn wir das zum ersten Mal machen, ist "der Teil des Decks, an dem wir jetzt arbeiten" natürlich das ganze Deck).

Zwei: Ich lege das Deck auf die von Ihnen gewählte Karte. Was ist dieses Ausspielen; wie spiele ich aus? Nun, ich gehe von der Startkarte abwärts, eine nach der anderen, und suche nach einer Karte, die höher ist als die Ausspielkarte.

Drittens: Ich gehe von der letzten Karte aufwärts und suche nach einer Karte, die niedriger ist als die ausgespielte Karte.

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

Irgendwann wird diese Schleife (von Zwei zu Drei) enden. Sie endet, wenn sich beide Hälften dieser Suche bei der gespreizten Karte treffen. Dann haben wir gerade den Stapel mit der Karte, die Sie in Schritt Eins gewählt haben, aufgespannt. Jetzt sind alle Karten in der Nähe des Starts niedriger als die gespreizte Karte, und die Karten in der Nähe des Endes sind höher als die gespreizte Karte. Cooler Trick!

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

Ich zerlege das Deck in Teile und sortiere jeden Teil, immer kleiner und kleiner, und irgendwann habe ich keine Arbeit mehr zu tun. Das mag jetzt langsam erscheinen, mit all den Regeln. Aber glauben Sie mir, es ist überhaupt nicht langsam. Es ist viel weniger Arbeit als die erste Art, die Dinge zu sortieren!

Wie wird diese Sortierung genannt? Sie wird Quick Sort genannt! Diese Sorte wurde von einem Mann namens C. A. R. Hoare und er nannte es Quick Sort. Jetzt wird Quick Sort ständig verwendet!

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

Hmmm. Ich glaube, da steckt eine Regel drin. Um große Aufgaben klein zu machen, muss man sie aufteilen.

Diese Sorte ist recht schnell. Wie schnell? Big O sagt uns: Diese Sortierung benötigt im mittleren Fall O(n log n) Arbeit.

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

Die erste Sortierung war O(n quadriert). Aber Quick Sort ist O(n log n). Sie wissen, dass n log n kleiner ist als n zum Quadrat, wenn n groß ist, nicht wahr? Daher wissen wir, dass Quick Sort schnell ist!

Wenn Sie ein Deck sortieren müssen, was ist die beste Methode? Nun, Sie können tun, was Sie wollen, aber ich würde Quick Sort wählen.

Warum wähle ich Quick Sort? Ich arbeite natürlich nicht gerne! Ich möchte die Arbeit so schnell wie möglich erledigen.

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

Jetzt kennen Sie meinen Freund Big O. Er hilft uns, weniger Arbeit zu machen. Und wenn du Big O kennst, kannst du auch weniger Arbeit machen!

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

Jetzt ist die Arbeit getan, gehen wir spielen!

---

[1]: Es gibt eine Möglichkeit, zu schummeln und alle Dinge von eins bis n auf einmal zu addieren. Ein Junge namens Gauß hat das herausgefunden, als er acht Jahre alt war. Ich bin allerdings nicht so schlau, also Fragen Sie mich nicht, wie er es gemacht hat. .

Answer 5

Ich bin mir nicht sicher, ob ich einen weiteren Beitrag zum Thema leiste, aber ich dachte, ich erzähle es trotzdem: Ich fand einmal dieser Blogbeitrag einige recht hilfreiche (wenn auch sehr grundlegende) Erklärungen und Beispiele zu Big O:

Anhand von Beispielen konnte ich mir die nackten Grundlagen in meinen schildpattähnlichen Schädel einprägen, so dass ich denke, dass die 10-minütige Lektüre einen guten Einstieg in die richtige Richtung darstellt.