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

Big O beschreibt eine Klasse von Funktionen.

Sie beschreibt, wie schnell Funktionen bei großen Eingabewerten wachsen.

Für eine gegebene Funktion f beschreibt O(f) alle Funktionen g(n), für die man ein n0 und eine Konstante c finden kann, so dass alle Werte von g(n) mit n >= n0 kleiner oder gleich c*f(n) sind

In weniger mathematischen Worten ist O(f) eine Menge von Funktionen. Nämlich alle Funktionen, die ab einem bestimmten Wert n0 langsamer oder genauso schnell wachsen wie f.

Wenn f(n) = n ist, dann

g(n) = 3n ist in O(f). Da konstante Faktoren keine Rolle spielen h(n) = n+1000 ist in O(f), weil es für alle Werte kleiner als 1000 größer sein kann, aber für großes O nur große Eingaben wichtig sind.

Allerdings ist i(n) = n^2 nicht in O(f), weil eine quadratische Funktion schneller wächst als eine lineare.

Answer 2

Sie stellt die Geschwindigkeit eines Algorithmus in auf lange Sicht .

Um eine wörtliche Analogie zu verwenden: Es interessiert Sie nicht, wie schnell ein Läufer einen 100-Meter-Sprint oder sogar einen 5-Kilometer-Lauf absolvieren kann. Sie interessieren sich eher für Marathonläufer und vorzugsweise für Ultramarathonläufer (bei denen die Analogie zum Laufen nicht mehr greift und man auf die metaphorische Bedeutung von "der lange Lauf" zurückgreifen muss).

Sie können hier aufhören zu lesen.

Ich füge diese Antwort hinzu, weil ich überrascht bin, wie mathematisch und technisch der Rest der Antworten ist. Der Begriff des "langen Laufs" im ersten Satz bezieht sich auf die beliebig zeitaufwändigen Rechenaufgaben. Im Gegensatz zum Laufen, das durch die menschliche Kapazität begrenzt ist, können Rechenaufgaben für bestimmte Algorithmen sogar mehr als Millionen von Jahren in Anspruch nehmen.

Was ist mit all diesen mathematischen Logarithmen y Polynome ? Es stellt sich heraus, dass die Algorithmen an sich die mit diesen mathematischen Begriffen zusammenhängen. Wenn Sie die Körpergröße aller Kinder im Viertel messen, brauchen Sie so viel Zeit, wie es Kinder gibt. Dies ist eng verbunden mit dem Begriff der n^1 oder einfach n wobei n ist nichts anderes als die Anzahl der Kinder im Wohnblock. Im Fall des Ultramarathons misst man die Höhe aller Kinder in der Stadt, muss dann aber die Reisezeiten ignorieren und davon ausgehen, dass sie alle in einer Reihe stehen (sonst würde man der aktuellen Erklärung vorgreifen).

Angenommen, du versuchst, die von dir erstellte Liste mit den Größen der Kinder in der Reihenfolge von der kleinsten bis zur größten Körpergröße zu ordnen. Wenn es sich nur um die Kinder in Ihrer Nachbarschaft handelt, könnten Sie die Liste einfach mit dem Auge ablesen und eine geordnete Liste erstellen. Das ist die "Sprint"-Analogie, und wir interessieren uns in der Informatik wirklich nicht für Sprints, denn warum sollte man einen Computer benutzen, wenn man etwas mit den Augen sehen kann?

Wenn Sie aber die Liste der Körpergrößen aller Kinder in Ihrer Stadt oder besser noch in Ihrem Land zusammenstellen, werden Sie feststellen, dass die Art und Weise, wie Sie dies tun, untrennbar mit der mathematischen Protokoll y n^2 . Wenn du deine Liste durchgehst, um das kleinste Kind zu finden, seinen Namen in ein separates Notizbuch schreibst und es aus dem ursprünglichen Notizbuch streichst, ist das an sich gebunden an die mathematische n^2 . Wenn Sie sich vorstellen, die Hälfte Ihres Notizbuchs zu ordnen, dann die andere Hälfte, und dann die Ergebnisse zu kombinieren, werden Sie zu einer Methode kommen, die an sich gebunden an den Logarithmus .

Nehmen wir schließlich an, Sie müssten erst in den Laden gehen, um ein Maßband zu kaufen. Dies ist ein Beispiel für einen Aufwand, der bei kurzen Sprints von Bedeutung ist, z. B. wenn Sie die Kinder im Viertel messen, aber wenn Sie alle Kinder der Stadt messen, können Sie diese Kosten getrost ignorieren. Dies ist die eigentliche Verbindung zum mathematischen Fallenlassen von, sagen wir, Polynomtermen niedriger Ordnung.

Ich hoffe, dass ich erklärt habe, dass es bei der Big-O-Notation lediglich um die Langfristigkeit geht, dass die Mathematik von Natur aus mit Berechnungsmethoden zusammenhängt und dass das Weglassen von mathematischen Begriffen und andere Vereinfachungen mit der Langfristigkeit auf eine ziemlich vernünftige Weise zusammenhängen.

Sobald Sie dies erkannt haben, werden Sie feststellen, dass das Big-O wirklich supereinfach ist, weil all die schwierige Mathematik aus der Highschool einfach wegfällt. Der einzige schwierige Teil ist die Analyse eines Algorithmus, um die mathematischen Begriffe zu identifizieren, aber mit etwas Übung können Sie anfangen, Begriffe während der Analyse selbst wegzulassen und sicher Teile des Algorithmus ignorieren, um sich nur auf den Teil zu konzentrieren, der für das Big-O relevant ist. D. h. Sie sollten in der Lage sein, die meisten Situationen zu überblicken.

Das war meine Lieblingsbeschäftigung in der Informatik - herauszufinden, dass etwas viel einfacher war, als ich dachte, und dann in der Lage zu sein, bei Google-Interviews anzugeben, wenn die Uneingeweihten eingeschüchtert wären, lol.

Answer 3

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

Ich möchte betonen, dass das Hauptmotiv für "Big O"-Notation ist eine Sache, wenn eine Eingabegröße des Algorithmus zu groß einige Teile (d.h. Konstanten, Koeffizienten, Terme) der Gleichung, die das Maß des Algorithmus beschreibt, wird so unbedeutend dass wir ignorieren. sie. Die Teile der Gleichung, die nach dem Ignorieren einiger ihrer Teile übrig bleiben, werden als die "Big O"-Notation des Algorithmus.

Wenn also die Eingabegröße NICHT zu groß ist, kann die Idee der "Big O"-Notation ( Obergrenze ) unwichtig sein wird.

Angenommen, Sie möchten die Leistung des folgenden Algorithmus quantifizieren

int sumArray (int[] nums){
    int sum=0;   // taking initialization and assignments n=1
    for(int i=0;nums.length;i++){
        sum += nums[i]; // taking initialization and assignments n=1
    }
    return sum;
}

Mit dem obigen Algorithmus können Sie Folgendes herausfinden T(n) wie folgt (Zeitkomplexität):

T(n) = 2*n + 2

Um die "Big O"-Notation zu finden, müssen wir eine sehr große Eingabegröße berücksichtigen:

n= 1,000,000   -> T(1,000,000) = 2,000,002
n=1,000,000,000  -> T(1,000,000,000) = 2,000,000,002
n=10,000,000,000  -> T(10,000,000,000) = 20,000,000,002

Geben wir die gleichen Eingaben für eine andere Funktion ein F(n) = n

n= 1,000,000   -> F(1,000,000) = 1,000,000 
n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000
n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

Wie Sie sehen können, wird die Eingabegröße zu groß die T(n) ungefähr gleich oder näher an F(n) so dass die Konstante 2 und der Koeffizient 2 zu unbedeutend werden, kommt jetzt die Idee der Big O"-Notation ins Spiel,

O(T(n)) = F(n)
O(T(n)) = n

Wir sagen das große O von T(n) es n und die Notation lautet O(T(n)) = n ist sie die obere Grenze von T(n) als n erhält zu groß . der gleiche Schritt gilt für andere Algorithmen.

Answer 4

Big O bedeutet in einfachem Englisch <= (weniger als oder gleich). Wenn wir für zwei Funktionen f und g sagen, f = O(g), bedeutet das, dass f <= g ist.

Dies bedeutet jedoch nicht, dass für jedes n f(n) <= g(n) ist. Eigentlich bedeutet es, dass f ist kleiner oder gleich g in Bezug auf das Wachstum . Das bedeutet, dass nach einem Punkt f(n) <= c*g(n) wenn c ist eine Konstante . Und nach einem Punkt bedeutet als für alle n >= n0, wobei n0 ist eine weitere Konstante .

Answer 5

Big O - Wirtschaftliche Sichtweise.

Mein liebstes englisches Wort zur Beschreibung dieses Konzepts ist das Preis Sie zahlen für eine Aufgabe, wenn sie größer wird.

Stellen Sie sich vor, dass es sich dabei um wiederkehrende Kosten handelt und nicht um Fixkosten, die Sie am Anfang bezahlen. Die Fixkosten werden im Gesamtbild vernachlässigbar, weil die Kosten nur wachsen und sich summieren. Wir wollen messen, wie schnell sie wachsen und wie schnell sie sich in Bezug auf das Rohmaterial, das wir für die Einrichtung zur Verfügung stellen, aufsummieren würden - die Größe des Problems.

Wenn jedoch die anfänglichen Einrichtungskosten hoch sind und Sie nur eine kleine Menge des Produkts herstellen, sollten Sie sich diese anfänglichen Kosten ansehen - sie werden auch als Konstanten bezeichnet.

Da diese Konstanten auf lange Sicht keine Rolle spielen, ermöglicht es uns diese Sprache, Aufgaben über die Art der Infrastruktur hinaus zu diskutieren, auf der sie ausgeführt werden. Die Fabriken können also überall stehen, und die Arbeiterinnen und Arbeiter können sein, wer immer sie sind - das ist alles nur Soße. Aber die Größe der Fabrik und die Anzahl der Arbeiter wären die Dinge, die wir auf lange Sicht variieren könnten, wenn die Inputs und Outputs wachsen.

Dies wird somit zu einer Angleichung des Gesamtbildes wie viel man ausgeben müsste, um etwas zu betreiben. Seit Zeit y Raum die ökonomischen Größen sind (d.h. sie sind begrenzt), können sie beide in dieser Sprache ausgedrückt werden.

Technische Hinweise: Einige Beispiele für Zeitkomplexität - O(n) bedeutet im Allgemeinen, dass ich bei einem Problem der Größe "n" zumindest alles sehen muss. O(log n) bedeutet im Allgemeinen, dass ich die Größe des Problems halbiere und prüfe und wiederhole, bis die Aufgabe erledigt ist. O(n^2) bedeutet, dass ich mir Paare von Dingen ansehen muss (z. B. Händeschütteln auf einer Party zwischen n Personen).