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

Wenn ich das einem 6-jährigen Kind erklären will, zeichne ich zum Beispiel die Funktionen f(x) = x und f(x) = x^2 und frage das Kind, welche Funktion oben auf der Seite steht. Dann werden wir mit dem Zeichnen fortfahren und sehen, dass x^2 gewinnt. "Wer gewinnt" ist eigentlich die Funktion, die schneller wächst, wenn x gegen unendlich tendiert. Funktion x ist in Big O von x^2" bedeutet also, dass x langsamer wächst als x^2, wenn x gegen unendlich tendiert. Dasselbe gilt, wenn x gegen 0 tendiert. Wenn wir diese beiden Funktionen für x von 0 bis 1 zeichnen, ist x eine obere Funktion, also "Funktion x^2 ist in Big O von x für x tendiert gegen 0". Wenn das Kind älter wird, füge ich hinzu, dass Big O wirklich eine Funktion sein kann, die nicht schneller wächst, sondern auf die gleiche Weise wie die gegebene Funktion. Außerdem wird die Konstante verworfen. Also ist 2x in Big O von x.

Answer 2

Es wurden bereits einige gute Antworten gepostet, aber ich möchte auf eine andere Art und Weise beitragen. Wenn Sie sich ein Bild davon machen wollen, was alles passiert, können Sie davon ausgehen, dass ein Compiler annähernd 10^8 Operationen in ~1 Sekunde durchführen kann. Wenn die Eingabe in 10^8 gegeben ist, sollte man einen Algorithmus entwerfen, der linear arbeitet (wie eine nicht verschachtelte for-Schleife). Im Folgenden finden Sie eine Tabelle, die Ihnen helfen kann, schnell herauszufinden, welche Art von Algorithmus Sie entwerfen möchten ;)

Answer 3

Wenn wir eine Funktion wie f(n) = n+3 und wir wollen wissen, wie der Graph aussieht, wenn n gegen unendlich geht, lassen wir einfach alle Konstanten und Terme niedrigerer Ordnung weg, weil sie keine Rolle spielen, wenn n wird groß. Das heißt, wir haben f(n) = n Warum können wir also nicht einfach diese Funktion verwenden, warum müssen wir nach einer Funktion suchen, die über und unter unserer f(n) = n+3 Funktion, also großes O und großes Omega.

Denn es wäre falsch zu sagen, dass die Funktion nur eine f(n) = n wenn n nähert sich der Unendlichkeit. Um korrekt zu sein, beschreiben wir also den Bereich, in dem die f(n) = n+3 sein könnte. Wir sind nicht daran interessiert, wo der Graph genau liegt, da Terme niedrigerer Ordnung und Konstanten das Wachstum des Graphen nicht wesentlich verändern. Mit anderen Worten: Der Bereich, der von der oberen und unteren Grenze eingeschlossen ist, ist eine vage Version unserer Funktion f(n) = n+3.

Das bloße Weglassen der Konstante und des Terms niedrigerer Ordnung ist genau der Vorgang, bei dem die Funktion gefunden wird, die unten und oben liegt.

Per Definition ist eine Funktion eine Unter- oder Obergrenze einer anderen Funktion, wenn man eine Konstante findet, mit der man die Funktion multiplizieren kann. f(n) = n Funktion, so dass für jede n die Ausgabe ist größer (oder kleiner für die untere Schranke) als bei der ursprünglichen Funktion:

f(n) = n*C > f(n) = n+3

Und ja C = 2 würde es tun, daher unsere Funktion f(n) = n kann eine Obergrenze für unsere f(x) = x+3 Funktion.

Dasselbe gilt für die untere Grenze:

f(n) = n*C < f(n) = n+3

C = -2 würde es tun

Also f(x) = n ist die obere und untere Grenze von f(x) = x+3 Wenn es sowohl ein großes O als auch ein Omega ist, dann ist es ein Theta, was bedeutet, dass es fest gebunden ist.

Big O könnte also auch sein f(x) = x^2 weil sie die Bedingung erfüllt f(n) = n^2*C > f(n) = n+3 . Sein über unser f(n) = n+3 Graphen, aber der Bereich zwischen dieser oberen Grenze und der unteren Grenze ist nicht so präzise wie unsere früheren Grenzen.

Answer 4

TLDR: Big O erklärt die Leistung eines Algorithmus in mathematischen Begriffen.

Langsamere Algorithmen laufen in der Regel mit n hoch x oder vielen, je nach Tiefe des Algorithmus, während schnellere Algorithmen wie die binäre Suche mit O(log n) laufen, so dass sie mit zunehmender Datenmenge schneller laufen. Big O könnte mit anderen Begriffen erklärt werden, die n verwenden, oder auch ohne n (z. B. O(1) ).

Man kann Big O berechnen, wenn man sich die komplexesten Zeilen des Algorithmus ansieht.

Bei kleinen oder unsortierten Datensätzen kann Big O überraschend sein, da Algorithmen mit n log n-Komplexität wie die binäre Suche bei kleineren oder unsortierten Datensätzen langsam sein können. Ein einfaches Beispiel für die lineare Suche im Vergleich zur binären Suche finden Sie in meinem JavaScript-Beispiel:

https://codepen.io/serdarsenay/pen/XELWqN?editors=1011 (Algorithmen unten geschrieben)

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}

Answer 5

Von ( Quelle ) kann man lesen:

Die Big-O-Notation ist eine mathematische Notation die den Grenzwert beschreibt Verhalten einer Funktion, wenn das Argument dazu tendiert gegenüber einer bestimmten Wert oder Unendlichkeit . (..) In der Informatik, Die Big-O-Notation wird verwendet, um Algorithmen zu klassifizieren je nachdem, wie ihre Laufzeit oder ihr Speicherplatzbedarf wächst wenn die Eingabegröße wächst .

Big O Notation stellt keine Funktion per si sondern vielmehr eine Reihe von Funktionen mit einer bestimmten asymptotischen Obergrenze; wie man aus Quelle :

Die Big-O-Notation charakterisiert Funktionen nach ihrem Wachstum Wachstumsraten: verschiedene Funktionen mit der gleichen Wachstumsrate können mit der gleichen O Notation.

Informell, in der Computerwissenschaft Zeitkomplexität y Raumkomplexität Theorien, kann man sich die Big O Notation als eine Kategorisierung von Algorithmen mit einem bestimmten Worst-Case-Szenario in Bezug auf Zeit und Raum. Zum Beispiel, O(n) :

Ein Algorithmus benötigt linear Zeit/Raum oder O(n) Zeit/Raum, wenn seine Zeit/Raum-Komplexität O(n) ist. Informell bedeutet dies, dass die laufende Zeit/Raum höchstens linear mit der Größe der Eingabe zunimmt ( Quelle ).

y O(n log n) als:

Ein Algorithmus läuft in quasilinearer Zeit/Raum, wenn T(n) = O(n log^k n) für eine positive Konstante k; linearithmische Zeit/Raum ist der Fall k = 1 ( Quelle ).

Dennoch wird eine solche entspannte Formulierung in der Regel verwendet, um (für den schlimmsten Fall) zu quantifizieren, wie sich eine Gruppe von Algorithmen im Vergleich zu einer anderen Gruppe von Algorithmen hinsichtlich der Zunahme ihrer Eingabegrößen verhält. Um zwei Klassen von Algorithmen zu vergleichen ( z.B.. , O(n log n) y O(n) ) sollte man analysieren, wie sich beide Klassen von Algorithmen mit der Zunahme ihrer Eingabegröße verhalten ( d.h., n) für das Worst-Case-Szenario; Analyse n wenn sie gegen das Unendliche tendiert

In der Abbildung oben big-O eine der asymptotisch kleinsten oberen Schranken der gezeichneten Funktionen bezeichnen und sich nicht auf die Mengen O(f(n)) .

Vergleichen Sie zum Beispiel O(n log n) vs. O(n) wie man auf dem Bild nach einer bestimmten Eingabe sehen kann, O(n log n) (grüne Linie) wächst schneller als O(n) (gelbe Linie). Deshalb ist (für den schlimmsten Fall) O(n) ist wünschenswerter als O(n log n) weil man die Eingabegröße erhöhen kann und die Wachstumsrate bei der ersten Variante langsamer steigt als bei der zweiten.