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

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

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


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

    Große O-Analyse

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

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

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

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

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

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

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

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

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

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

    Siehst du 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) oder lineare Komplexität .

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

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

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

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

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

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

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

    Das Telefonbuch

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

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

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

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

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

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

    Das ist erstaunlich gut, nicht wahr?

    In Big-O-Termen ist dies O (log n) oder logarithmische Komplexität . Nun könnte der betreffende Logarithmus ln (Basis e), log 10 , log 2 oder irgendeine andere Basis sein. Es spielt keine Rolle, dass es immer noch O (log n) ist, genau wie O (2n 2 ) und O (100n 2 ) immer noch beide O (n 2 ) sind.

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

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

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

    Zurück zum Telefonbuch.

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

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

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

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

    Der fahrende Verkäufer

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

    Klingt einfach? Denk nochmal.

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

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

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

    In Wirklichkeit gibt es 3 Möglichkeiten.

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

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

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

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

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

    Etwas zum Nachdenken.

    Polynomzeit

    Ein weiterer Punkt, den ich kurz erwähnen möchte, ist, dass jeder Algorithmus, der eine Komplexität von O (na) hat, Polynomkomplexität hat oder in polynomieller Zeit lösbar ist.

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

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

    Es zeigt, wie ein Algorithmus skaliert.

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

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

    Beachten Sie, dass sich die Anzahl der Elemente um den Faktor 10 erhöht, die Zeit jedoch um den Faktor 10 2 zunimmt. Im Grunde ist n = 10 und O (n 2 ) gibt uns den Skalierungsfaktor n 2, der 10 2 ist .

    O (n) : als lineare Komplexität bekannt

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

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

    O (1) : bekannt als konstante Komplexität

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

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

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

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

    Die Anzahl der Berechnungen wird nur um einen Logarithmus des Eingabewerts erhöht. Wenn also in diesem Fall angenommen wird, dass jede Berechnung 1 Sekunde dauert, ist der Logarithmus der Eingabe n die benötigte Zeit, also log n .

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

    Die Big-O-Notation (auch “asymptotisches Wachstum” -Notation genannt) funktioniert wie “aussehen”, wenn Sie konstante Faktoren und Dinge in der Nähe des Ursprungs ignorieren . Wir verwenden es, um darüber zu sprechen, wie das Ding skaliert .


    Grundlagen

    für “ausreichend” große Eingänge …

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

    Die Groß-O-Notation kümmert sich nicht um konstante Faktoren: Die function 9x² soll “genau wie” 10x² wachsen. Keine asymptotische Groß-O-Notation kümmert sich auch um nicht-asymptotische Sachen (“Zeug nahe dem Ursprung” oder “Was passiert, wenn die Problemgröße klein ist”): Die function 10x² soll “genau wie” 10x² - x + 2 wachsen.

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

    Anders ausgedrückt, dreht sich alles um das Verhältnis, wenn Sie ins Unendliche gehen. Wenn Sie die tatsächliche Zeit durch den O(...) teilen, erhalten Sie einen konstanten Faktor in der Grenze der großen Eingaben. Intuitiv macht das Sinn: functionen “skalieren” sich gegenseitig, wenn man die eine multiplizieren kann, um die andere zu bekommen. Das heißt, wenn wir sagen …

     actualAlgorithmTime(N) ∈ O(bound(N)) eg "time to mergesort N elements is O(N log(N))" 

    … das bedeutet, dass für “groß genug” Problemgrößen N (wenn wir Zeug in der Nähe des Ursprungs ignorieren) eine Konstante (z. B. 2,5, vollständig zusammengesetzt) ​​existiert, so dass:

     actualAlgorithmTime(N) eg "mergesort_duration(N) " ────────────────────── < constant ───────────────────── < 2.5 bound(N) N log(N) 

    Es gibt viele Möglichkeiten der Konstanten; oft ist die "beste" Wahl bekannt als der "konstante Faktor" des Algorithmus ... aber wir ignorieren sie oft, als ob wir nicht-größte Terme ignorieren würden (siehe Abschnitt Konstante Faktoren für warum sie normalerweise keine Rolle spielen). Man kann sich auch die obige Gleichung als eine Grenze vorstellen: " Im schlimmsten Fall wird die Zeit niemals schlechter sein als ungefähr N*log(N) , innerhalb eines Faktors von 2,5 (ein konstanter Faktor, den wir nicht anwenden) t interessieren Sie sich sehr) ".

    Im Allgemeinen ist O(...) das nützlichste, weil uns oft das Worst-Case-Verhalten am Herzen liegt. Wenn f(x) etwas "schlechtes" wie processor- oder Speichernutzung darstellt, dann bedeutet " f(x) ∈ O(upperbound) " " upperbound ist das Worst-Case-Szenario der processor- / Speichernutzung".


    Anwendungen

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

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

    Beispiel

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

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

    Jeder schüttelt alle anderen. Bildkredit und Lizenz per Wikipedia / Wikimedia Commons Adjazenzmatrix

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

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

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

    (vorübergehender Exkurs von "einfachem Englisch" 🙂 Wenn du das selbst beweisen willst, könntest du eine einfache Algebra über das Verhältnis machen, um es in mehrere Begriffe aufzuteilen ( lim bedeutet "in der Grenze von" betrachtet), ignoriere es einfach wenn Du hast es nicht gesehen, es ist nur Notation für "und N ist wirklich sehr groß"):

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

    tl; dr: Die Anzahl der Handshakes sieht bei großen Werten wie 'x² aus. Wenn wir das Verhältnis # handshakes / x² aufschreiben würden, würde die Tatsache, dass wir nicht genau x² Handshakes benötigen , nicht einmal auftauchen in der Dezimalzahl für eine beliebig lange Zeit.

    zB für x = 1million, ratio # handshakes / x²: 0.499999 ...


    Gebäudeintuition

    So können wir Aussagen machen wie ...

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

    • ... Ich verdopple die Zeit, die ein O (N) ("linearer Zeit") Algorithmus braucht. "

      N → (2N) = 2 ( N )

    • ... Ich habe die Zeit verdoppelt, die ein O (N²) ("quadratischer Zeit" -Algorithmus benötigt). (ZB ein Problem 100x so groß dauert 100² = 10000x so lang ... möglicherweise nicht nachhaltig)

      → (2N) ² = 4 ( )

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

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

    • ... Ich füge einen festen Betrag zu der Zeit hinzu, die ein O (log (N)) ("logarithmischer Zeit") Algorithmus benötigt. " (Billig!)

      c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (feste Menge) + ( c log (N) )

    • ... Ich ändere nicht die Zeit, die ein O (1) ("Konstante Zeit") Algorithmus braucht. " (Das billigste!)

      c * 1c * 1

    • ... Ich "verdopple" im Prinzip die Zeit, die ein O (N log (N)) Algorithmus braucht. (Ziemlich häufig)

      Es ist weniger als O (N 1.000001 ), was Sie vielleicht grundsätzlich linear nennen möchten

    • ... Ich vergrößere lächerlich die Zeit, die ein O (2 N ) ("Exponentialzeit") - Algorithmus benötigt. " (Sie würden die Zeit verdoppeln (oder verdreifachen, etc.), indem Sie das Problem um eine einzige Einheit erhöhen)

      2 N → 2 2 N = (4 N ) ............ anders ausgedrückt ...... 2 N → 2 N + 1 = 2 N 2 1 = 2 2 N

    [für die mathematisch geneigt, können Sie Maus für kleinere Nebenbemerkungen über die Spoiler]

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

    (technisch könnte der konstante Faktor vielleicht in einigen mehr esoterischen Beispielen eine Rolle spielen, aber ich habe Dinge oben gesagt (zB in log (N)), so dass es nicht so ist)

    Dies sind die Wachstumsbefehle, die Programmierer und angewandte Informatiker als Referenzpunkte verwenden. Sie sehen diese die ganze Zeit. (Obwohl man technisch denken könnte "Verdoppelung der Eingabe macht einen O (√N) Algorithmus 1.414 mal langsamer", ist es besser, es als "das ist schlimmer als logarithmisch, aber besser als linear" zu verstehen).


    Konstante Faktoren

    Normalerweise ist es uns egal, was die spezifischen konstanten Faktoren sind, weil sie die Art, wie die function wächst, nicht beeinflussen. Zum Beispiel können zwei Algorithmen beide O(N) -Zeit benötigen, um abgeschlossen zu werden, aber eine kann zweimal so langsam wie die andere sein. Normalerweise ist uns das nicht so wichtig, es sei denn, der Faktor ist sehr groß, da die Optimierung schwierig ist ( Wann ist die Optimierung zu früh? ); Auch der bloße Akt der Auswahl eines Algorithmus mit einem besseren Big-O verbessert oft die performance um Größenordnungen.

    Einige asymptotisch überlegene Algorithmen (z. B. eine Nicht-Vergleichs- O(N log(log(N))) Sortierung) können einen so großen konstanten Faktor (z. B. 100000*N log(log(N)) ) oder einen relativ großen Overhead haben wie O(N log(log(N))) mit einem versteckten + 100*N , das sie selbst bei "Big Data" selten wert sind.


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

    O(N) Algorithmen sind in gewisser Weise die "besten" Algorithmen, wenn Sie all Ihre Daten lesen müssen. Der Vorgang des Lesens einer Menge von Daten ist eine O(N) -Operation. 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 jedes Datenelement (oder sogar jedes andere Datenelement) anfassen oder sogar betrachten , benötigt Ihr Algorithmus eine Zeit von O(N) , um dieses Suchen durchzuführen. Wie lange Ihr Algorithmus dauert, wird mindestens O(N) weil er sich die Zeit genommen hat, alle Daten zu betrachten.

    Dasselbe kann für den Akt des Schreibens gesagt werden. Alle Algorithmen, die N Dinge ausgeben, benötigen N Zeit, weil die Ausgabe mindestens so lang ist (zB das Ausdrucken aller Permutationen (Möglichkeiten zum Umordnen) eines Satzes von N Spielkarten ist faktoriell: O(N!) ).

    Dies motiviert die Verwendung von Datenstrukturen : eine Datenstruktur erfordert das Lesen der Daten nur einmal (normalerweise O(N) Zeit), zuzüglich einer beliebigen Menge an Vorverarbeitung (zB O(N) oder O(N log(N)) oder O(N²) ) was wir versuchen klein zu halten. Danach dauert das Ändern der Datenstruktur (Einfügungen / Löschungen / usw.) und Abfragen der Daten sehr wenig Zeit, beispielsweise O(1) oder O(log(N)) . Sie fahren dann fort, eine große Anzahl von Abfragen zu machen! Je mehr Arbeit Sie im Voraus leisten möchten, desto weniger Arbeit müssen Sie später erledigen.

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

    • Naive Methode: Wenn Sie die Koordinaten einer Straßenkreuzung hätten und die Straßen in der Nähe untersuchen wollten, müssten Sie jedes Mal die Millionen von Segmenten durchgehen und jedes für die Nachbarschaft überprüfen.
    • Wenn du das nur einmal machen müsstest, wäre es kein Problem, die naive Methode der O(N) Arbeit nur einmal zu machen, aber wenn du es mehrmals machen willst (in diesem Fall N mal, einmal für jedes Segment), müssten wir O(N²) arbeiten oder 1000000² = 1000000000000 Operationen. Nicht gut (ein moderner Computer kann etwa eine Milliarde Operationen pro Sekunde ausführen).
    • Wenn wir eine einfache Struktur verwenden, die Hash-Tabelle genannt wird (eine Instant-Speed-Lookup-Tabelle, auch bekannt als Hashmap oder Dictionary), zahlen wir einen kleinen Preis, indem wir alles in O(N) -Zeit vorverarbeiten. Danach braucht man im Durchschnitt nur eine konstante Zeit, um etwas nach seinem Schlüssel zu suchen (in diesem Fall ist unser Schlüssel die Breiten- und Längenkoordinaten, gerundet in ein Gitter; wir suchen die benachbarten Gitterräume, von denen es nur 9 gibt, was a ist Konstante).
    • Unsere Aufgabe ging von einem undurchführbaren O(N²) zu einem überschaubaren O(N) , und alles, was wir zu tun hatten, war die Zahlung kleinerer Kosten, um eine Hashtabelle zu erstellen.
    • 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 Farbe und Muster. Wir nutzen dies aus, um später zusätzliche Arbeit zu vermeiden (Vergleich von Puzzleteilen gleicher Farbe miteinander und nicht mit jedem anderen Puzzlestück).

    Die Moral der Geschichte: Eine Datenstruktur lässt uns Operationen beschleunigen. Mit fortschrittlicheren Datenstrukturen können Sie Vorgänge auf unglaublich clevere Weise kombinieren, verzögern oder sogar ignorieren. Unterschiedliche Probleme hätten unterschiedliche Analogien, aber sie würden alle dazu führen, die Daten so zu organisieren, dass sie eine Struktur ausnutzen, die uns wichtig ist, oder die wir künstlich für die Buchhaltung eingeführt haben. Wir arbeiten vor der Zeit (im Grunde planen und organisieren), und jetzt sind wiederholte Aufgaben viel einfacher!


    Praktisches Beispiel: Visualisieren von Wachstumsstufen beim Codieren

    Die asymptotische Notation ist in ihrem core ziemlich von der Programmierung getrennt. Die asymptotische Notation ist ein mathematischer Rahmen, um darüber nachzudenken, wie Dinge skalieren, und kann in vielen verschiedenen Bereichen verwendet werden. Das heißt ... so wenden Sie die asymptotische Notation auf die Codierung an.

    Die Grundlagen: Wann immer wir mit jedem Element in einer Sammlung der Größe A interagieren (z. B. ein Array, ein Satz, alle Schlüssel einer Karte usw.) oder A Wiederholungen einer Schleife durchführen, ist dies ein Multiplikationsfaktor der Größe A Warum sage ich "einen multiplikativen Faktor" - weil Schleifen und functionen (fast per definitionem) multiplikative Laufzeit haben: die Anzahl der Iterationen, die Zeit, die in der Schleife gearbeitet wird (oder für functionen: die Anzahl der Aufrufe der function, mal Arbeit in der function erledigt). (Dies gilt, wenn wir nichts Besonderes machen, wie Skip-Loops oder die Schleife vorzeitig beenden oder den Kontrollfluss in der function basierend auf Argumenten ändern, was sehr häufig ist.) Hier sind einige Beispiele von Visualisierungstechniken mit begleitendem Pseudocode.

    (Hier stehen die x s für konstante Zeiteinheiten der Arbeit, processoranweisungen, Interpreter-Opcodes, was auch immer)

     for(i=0; i A*1 --> O(A) time visualization: |< ------ A ------->| 1 2 3 4 5 xx ... 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 x ... some O(1) operation // 1 some O(B) operation // B for every y in listOfSizeC: // C x ... some O(1) operation // 1 --> O(A*(1 + B + C)) O(A*(B+C)) (1 is dwarfed) visualization: |< ------ A ------->| 1 xxxxxx ... x 2 xxxxxx ... x ^ 3 xxxxxx ... x | 4 xxxxxx ... x | 5 xxxxxx ... x B < -- A*B xxxxxxx ... x | ................... | xxxxxxx ... xv xxxxxxx ... x ^ xxxxxxx ... x | xxxxxxx ... x | xxxxxxx ... x C <-- A*C xxxxxxx ... x | ................... | xxxxxxx ... xv 

    Beispiel 3:

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

    Wenn wir etwas Kompliziertes machen, können Sie sich vielleicht visuell vorstellen, was vor sich geht:

     for x in range(A): for y in range(1..x): simpleOperation(x*y) xxxxxxxxxx | xxxxxxxxx | xxxxxxxx | xxxxxxx | xxxxxx | xxxxx | xxxx | xxx | xx | x___________________| 

    Hier ist der kleinste erkennbare Umriss, den Sie zeichnen können, wichtig. ein Dreieck ist eine zweidimensionale Form (0,5 A ^ 2), genau wie ein Quadrat eine zweidimensionale Form (A ^ 2) ist; der konstante Faktor von zwei bleibt hier im asymptotischen Verhältnis zwischen den beiden, aber wir ignorieren es wie alle Faktoren ... (Es gibt einige unglückliche Nuancen zu dieser Technik, auf die ich hier nicht eingehe; sie können dich in die Irre führen.)

    Natürlich bedeutet das nicht, dass Schleifen und functionen 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 und functionen und Bedingungen mit unseren Daten (Kontrollfluss usw.) verknüpfen, den Zeit- und Raumverbrauch unseres Programms nachahmt! Wenn Zeit und Raumnutzung zu einem Problem werden, dann greifen wir auf Klugheit zurück und finden einen einfachen Algorithmus oder eine Datenstruktur, die wir nicht berücksichtigt haben, um die Wachstumsordnung irgendwie zu reduzieren. Dennoch können diese Visualisierungstechniken (obwohl sie nicht immer funktionieren) Ihnen eine naive Vermutung über die ungünstigste Laufzeit geben.

    Hier ist eine andere Sache, die wir visuell erkennen können:

     < ----------------------------- N -----------------------------> xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxx xxxx xx x 

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

     < ----------------------------- N -----------------------------> xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxx|xxxxxxxx|xxxx|xx|x 

    Oder vielleicht loggen Sie (N) die Daten durch, für O (N * log (N)) Gesamtzeit:

      < ----------------------------- N -----------------------------> ^ xxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxx | xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx lgN xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx | xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx|xx vx|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x 

    Unzusammenhängend, aber erwähnenswert: Wenn wir einen Hash durchführen (zB ein Dictionary / Hashtable Lookup), 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, etwa mit einer rekursiven function oder einem Divide-and-Conquer-Algorithmus, können Sie den Hauptsatz verwenden (normalerweise funktioniert das) oder in lächerlichen Fällen den Satz von Akra-Bazzi (fast immer) Laufzeit Ihres Algorithmus auf Wikipedia.

    Aber Programmierer denken nicht so, weil schließlich die Intuition des Algorithmus zur zweiten Natur wird. Sie fangen an, etwas Ineffizientes zu programmieren und denken sofort: "Mache ich etwas sehr ineffizientes? ". Wenn die Antwort "Ja" ist und Sie voraussehen, dass es wirklich wichtig ist, dann können Sie einen Schritt zurück machen und an verschiedene Tricks denken, um die Dinge schneller laufen zu lassen (die Antwort ist fast immer "benutzen Sie eine Hashtabelle", selten "benutzen Sie einen Baum"), und sehr selten etwas etwas komplizierter).


    Amortisierte und durchschnittliche Komplexität

    Es gibt auch das Konzept der "amortisierten" und / oder "durchschnittlichen Fälle" (beachten Sie, dass diese unterschiedlich sind).

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

    Amortisierter Worst-Case : Einige Datenstrukturen können eine Worst-Case-Komplexität aufweisen, die groß ist, aber garantieren, dass, wenn Sie viele dieser Operationen ausführen, der durchschnittliche Arbeitsaufwand besser ist als der Worst-Case. Zum Beispiel können Sie eine Datenstruktur haben, die normalerweise eine konstante O(1) Zeit benötigt. However, occasionally it will 'hiccup' and take O(N) time for one random operation, because maybe it needs to do some bookkeeping or garbage collection or something... but it promises you that if it does hiccup, it won't hiccup again for N more operations. The worst-case cost is still O(N) per operation, but the amortized cost over many runs is O(N)/N = O(1) per operation. Because the big operations are sufficiently rare, the massive amount of occasional work can be considered to blend in with the rest of the work as a constant factor. We say the work is "amortized" over a sufficiently large number of calls that it disappears asymptotically.

    The analogy for amortized analysis:

    You drive a car. Occasionally, you need to spend 10 minutes going to the gas station and then spend 1 minute refilling the tank with gas. If you did this every time you went anywhere with your car (spend 10 minutes driving to the gas station, spend a few seconds filling up a fraction of a gallon), it would be very inefficient. But if you fill up the tank once every few days, the 11 minutes spent driving to the gas station is "amortized" over a sufficiently large number of trips, that you can ignore it and pretend all your trips were maybe 5% longer.

    Comparison between average-case and amortized worst-case:

    • Average-case: We make some assumptions about our inputs; ie if our inputs have different probabilities, then our outputs/runtimes will have different probabilities (which we take the average of). Usually we assume that our inputs are all equally likely (uniform probability), but if the real-world inputs don't fit our assumptions of "average input", the average output/runtime calculations may be meaningless. If you anticipate uniformly random inputs though, this is useful to think about!
    • Amortized worst-case: If you use an amortized worst-case data structure, the performance is guaranteed to be within the amortized worst-case... eventually (even if the inputs are chosen by an evil demon who knows everything and is trying to screw you over). Usually we use this to analyze algorithms which may be very 'choppy' in performance with unexpected large hiccups, but over time perform just as well as other algorithms. (However unless your data structure has upper limits for much outstanding work it is willing to procrastinate on, an evil attacker could perhaps force you to catch up on the maximum amount of procrastinated work all-at-once.

    Though, if you're reasonably worried about an attacker, there are many other algorithmic attack vectors to worry about besides amortization and average-case.)

    Both average-case and amortization are incredibly useful tools for thinking about and designing with scaling in mind.

    (See Difference between average case and amortized analysis if interested on this subtopic.)


    Multidimensional big-O

    Most of the time, people don't realize that there's more than one variable at work. For example, in a string-search algorithm, your algorithm may take time O([length of text] + [length of query]) , ie it is linear in two variables like O(N+M) . Other more naive algorithms may be O([length of text]*[length of query]) or O(N*M) . Ignoring multiple variables is one of the most common oversights I see in algorithm analysis, and can handicap you when designing an algorithm.


    The whole story

    Keep in mind that big-O is not the whole story. You can drastically speed up some algorithms by using caching, making them cache-oblivious, avoiding bottlenecks by working with RAM instead of disk, using parallelization, or doing work ahead of time -- these techniques are often independent of the order-of-growth "big-O" notation, though you will often see the number of cores in the big-O notation of parallel algorithms.

    Also keep in mind that due to hidden constraints of your program, you might not really care about asymptotic behavior. You may be working with a bounded number of values, for example:

    • If you're sorting something like 5 elements, you don't want to use the speedy O(N log(N)) quicksort; you want to use insertion sort, which happens to perform well on small inputs. These situations often comes up in divide-and-conquer algorithms, where you split up the problem into smaller and smaller subproblems, such as recursive sorting, fast Fourier transforms, or matrix multiplication.
    • If some values are effectively bounded due to some hidden fact (eg the average human name is softly bounded at perhaps 40 letters, and human age is softly bounded at around 150). You can also impose bounds on your input to effectively make terms constant.

    In practice, even among algorithms which have the same or similar asymptotic performance, their relative merit may actually be driven by other things, such as: other performance factors (quicksort and mergesort are both O(N log(N)) , but quicksort takes advantage of CPU caches); non-performance considerations, like ease of implementation; whether a library is available, and how reputable and maintained the library is.

    Programs will also run slower on a 500MHz computer vs 2GHz computer. We don't really consider this as part of the resource bounds, because we think of the scaling in terms of machine resources (eg per clock cycle), not per real second. However, there are similar things which can 'secretly' affect performance, such as whether you are running under emulation, or whether the compiler optimized code or not. These might make some basic operations take longer (even relative to each other), or even speed up or slow down some operations asymptotically (even relative to each other). The effect may be small or large between different implementation and/or environment. Do you switch languages or machines to eke out that little extra work? That depends on a hundred other reasons (necessity, skills, coworkers, programmer productivity, the monetary value of your time, familiarity, workarounds, why not assembly or GPU, etc...), which may be more important than performance.

    The above issues, like programming language, are almost never considered as part of the constant factor (nor should they be); yet one should be aware of them, because sometimes (though rarely) they may affect things. For example in cpython, the native priority queue implementation is asymptotically non-optimal ( O(log(N)) rather than O(1) for your choice of insertion or find-min); do you use another implementation? Probably not, since the C implementation is probably faster, and there are probably other similar issues elsewhere. There are tradeoffs; sometimes they matter and sometimes they don't.


    ( edit : The "plain English" explanation ends here.)

    Math addenda

    For completeness, the precise definition of big-O notation is as follows: f(x) ∈ O(g(x)) means that "f is asymptotically upper-bounded by const*g": ignoring everything below some finite value of x, there exists a constant such that |f(x)| ≤ const * |g(x)| . (The other symbols are as follows: just like O means ≤, Ω means ≥. There are lowercase variants: o means < , and ω means >.) f(x) ∈ Ɵ(g(x)) means both f(x) ∈ O(g(x)) and f(x) ∈ Ω(g(x)) (upper- and lower-bounded by g): there exists some constants such that f will always lie in the "band" between const1*g(x) and const2*g(x) . It is the strongest asymptotic statement you can make and roughly equivalent to == . (Sorry, I elected to delay the mention of the absolute-value symbols until now, for clarity's sake; especially because I have never seen negative values come up in a computer science context.)

    People will often use = O(...) , which is perhaps the more correct 'comp-sci' notation, and entirely legitimate to use... but one should realize = is not being used as equality; it is a compound notation that must be read as an idiom. I was taught to use the more rigorous ∈ O(...) . means "is an element of". O(N²) is actually an equivalence class , that is, it is a set of things which we consider to be the same. In this particular case, O(N²) contains elements like { 2 N² , 3 N² , 1/2 N² , 2 N² + log(N) , - N² + N^1.9 , ...} and is infinitely large, but it's still a set. The = notation might be the more common one, and is even used in papers by world-renowned computer scientists. Additionally, it is often the case that in a casual setting, people will say O(...) when they mean Ɵ(...) ; this is technically true since the set of things Ɵ(exactlyThis) is a subset of O(noGreaterThanThis) ... and it's easier to type. 😉

    EDIT: Quick note, this is almost certainly confusing Big O notation (which is an upper bound) with Theta notation (which is both an upper and lower bound). In my experience this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.

    In one sentence: As the size of your job goes up, how much longer does it take to complete it?

    Obviously that’s only using “size” as the input and “time taken” as the output — the same idea applies if you want to talk about memory usage etc.

    Here’s an example where we have N T-shirts which we want to dry. We’ll assume it’s incredibly quick to get them in the drying position (ie the human interaction is negligible). That’s not the case in real life, of course…

    • Using a washing line outside: assuming you have an infinitely large back yard, washing dries in O(1) time. However much you have of it, it’ll get the same sun and fresh air, so the size doesn’t affect the drying time.

    • Using a tumble dryer: you put 10 shirts in each load, and then they’re done an hour later. (Ignore the actual numbers here — they’re irrelevant.) So drying 50 shirts takes about 5 times as long as drying 10 shirts.

    • Putting everything in an airing cupboard: If we put everything in one big pile and just let general warmth do it, it will take a long time for the middle shirts to get dry. I wouldn’t like to guess at the detail, but I suspect this is at least O(N^2) — as you increase the wash load, the drying time increases faster.

    One important aspect of “big O” notation is that it doesn’t say which algorithm will be faster for a given size. Take a hashtable (string key, integer value) vs an array of pairs (string, integer). Is it faster to find a key in the hashtable or an element in the array, based on a string? (ie for the array, “find the first element where the string part matches the given key.”) Hashtables are generally amortised (~= “on average”) O(1) — once they’re set up, it should take about the same time to find an entry in a 100 entry table as in a 1,000,000 entry table. Finding an element in an array (based on content rather than index) is linear, ie O(N) — on average, you’re going to have to look at half the entries.

    Does this make a hashtable faster than an array for lookups? Not necessarily. If you’ve got a very small collection of entries, an array may well be faster — you may be able to check all the strings in the time that it takes to just calculate the hashcode of the one you’re looking at. As the data set grows larger, however, the hashtable will eventually beat the array.

    Big O describes an upper limit on the growth behaviour of a function, for example the runtime of a program, when inputs become large.

    Beispiele:

    • O(n): If I double the input size the runtime doubles

    • O(n 2 ): If the input size doubles the runtime quadruples

    • O(log n): If the input size doubles the runtime increases by one

    • O(2 n ): If the input size increases by one, the runtime doubles

    The input size is usually the space in bits needed to represent the input.

    Big O notation is most commonly used by programmers as an approximate measure of how long a computation (algorithm) will take to complete expressed as a function of the size of the input set.

    Big O is useful to compare how well two algorithms will scale up as the number of inputs is increased.

    More precisely Big O notation is used to express the asymptotic behavior of a function. That means how the function behaves as it approaches infinity.

    In many cases the “O” of an algorithm will fall into one of the following cases:

    • O(1) – Time to complete is the same regardless of the size of input set. An example is accessing an array element by index.
    • O(Log N) – Time to complete increases roughly in line with the log2(n). For example 1024 items takes roughly twice as long as 32 items, because Log2(1024) = 10 and Log2(32) = 5. An example is finding an item in a binary search tree (BST).
    • O(N) – Time to complete that scales linearly with the size of the input set. In other words if you double the number of items in the input set, the algorithm takes roughly twice as long. An example is counting the number of items in a linked list.
    • O(N Log N) – Time to complete increases by the number of items times the result of Log2(N). An example of this is heap sort and quick sort .
    • O(N^2) – Time to complete is roughly equal to the square of the number of items. An example of this is bubble sort .
    • O(N!) – Time to complete is the factorial of the input set. An example of this is the traveling salesman problem brute-force solution .

    Big O ignores factors that do not contribute in a meaningful way to the growth curve of a function as the input size increases towards infinity. This means that constants that are added to or multiplied by the function are simply ignored.

    Big O is just a way to “Express” yourself in a common way, “How much time / space does it take to run my code?”.

    You may often see O(n), O(n 2 ), O(nlogn) and so forth, all these are just ways to show; How does an algorithm change?

    O(n) means Big O is n, and now you might think, “What is n!?” Well “n” is the amount of elements. Imaging you want to search for an Item in an Array. You would have to look on Each element and as “Are you the correct element/item?” in the worst case, the item is at the last index, which means that it took as much time as there are items in the list, so to be generic, we say “oh hey, n is a fair given amount of values!”.

    So then you might understand what “n 2 ” means, but to be even more specific, play with the thought you have a simple, the simpliest of the sorting algorithms; bubblesort. This algorithm needs to look through the whole list, for each item.

    My list

    1. 1
    2. 6
    3. 3

    The flow here would be:

    • Compare 1 and 6, which is biggest? Ok 6 is in the right position, moving forward!
    • Compare 6 and 3, oh, 3 is less! Let’s move that, Ok the list changed, we need to start from the begining now!

    This is O n 2 because, you need to look at all items in the list there are “n” items. For each item, you look at all items once more, for comparing, this is also “n”, so for every item, you look “n” times meaning n*n = n 2

    I hope this is as simple as you want it.

    But remember, Big O is just a way to experss yourself in the manner of time and space.

    Big O describes the fundamental scaling nature of an algorithm.

    There is a lot of information that Big O does not tell you about a given algorithm. It cuts to the bone and gives only information about the scaling nature of an algorithm, specifically how the resource use (think time or memory) of an algorithm scales in response to the “input size”.

    Consider the difference between a steam engine and a rocket. They are not merely different varieties of the same thing (as, say, a Prius engine vs. a Lamborghini engine) but they are dramatically different kinds of propulsion systems, at their core. A steam engine may be faster than a toy rocket, but no steam piston engine will be able to achieve the speeds of an orbital launch vehicle. This is because these systems have different scaling characteristics with regards to the relation of fuel required (“resource usage”) to reach a given speed (“input size”).

    Why is this so important? Because software deals with problems that may differ in size by factors up to a trillion. Consider that for a moment. The ratio between the speed necessary to travel to the Moon and human walking speed is less than 10,000:1, and that is absolutely tiny compared to the range in input sizes software may face. And because software may face an astronomical range in input sizes there is the potential for the Big O complexity of an algorithm, it’s fundamental scaling nature, to trump any implementation details.

    Consider the canonical sorting example. Bubble-sort is O(n 2 ) while merge-sort is O(n log n). Let’s say you have two sorting applications, application A which uses bubble-sort and application B which uses merge-sort, and let’s say that for input sizes of around 30 elements application A is 1,000x faster than application B at sorting. If you never have to sort much more than 30 elements then it’s obvious that you should prefer application A, as it is much faster at these input sizes. However, if you find that you may have to sort ten million items then what you’d expect is that application B actually ends up being thousands of times faster than application A in this case, entirely due to the way each algorithm scales.

    Here is the plain English bestiary I tend to use when explaining the common varieties of Big-O

    In all cases, prefer algorithms higher up on the list to those lower on the list. However, the cost of moving to a more expensive complexity class varies significantly.

    O(1):

    No growth. Regardless of how big as the problem is, you can solve it in the same amount of time. This is somewhat analogous to broadcasting where it takes the same amount of energy to broadcast over a given distance, regardless of the number of people that lie within the broadcast range.

    O(log n ):

    This complexity is the same as O(1) except that it’s just a little bit worse. For all practical purposes, you can consider this as a very large constant scaling. The difference in work between processing 1 thousand and 1 billion items is only a factor six.

    O( n ):

    The cost of solving the problem is proportional to the size of the problem. If your problem doubles in size, then the cost of the solution doubles. Since most problems have to be scanned into the computer in some way, as data entry, disk reads, or network traffic, this is generally an affordable scaling factor.

    O( n log n ):

    This complexity is very similar to O( n ) . For all practical purposes, the two are equivalent. This level of complexity would generally still be considered scalable. By tweaking assumptions some O( n log n ) algorithms can be transformed into O( n ) algorithms. For example, bounding the size of keys reduces sorting from O( n log n ) to O( n ) .

    O( n 2 ):

    Grows as a square, where n is the length of the side of a square. This is the same growth rate as the “network effect”, where everyone in a network might know everyone else in the network. Growth is expensive. Most scalable solutions cannot use algorithms with this level of complexity without doing significant gymnastics. This generally applies to all other polynomial complexities – O( n k ) – as well.

    O(2 n ):

    Does not scale. You have no hope of solving any non-trivially sized problem. Useful for knowing what to avoid, and for experts to find approximate algorithms which are in O( n k ) .

    Big O is a measure of how much time/space an algorithm uses relative to the size of its input.

    If an algorithm is O(n) then the time/space will increase at the same rate as its input.

    If an algorithm is O(n 2 ) then the time/space increase at the rate of its input squared.

    und so weiter.

    It is very difficult to measure the speed of software programs, and when we try, the answers can be very complex and filled with exceptions and special cases. This is a big problem, because all those exceptions and special cases are distracting and unhelpful when we want to compare two different programs with one another to find out which is “fastest”.

    As a result of all this unhelpful complexity, people try to describe the speed of software programs using the smallest and least complex (mathematical) expressions possible. These expressions are very very crude approximations: Although, with a bit of luck, they will capture the “essence” of whether a piece of software is fast or slow.

    Because they are approximations, we use the letter “O” (Big Oh) in the expression, as a convention to signal to the reader that we are making a gross oversimplification. (And to make sure that nobody mistakenly thinks that the expression is in any way accurate).

    If you read the “Oh” as meaning “on the order of” or “approximately” you will not go too far wrong. (I think the choice of the Big-Oh might have been an attempt at humour).

    The only thing that these “Big-Oh” expressions try to do is to describe how much the software slows down as we increase the amount of data that the software has to process. If we double the amount of data that needs to be processed, does the software need twice as long to finish it’s work? Ten times as long? In practice, there are a very limited number of big-Oh expressions that you will encounter and need to worry about:

    The good:

    • O(1) Constant : The program takes the same time to run no matter how big the input is.
    • O(log n) Logarithmic : The program run-time increases only slowly, even with big increases in the size of the input.

    The bad:

    • O(n) Linear : The program run-time increases proportionally to the size of the input.
    • O(n^k) Polynomial : – Processing time grows faster and faster – as a polynomial function – as the size of the input increases.

    … and the ugly:

    • O(k^n) Exponential The program run-time increases very quickly with even moderate increases in the size of the problem – it is only practical to process small data sets with exponential algorithms.
    • O(n!) Factorial The program run-time will be longer than you can afford to wait for anything but the very smallest and most trivial-seeming datasets.

    What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

    A Plain English Explanation of the Need for Big-O Notation:

    When we program, we are trying to solve a problem. What we code is called an algorithm. Big O notation allows us to compare the worse case performance of our algorithms in a standardized way. Hardware specs vary over time and improvements in hardware can reduce the time it takes an algorithms to run. But replacing the hardware does not mean our algorithm is any better or improved over time, as our algorithm is still the same. So in order to allow us to compare different algorithms, to determine if one is better or not, we use Big O notation.

    A Plain English Explanation of What Big O Notation is:

    Not all algorithms run in the same amount of time, and can vary based on the number of items in the input, which we’ll call n . Based on this, we consider the worse case analysis, or an upper-bound of the run-time as n get larger and larger. We must be aware of what n is, because many of the Big O notations reference it.

    A simple straightforward answer can be:

    Big O represents the worst possible time/space for that algorithm. The algorithm will never take more space/time above that limit. Big O represents time/space complexity in the extreme case.

    Ok, my 2cents.

    Big-O, is rate of increase of resource consumed by program, wrt problem-instance-size

    Resource : Could be total-CPU time, could be maximum RAM space. By default refers to CPU time.

    Say the problem is “Find the sum”,

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

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

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

    For input of size “n” the program is growing at speed of “n” iterations in array. Hence Big-O is N expressed as O(n)

    Say the problem is “Find the Combination”,

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

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

    problem-instance= {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations= 5*5 =25

    For input of size "n" the program is growing at speed of "n*n" iterations in array. Hence Big-O is N 2 expressed as O(n 2 )

    Big O notation is a way of describing the upper bound of an algorithm in terms of space or running time. The n is the number of elements in the the problem (ie size of an array, number of nodes in a tree, etc.) We are interested in describing the running time as n gets big.

    When we say some algorithm is O(f(n)) we are saying that the running time (or space required) by that algorithm is always lower than some constant times f(n).

    To say that binary search has a running time of O(logn) is to say that there exists some constant c which you can multiply log(n) by that will always be larger than the running time of binary search. In this case you will always have some constant factor of log(n) comparisons.

    In other words where g(n) is the running time of your algorithm, we say that g(n) = O(f(n)) when g(n) < = c*f(n) when n > k, where c and k are some constants.

    What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.

    Such a beautifully simple and short question seems at least to deserve an equally short answer, like a student might receive during tutoring.

    Big O notation simply tells how much time* an algorithm can run within, in terms of only the amount of input data **.

    ( *in a wonderful, unit-free sense of time!)
    (**which is what matters, because people will always want more , whether they live today or tomorrow)

    Well, what’s so wonderful about Big O notation if that’s what it does?

    • Practically speaking, Big O analysis is so useful and important because Big O puts the focus squarely on the algorithm’s own complexity and completely ignores anything that is merely a proportionality constant—like a JavaScript engine, the speed of a CPU, your Internet connection, and all those things which become quickly become as laughably outdated as a Model T . Big O focuses on performance only in the way that matters equally as much to people living in the present or in the future.

    • Big O notation also shines a spotlight directly on the most important principle of computer programming/engineering, the fact which inspires all good programmers to keep thinking and dreaming: the only way to achieve results beyond the slow forward march of technology is to invent a better algorithm .

    Algorithm example (Java):

     // given a list of integers L, and an integer K public boolean simple_search(List 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; } 

    Algorithm description:

    • This algorithm search a list, item by item, looking for a key,

    • Iterating on each item in the list, if it’s the key then return True,

    • If the loop has finished without finding the key, return False.

    Big-O notation represent the upper-bound on the Complexity (Time, Space, ..)

    To find The Big-O on Time Complexity:

    • Calculate how much time (regarding input size) the worst case takes:

    • Worst-Case: the key doesn’t exist in the list.

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

    • Time: O(4n+1) = O(n) | in Big-O, constants are neglected

    • O(n) ~ Linear

    There’s also Big-Omega, which represent complexity of the Best-Case:

    • Best-Case: the key is the first item.

    • Time(Best-Case) = 4

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

    Big O

    f (x) = O( g (x)) when x goes to a (for example, a = +∞) means that there is a function k such that:

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

    2. k is bounded in some neighborhood of a (if a = +∞, this means that there are numbers N and M such that for every x > N, | k (x)| < M).

    In other words, in plain English: f (x) = O( g (x)), x → a, means that in a neighborhood of a, f decomposes into the product of g and some bounded function.

    Small o

    By the way, here is for comparison the definition of small o.

    f (x) = o( g (x)) when x goes to a means that there is a function k such that:

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

    2. k (x) goes to 0 when x goes to a.

    Examples

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

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

    • x 2 + x = O(x) when x → 0,

    • x 2 + x = O(x 2 ) when x → +∞,

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

    Attention! The notation with the equal sign “=” uses a “fake equality”: it is true that o(g(x)) = O(g(x)), but false that O(g(x)) = o(g(x)). Similarly, it is ok to write “ln(x) = o(x) when x → +∞”, but the formula “o(x) = ln(x)” would make no sense.

    More examples

    • O(1) = O(n) = O(n 2 ) when n → +∞ (but not the other way around, the equality is “fake”),

    • O(n) + O(n 2 ) = O(n 2 ) when n → +∞

    • O(O(n 2 )) = O(n 2 ) when n → +∞

    • O(n 2 )O(n 3 ) = O(n 5 ) when n → +∞


    Here is the Wikipedia article: https://en.wikipedia.org/wiki/Big_O_notation

    Big O notation is a way of describing how quickly an algorithm will run given an arbitrary number of input parameters, which we’ll call “n”. It is useful in computer science because different machines operate at different speeds, and simply saying that an algorithm takes 5 seconds doesn’t tell you much because while you may be running a system with a 4.5 Ghz octo-core processor, I may be running a 15 year old, 800 Mhz system, which could take longer regardless of the algorithm. So instead of specifying how fast an algorithm runs in terms of time, we say how fast it runs in terms of number of input parameters, or “n”. By describing algorithms in this way, we are able to compare the speeds of algorithms without having to take into account the speed of the computer itself.

    Not sure I’m further contributing to the subject but still thought I’d share: I once found this blog post to have some quite helpful (though very basic) explanations & examples on Big O:

    Via examples, this helped get the bare basics into my tortoiseshell-like skull, so I think it’s a pretty descent 10-minute read to get you headed in the right direction.

    You want to know all there is to know of big O? So do I.

    So to talk of big O, I will use words that have just one beat in them. One sound per word. Small words are quick. You know these words, and so do I. We will use words with one sound. They are small. I am sure you will know all of the words we will use!

    Now, let’s you and me talk of work. Most of the time, I do not like work. Do you like work? It may be the case that you do, but I am sure I do not.

    I do not like to go to work. I do not like to spend time at work. If I had my way, I would like just to play, and do fun things. Do you feel the same as I do?

    Now at times, I do have to go to work. It is sad, but true. So, when I am at work, I have a rule: I try to do less work. As near to no work as I can. Then I go play!

    So here is the big news: the big O can help me not to do work! I can play more of the time, if I know big O. Less work, more play! That is what big O helps me do.

    Now I have some work. I have this list: one, two, three, four, five, six. I must add all things in this list.

    Wow, I hate work. But oh well, I have to do this. So here I go.

    One plus two is three… plus three is six… and four is… I don’t know. I got lost. It is too hard for me to do in my head. I don’t much care for this kind of work.

    So let’s not do the work. Let’s you and me just think how hard it is. How much work would I have to do, to add six numbers?

    Well, let’s see. I must add one and two, and then add that to three, and then add that to four… All in all, I count six adds. I have to do six adds to solve this.

    Here comes big O, to tell us just how hard this math is.

    Big O says: we must do six adds to solve this. One add, for each thing from one to six. Six small bits of work… each bit of work is one add.

    Well, I will not do the work to add them now. But I know how hard it would be. It would be six adds.

    Oh no, now I have more work. Sheesh. Who makes this kind of stuff?!

    Now they ask me to add from one to ten! Why would I do that? I did not want to add one to six. To add from one to ten… well… that would be even more hard!

    How much more hard would it be? How much more work would I have to do? Do I need more or less steps?

    Well, I guess I would have to do ten adds… one for each thing from one to ten. Ten is more than six. I would have to work that much more to add from one to ten, than one to six!

    I do not want to add right now. I just want to think on how hard it might be to add that much. And, I hope, to play as soon as I can.

    To add from one to six, that is some work. But do you see, to add from one to ten, that is more work?

    Big O is your friend and mine. Big O helps us think on how much work we have to do, so we can plan. And, if we are friends with big O, he can help us choose work that is not so hard!

    Now we must do new work. Oh, no. I don’t like this work thing at all.

    The new work is: add all things from one to n.

    Warten! What is n? Did I miss that? How can I add from one to n if you don’t tell me what n is?

    Well, I don’t know what n is. I was not told. Were you? No? Naja. So we can’t do the work. Whew.

    But though we will not do the work now, we can guess how hard it would be, if we knew n. We would have to add up n things, right? Of course!

    Now here comes big O, and he will tell us how hard this work is. He says: to add all things from one to N, one by one, is O(n). To add all these things, [I know I must add n times.][1] That is big O! He tells us how hard it is to do some type of work.

    To me, I think of big O like a big, slow, boss man. He thinks on work, but he does not do it. He might say, “That work is quick.” Or, he might say, “That work is so slow and hard!” But he does not do the work. He just looks at the work, and then he tells us how much time it might take.

    I care lots for big O. Why? I do not like to work! No one likes to work. That is why we all love big O! He tells us how fast we can work. He helps us think of how hard work is.

    Uh oh, more work. Now, let’s not do the work. But, let’s make a plan to do it, step by step.

    They gave us a deck of ten cards. They are all mixed up: seven, four, two, six… not straight at all. And now… our job is to sort them.

    Ergh. That sounds like a lot of work!

    How can we sort this deck? I have a plan.

    I will look at each pair of cards, pair by pair, through the deck, from first to last. If the first card in one pair is big and the next card in that pair is small, I swap them. Else, I go to the next pair, and so on and so on… and soon, the deck is done.

    When the deck is done, I ask: did I swap cards in that pass? If so, I must do it all once more, from the top.

    At some point, at some time, there will be no swaps, and our sort of the deck would be done. So much work!

    Well, how much work would that be, to sort the cards with those rules?

    I have ten cards. And, most of the time — that is, if I don’t have lots of luck — I must go through the whole deck up to ten times, with up to ten card swaps each time through the deck.

    Big O, help me!

    Big O comes in and says: for a deck of n cards, to sort it this way will be done in O(N squared) time.

    Why does he say n squared?

    Well, you know n squared is n times n. Now, I get it: n cards checked, up to what might be n times through the deck. That is two loops, each with n steps. That is n squared much work to be done. A lot of work, for sure!

    Now when big O says it will take O(n squared) work, he does not mean n squared adds, on the nose. It might be some small bit less, for some case. But in the worst case, it will be near n squared steps of work to sort the deck.

    Now here is where big O is our friend.

    Big O points out this: as n gets big, when we sort cards, the job gets MUCH MUCH MORE HARD than the old just-add-these-things job. How do we know this?

    Well, if n gets real big, we do not care what we might add to n or n squared.

    For big n, n squared is more large than n.

    Big O tells us that to sort things is more hard than to add things. O(n squared) is more than O(n) for big n. That means: if n gets real big, to sort a mixed deck of n things MUST take more time, than to just add n mixed things.

    Big O does not solve the work for us. Big O tells us how hard the work is.

    I have a deck of cards. I did sort them. You helped. Vielen Dank.

    Is there a more fast way to sort the cards? Can big O help us?

    Yes, there is a more fast way! It takes some time to learn, but it works… and it works quite fast. You can try it too, but take your time with each step and do not lose your place.

    In this new way to sort a deck, we do not check pairs of cards the way we did a while ago. Here are your new rules to sort this deck:

    One: I choose one card in the part of the deck we work on now. You can choose one for me if you like. (The first time we do this, “the part of the deck we work on now” is the whole deck, of course.)

    Two: I splay the deck on that card you chose. What is this splay; how do I splay? Well, I go from the start card down, one by one, and I look for a card that is more high than the splay card.

    Three: I go from the end card up, and I look for a card that is more low than the splay card.

    Once I have found these two cards, I swap them, and go on to look for more cards to swap. That is, I go back to step Two, and splay on the card you chose some more.

    At some point, this loop (from Two to Three) will end. It ends when both halves of this search meet at the splay card. Then, we have just splayed the deck with the card you chose in step One. Now, all the cards near the start are more low than the splay card; and the cards near the end are more high than the splay card. Cool trick!

    Four (and this is the fun part): I have two small decks now, one more low than the splay card, and one more high. Now I go to step one, on each small deck! That is to say, I start from step One on the first small deck, and when that work is done, I start from step One on the next small deck.

    I break up the deck in parts, and sort each part, more small and more small, and at some time I have no more work to do. Now this may seem slow, with all the rules. But trust me, it is not slow at all. It is much less work than the first way to sort things!

    What is this sort called? It is called Quick Sort! That sort was made by a man called CAR Hoare and he called it Quick Sort. Now, Quick Sort gets used all the time!

    Quick Sort breaks up big decks in small ones. That is to say, it breaks up big tasks in small ones.

    Hmmm. There may be a rule in there, I think. To make big tasks small, break them up.

    This sort is quite quick. How quick? Big O tells us: this sort needs O(n log n) work to be done, in the mean case.

    Is it more or less fast than the first sort? Big O, please help!

    The first sort was O(n squared). But Quick Sort is O(n log n). You know that n log n is less than n squared, for big n, right? Well, that is how we know that Quick Sort is fast!

    If you have to sort a deck, what is the best way? Well, you can do what you want, but I would choose Quick Sort.

    Why do I choose Quick Sort? I do not like to work, of course! I want work done as soon as I can get it done.

    How do I know Quick Sort is less work? I know that O(n log n) is less than O(n squared). The O’s are more small, so Quick Sort is less work!

    Now you know my friend, Big O. He helps us do less work. And if you know big O, you can do less work too!

    You learned all that with me! You are so smart! Thank you so much!

    Now that work is done, let’s go play!


    [1]: There is a way to cheat and add all the things from one to n, all at one time. Some kid named Gauss found this out when he was eight. I am not that smart though, so don’t ask me how he did it .

    Assume we’re talking about an algorithm A , which should do something with a dataset of size n .

    Then O( ) means, in simple English:

    If you’re unlucky when executing A, it might take X(n) operations to complete.

    As it happens, there are certain functions (think of them as implementations of X(n) ) that tend to occur quite often. These are well known and easily compared (Examples: 1 , Log N , N , N^2 , N! , etc..)

    By comparing these when talking about A and other algorithms, it is easy to rank the algorithms according to the number of operations they may (worst-case) require to complete.

    In general, our goal will be to find or structure an algorithm A in such a way that it will have a function X(n) that returns as low a number as possible.

    I’ve more simpler way to understand the time complexity he most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:

     statement; 

    Is constant. The running time of the statement will not change in relation to N

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

    Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

     for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; } 

    Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by 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; } 

    Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.

     void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); } 

    Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.

    In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( ) where is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).

    Note: None of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course.

    • See more at: Here

    Say you order Harry Potter: Complete 8-Film Collection [Blu-ray] from Amazon and download the same film collection online at the same time. You want to test which method is faster. The delivery takes almost a day to arrive and the download completed about 30 minutes earlier. Groß! So it’s a tight race.

    What if I order several Blu-ray movies like The Lord of the Rings, Twilight, The Dark Knight Trilogy, etc. and download all the movies online at the same time? This time, the delivery still take a day to complete, but the online download takes 3 days to finish. For online shopping, the number of purchased item (input) doesn’t affect the delivery time. The output is constant. We call this O(1) .

    For online downloading, the download time is directly proportional to the movie file sizes (input). We call this O(n) .

    From the experiments, we know that online shopping scales better than online downloading. It is very important to understand big O notation because it helps you to analyze the scalability and efficiency of algorithms.

    Note: Big O notation represents the worst-case scenario of an algorithm. Let’s assume that O(1) and O(n) are the worst-case scenarios of the example above.

    Reference : http://carlcheo.com/compsci

    If you have a suitable notion of infinity in your head, then there is a very brief description:

    Big O notation tells you the cost of solving an infinitely large problem.

    And furthermore

    Constant factors are negligible

    If you upgrade to a computer that can run your algorithm twice as fast, big O notation won’t notice that. Constant factor improvements are too small to even be noticed in the scale that big O notation works with. Note that this is an intentional part of the design of big O notation.

    Although anything “larger” than a constant factor can be detected, however.

    When interested in doing computations whose size is “large” enough to be considered as approximately infinity, then big O notation is approximately the cost of solving your problem.


    If the above doesn’t make sense, then you don’t have a compatible intuitive notion of infinity in your head, and you should probably disregard all of the above; the only way I know to make these ideas rigorous, or to explain them if they aren’t already intuitively useful, is to first teach you big O notation or something similar. (although, once you well understand big O notation in the future, it may be worthwhile to revisit these ideas)

    Simplest way to look at it (in plain English)

    We are trying to see how the number of input parameters, affects the running time of an algorithm. If the running time of your application is proportional to the number of input parameters, then it is said to be in Big O of n.

    The above statement is a good start but not completely true.

    A more accurate explanation (mathematical)

    Suppose

    n=number of input parameters

    T(n)= The actual function that expresses the running time of the algorithm as a function of n

    c= a constant

    f(n)= An approximate function that expresses the running time of the algorithm as a function of n

    Then as far as Big O is concerned, the approximation f(n) is considered good enough as long as the below condition is true.

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

    The equation is read as As n approaches infinity, T of n, is less than or equal to c times f of n.

    In big O notation this is written as

     T(n)∈O(n) 

    This is read as T of n is in big O of n.

    Back to English

    Based on the mathematical definition above, if you say your algorithm is a Big O of n, it means it is a function of n (number of input parameters) or faster . If your algorithm is Big O of n, then it is also automatically the Big O of n square.

    Big O of n means my algorithm runs at least as fast as this. You cannot look at Big O notation of your algorithm and say its slow. You can only say its fast.

    Check this out for a video tutorial on Big O from UC Berkley. It’s is actually a simple concept. If you hear professor Shewchuck (aka God level teacher) explaining it, you will say “Oh that’s all it is!”.

    What is a plain English explanation of “Big O” notation?

    Very Quick Note:

    The O in “Big O” refers to as “Order”(or precisely “order of”)
    so you could get its idea literally that it’s used to order something to compare them.

    • “Big O” does two things:

      1. Estimates how many steps of the method your computer applies to accomplish a task.
      2. Facilitate the process to compare with others in order to determine whether it’s good or not?
      3. “Big O’ achieves the above two with standardized Notations .
    • There are seven most used notations

      1. O(1), means your computer gets a task done with 1 step, it’s excellent, Ordered No.1
      2. O(logN), means your computer complete a task with logN steps, its good, Ordered No.2
      3. O(N), finish a task with N steps, its fair, Order No.3
      4. O(NlogN), ends a task with O(NlogN) steps, it’s not good, Order No.4
      5. O(N^2), get a task done with N^2 steps, it’s bad, Order No.5
      6. O(2^N), get a task done with 2^N steps, it’s horrible, Order No.6
      7. O(N!), get a task done with N! steps, it’s terrible, Order No.7

    Bildbeschreibung hier eingeben

    Suppose you get notation O(N^2) , not only you are clear the method takes N*N steps to accomplish a task, also you see that it’s not good as O(NlogN) from its ranking.

    Please note the order at line end, just for your better understanding.There’s more than 7 notations if all possibilities considered.

    In CS, the set of steps to accomplish a task is called algorithms.
    In Terminology, Big O notation is used to describe the performance or complexity of an algorithm.

    In addition, Big O establishes the worst-case or measure the Upper-Bound steps.
    You could refer to Big-Ω (Big-Omega) for best case.

    Big-Ω (Big-Omega) notation (article) | Khan Academy

    • Zusammenfassung
      “Big O” describes the algorithm’s performance and evaluates it.

      or address it formally, “Big O” classifies the algorithms and standardize the comparison process.

    This is a very simplified explanation, but I hope it covers most important details.

    Let’s say your algorithm dealing with the problem depends on some ‘factors’, for example let’s make it N and X.

    Depending on N and X, your algorithm will require some operations, for example in the WORST case it’s 3(N^2) + log(X) operations.

    Since Big-O doesn’t care too much about constant factor (aka 3), the Big-O of your algorithm is O(N^2 + log(X)) . It basically translates ‘the amount of operations your algorithm needs for the worst case scales with this’.

    Definition :- Big O notation is a notation which says how a algorithm performance will perform if the data input increases.

    When we talk about algorithms there are 3 important pillars Input , Output and Processing of algorithm. Big O is symbolic notation which says if the data input is increased in what rate will the performance vary of the algorithm processing.

    I would encourage you to see this youtube video which explains Big O Notation in depth with code examples.

    Algorithm basic pillars

    So for example assume that a algorithm takes 5 records and the time required for processing the same is 27 seconds. Now if we increase the records to 10 the algorithm takes 105 seconds.

    In simple words the time taken is square of the number of records. We can denote this by O(n ^ 2) . This symbolic representation is termed as Big O notation.

    Now please note the units can be anything in inputs it can be bytes , bits number of records , the performance can be measured in any unit like second , minutes , days and so on. So its not the exact unit but rather the relationship.

    Big O symbols

    For example look at the below function “Function1” which takes a collection and does processing on the first record. Now for this function the performance will be same irrespective you put 1000 , 10000 or 100000 records. So we can denote it by O(1) .

     void Function1(List data) { string str = data[0]; } 

    Now see the below function “Function2()”. In this case the processing time will increase with number of records. We can denote this algorithm performance using O(n) .

     void Function2(List data) { foreach(string str in data) { if (str == "shiv") { return; } } } 

    When we see a Big O notation for any algorithm we can classify them in to three categories of performance :-

    1. Log and constant category :- Any developer would love to see their algorithm performance in this category.
    2. Linear :- Developer will not want to see algorithms in this category , until its the last option or the only option left.
    3. Exponential :- This is where we do not want to see our algorithms and a rework is needed.

    So by looking at Big O notation we categorize good and bad zones for algorithms.

    Bog O classification

    I would recommend you to watch this 10 minutes video which discusses Big O with sample code

    https://www.youtube.com/watch?v=k6kxtzICG_g

    If I want to explain this to 6 years old child I will start to draw some functions f(x) = x and f(x) = x^2 for example and ask a child which function will be upper function on the top of the page. Then we will proceed with drawing and see that x^2 wins. “Who wins” actually is the function which grows faster when x tends to infinity. So “function x is in Big O of x^2” means that x grows slower than x^2 when x tends to infinity. The same can be done when x tends to 0. If we draw these two function for x from 0 to 1 x will be upper function, so “function x^2 is in Big O of x for x tends to 0”. When child will get older I add that really Big O can be a function which grows not faster but the same way as given function. Moreover constant is discarded. So 2x is in Big O of x.