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

Es ist sehr schwierig, die Geschwindigkeit von Softwareprogrammen zu messen, und wenn wir es versuchen, können die Antworten sehr komplex und voller Ausnahmen und Sonderfälle sein. Das ist ein großes Problem, denn all diese Ausnahmen und Sonderfälle lenken ab und sind nicht hilfreich, wenn wir zwei verschiedene Programme miteinander vergleichen wollen, um herauszufinden, welches das "schnellste" ist.

Infolge dieser wenig hilfreichen Komplexität versucht man, die Geschwindigkeit von Softwareprogrammen mit möglichst kleinen und wenig komplexen (mathematischen) Ausdrücken zu beschreiben. Diese Ausdrücke sind sehr grobe Näherungen: Obwohl sie mit etwas Glück die "Essenz" dessen, ob eine Software schnell oder langsam ist, erfassen.

Da es sich um Näherungswerte handelt, verwenden wir den Buchstaben "O" (Big Oh) im Ausdruck, um dem Leser zu signalisieren, dass wir eine grobe Vereinfachung vornehmen. (Und um sicherzustellen, dass niemand fälschlicherweise denkt, dass der Ausdruck in irgendeiner Weise genau ist).

Wenn Sie das "Oh" im Sinne von "in der Größenordnung von" oder "ungefähr" verstehen, können Sie nicht allzu viel falsch machen. (Ich denke, die Wahl des Big-Oh könnte ein Versuch gewesen sein, Humor zu zeigen).

Das Einzige, was diese "Big-Oh"-Ausdrücke zu tun versuchen, ist zu beschreiben, wie sehr die Software langsamer wird, wenn wir die Datenmenge erhöhen, die die Software verarbeiten muss. Wenn wir die Menge der zu verarbeitenden Daten verdoppeln, braucht die Software dann doppelt so lange, um ihre Arbeit zu erledigen? Zehnmal so lange? In der Praxis gibt es nur eine sehr begrenzte Anzahl von Big-Oh-Ausdrücken, mit denen Sie konfrontiert werden und über die Sie sich Gedanken machen müssen:

Das Gute:

• O(1) Konstante : Das Programm benötigt die gleiche Zeit, egal wie groß die Eingabe ist.
• O(log n) Logarithmisch : Die Programmlaufzeit erhöht sich nur langsam, auch wenn die Größe der Eingaben stark zunimmt.

Das Schlechte:

• O(n) Linear : Die Programmlaufzeit steigt proportional zur Größe der Eingabe.
• O(n^k) Polynom : - Die Verarbeitungszeit wächst immer schneller - als Polynomfunktion - wenn die Größe der Eingabe zunimmt.

... und das Hässliche:

• O(k^n) Exponential Die Programmlaufzeit steigt schon bei mäßiger Vergrößerung des Problems sehr schnell an - es ist nur sinnvoll, kleine Datensätze mit exponentiellen Algorithmen zu verarbeiten.
• O(n!) Faktoriell Die Programmlaufzeit wird länger sein, als Sie es sich leisten können, auf irgendetwas zu warten, außer auf die kleinsten und trivial erscheinenden Datensätze.

Answer 2

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

Eine einfache englische Erläuterung der Bedarf für die Big-O-Notation:

Wenn wir programmieren, versuchen wir, ein Problem zu lösen. Was wir codieren, wird Algorithmus genannt. Die Big-O-Notation ermöglicht es uns, die Leistung unserer Algorithmen im schlimmsten Fall auf standardisierte Weise zu vergleichen. Hardware-Spezifikationen ändern sich mit der Zeit, und Verbesserungen der Hardware können die Ausführungszeit eines Algorithmus verkürzen. Ein Austausch der Hardware bedeutet jedoch nicht, dass unser Algorithmus besser ist oder sich im Laufe der Zeit verbessert, da unser Algorithmus immer noch derselbe ist. Um verschiedene Algorithmen zu vergleichen und festzustellen, ob einer besser ist oder nicht, verwenden wir die Big-O-Notation.

Eine einfache englische Erläuterung von Was Big O Notation ist:

Nicht alle Algorithmen laufen in der gleichen Zeit und können je nach Anzahl der Elemente in der Eingabe variieren, die wir als n . Auf dieser Grundlage betrachten wir die Worst-Case-Analyse bzw. eine Obergrenze der Laufzeit als n werden größer und größer. Wir müssen uns bewusst sein, was n ist, weil viele der Big-O-Notationen darauf verweisen.

Answer 3

Ok, meine 2cents.

Big-O, ist Steigerungsrate der vom Programm verbrauchten Ressourcen, bezogen auf die Größe der Probleminstanz

Ressource : Kann die Gesamt-CPU-Zeit sein, kann aber auch der maximale RAM-Speicherplatz sein. Standardmäßig bezieht sich das auf die CPU-Zeit.

Angenommen, die Aufgabe lautet "Finde die Summe",

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

Bei einer Eingabe der Größe "n" wächst das Programm mit der Geschwindigkeit von "n" Iterationen im Array. Daher ist Big-O N ausgedrückt als O(n)

Angenommen, die Aufgabe lautet "Finde die Kombination",

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

problem-instance= {5,10,15} ==> 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

Bei einer Eingabe der Größe "n" wächst das Programm mit der Geschwindigkeit von "n*n" Iterationen im Array. Folglich ist Big-O N 2 ausgedrückt als O(n 2 )

Answer 4

Eine einfache und direkte Antwort kann lauten:

Big O steht für die schlechtestmögliche Zeit/Raum für diesen Algorithmus. Der Algorithmus wird nie mehr Raum/Zeit benötigen als diese Grenze. Big O steht für die Zeit-/Raumkomplexität im Extremfall.

Answer 5

Die Big-O-Notation ist eine Möglichkeit, die Obergrenze eines Algorithmus in Bezug auf den Platz oder die Laufzeit zu beschreiben. n ist die Anzahl der Elemente des Problems (d. h. die Größe eines Arrays, die Anzahl der Knoten in einem Baum usw.) Wir sind daran interessiert, die Laufzeit zu beschreiben, wenn n groß wird.

Wenn wir sagen, dass ein Algorithmus O(f(n)) ist, dann heißt das, dass die Laufzeit (oder der Platzbedarf) dieses Algorithmus immer kleiner ist als eine Konstante mal f(n).

Die Aussage, dass die binäre Suche eine Laufzeit von O(logn) hat, bedeutet, dass es eine Konstante c gibt, mit der man log(n) multiplizieren kann und die immer größer ist als die Laufzeit der binären Suche. In diesem Fall wird man immer einen konstanten Faktor von log(n) Vergleichen haben.

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