[algorithm] Big O, wie berechnen / approximieren Sie es?



Answers

Big O gibt die Obergrenze für die zeitliche Komplexität eines Algorithmus an. Es wird normalerweise in Verbindung mit der Verarbeitung von Datensätzen (Listen) verwendet, kann aber auch anderswo verwendet werden.

Ein paar Beispiele, wie es in C-Code verwendet wird.

Angenommen, wir haben ein Array von n Elementen

int array[n];

Wenn wir auf das erste Element des Arrays zugreifen wollten, wäre dies O (1), da es egal ist, wie groß das Array ist, es benötigt immer dieselbe konstante Zeit, um das erste Element zu erhalten.

x = array[0];

Wenn wir eine Nummer in der Liste finden wollten:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

Dies wäre O (n), da wir höchstens die gesamte Liste durchsehen müssten, um unsere Nummer zu finden. Das Big-O ist immer noch O (n), obwohl wir vielleicht unsere Nummer beim ersten Versuch finden und einmal durch die Schleife laufen, weil Big-O die obere Grenze für einen Algorithmus beschreibt (Omega ist für untere Grenze und Theta für enge Bindung) .

Wenn wir zu verschachtelten Schleifen kommen:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

Das ist O (n ^ 2), da wir für jeden Durchlauf der äußeren Schleife (O (n)) die gesamte Liste erneut durchgehen müssen, so dass die n multiplizieren und uns mit n Quadrat verlassen.

Das kratzt kaum an der Oberfläche, aber wenn man komplexere Algorithmen analysiert, kommt eine komplexe Mathematik mit Beweisen ins Spiel. Hoffentlich macht dich das zumindest mit den Grundlagen vertraut.

Question

Die meisten Leute mit einem Abschluss in CS werden sicherlich wissen, wofür Big O steht . Es hilft uns zu messen, wie (in) effizient ein Algorithmus wirklich ist und wenn Sie wissen, in welcher Kategorie das Problem, das Sie zu lösen versuchen, liegt , können Sie herausfinden, ob es noch möglich ist, diese kleine zusätzliche Leistung herauszupressen. 1

Aber ich bin neugierig, wie berechnen oder approximieren Sie die Komplexität Ihrer Algorithmen?

1 aber wie sie sagen, übertreiben Sie es nicht, ist vorzeitige Optimierung die Wurzel allen Übels , und Optimierung ohne eine berechtigte Ursache sollte diesen Namen auch verdienen.




Für den ersten Fall wird die innere Schleife n-1 mal ausgeführt, so dass die Gesamtanzahl der Ausführungen die Summe für i , die von 0 zu n-1 (weil niedriger als, nicht niedriger als oder gleich) von ni . Sie erhalten schließlich n*(n + 1) / 2 , also O(n²/2) = O(n²) .

Für die 2. Schleife ist i zwischen 0 und n für die äußere Schleife enthalten; dann wird die innere Schleife ausgeführt, wenn j streng größer als n , was dann unmöglich ist.




great question!

If you're using the Big O, you're talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Ok, so now what do we mean by "best-case" and "worst-case" complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it'll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.




For code A, the outer loop will execute for n+1 times, the '1' time means the process which checks the whether i still meets the requirement. And inner loop runs n times, n-2 times.... Thus, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

For code B, though inner loop wouldn't step in and execute the foo(), the inner loop will be executed for n times depend on outer loop execution time, which is O(n)




Grundsätzlich ist die Sache, die 90% der Zeit auftaucht, nur Schleifen zu analysieren. Haben Sie einzelne, doppelte, dreifach verschachtelte Schleifen? Sie haben O (n), O (n ^ 2), O (n ^ 3) Laufzeit.

Sehr selten (es sei denn, Sie schreiben eine Plattform mit einer umfangreichen Basisbibliothek (wie zB .NET BCL oder C ++'s STL), werden Sie auf etwas stoßen, das schwieriger ist, als nur Ihre Schleifen zu betrachten (für Anweisungen, while, goto, etc...)




Fangen wir von vorne an.

Nehmen Sie zunächst das Prinzip an, dass bestimmte einfache Operationen an Daten in O(1) -Zeit durchgeführt werden können, dh in einer Zeit, die unabhängig von der Größe der Eingabe ist. Diese primitiven Operationen in C bestehen aus

  1. Arithmetische Operationen (zB + oder%).
  2. Logische Operationen (zB &&).
  3. Vergleichsoperationen (zB <=)
  4. Strukturzugriffe (z. B. Array-Indizierung wie A [i] oder Zeiger nach dem Operator ->).
  5. Einfache Zuweisung wie das Kopieren eines Wertes in eine Variable.
  6. Ruft Bibliotheksfunktionen auf (z. B. scanf, printf).

Die Begründung für dieses Prinzip erfordert ein detailliertes Studium der Maschinenanweisungen (primitive Schritte) eines typischen Computers. Jede der beschriebenen Operationen kann mit einer kleinen Anzahl von Maschinenbefehlen durchgeführt werden; oft werden nur ein oder zwei Anweisungen benötigt. Als Folge können mehrere Arten von Anweisungen in C in O(1) -Zeit ausgeführt werden, dh in einer konstanten, von der Eingabe unabhängigen Zeit. Diese einfachen enthalten

  1. Zuweisungsanweisungen, die keine Funktionsaufrufe in ihren Ausdrücken enthalten.
  2. Lesen Sie die Anweisungen.
  3. Schreiben Sie Anweisungen, die keine Funktionsaufrufe zum Auswerten von Argumenten erfordern.
  4. Die Sprunganweisungen break, continue, goto und return expression, wobei ausdruck keinen Funktionsaufruf enthält.

In C werden viele for-Schleifen gebildet, indem eine Indexvariable auf einen Wert initialisiert wird und diese Variable jedes Mal um 1 inkrementiert wird. Die for-Schleife endet, wenn der Index ein Limit erreicht. Zum Beispiel die for-Schleife

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

verwendet die Indexvariable i. Sie erhöht jedesmal um die Schleife i um 1, und die Iterationen enden, wenn ich n - 1 erreiche.

Konzentrieren Sie sich jedoch im Moment auf die einfache Form der for-Schleife, bei der die Differenz zwischen den End- und Initialwerten geteilt durch den Betrag, um den die Indexvariable inkrementiert wird, angibt, wie oft wir die Schleife durchlaufen . Diese Anzahl ist genau, es sei denn, es gibt Möglichkeiten, die Schleife über eine Sprunganweisung zu verlassen; es ist in jedem Fall eine obere Grenze für die Anzahl der Iterationen.

Zum Beispiel iteriert die For-Schleife ((n − 1) − 0)/1 = n − 1 times , da 0 der Anfangswert von i ist, n - 1 der höchste Wert ist, der von i erreicht wird (dh wenn i erreicht wird n-1 stoppt die Schleife und es findet keine Iteration mit i = n-1 statt, und bei jeder Iteration der Schleife wird 1 zu i addiert.

Im einfachsten Fall, wenn die Zeit, die im Schleifenkörper verbracht wird, für jede Iteration gleich ist, können wir die obere Schranke für den Körper nach der Anzahl der Schleifen um den Faktor multiplizieren . Genau genommen müssen wir dann O (1) Zeit hinzufügen, um den Schleifenindex und O (1) Zeit für den ersten Vergleich des Schleifenindex mit dem Grenzwert zu initialisieren , weil wir ein weiteres Mal testen, als wir die Schleife durchlaufen. Wenn es jedoch nicht möglich ist, die Schleifen-Null-Zeiten auszuführen, ist die Zeit zum Initialisieren der Schleife und zum einmaligen Testen der Grenze ein Ausdruck niedriger Ordnung, der durch die Summierungsregel fallen gelassen werden kann.

Betrachten Sie nun dieses Beispiel:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

Wir wissen, dass Zeile (1) O(1) Zeit braucht. Klar, wir gehen n-mal um die Schleife herum, wie wir durch Subtrahieren der unteren Grenze von der oberen Grenze in Zeile (1) und dann Hinzufügen von 1 bestimmen können. Da der Körper, Zeile (2), O (1) Zeit benötigt, wir können die Zeit vernachlässigen, um j zu vergrößern und die Zeit, um j mit n zu vergleichen, die beide auch O (1) sind. Somit ist die Laufzeit der Linien (1) und (2) das Produkt von n und O (1) , welches O(n) .

Ähnlich können wir die Laufzeit der äußeren Schleife, die aus den Linien (2) bis (4) besteht, begrenzen

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

Wir haben bereits festgestellt, dass die Schleife der Linien (3) und (4) O (n) Zeit benötigt. Daher können wir die O (1) -Zeit vernachlässigen, um i zu inkrementieren und zu testen, ob i <n in jeder Iteration ist, was zu dem Schluss führt, dass jede Iteration der äußeren Schleife O (n) -Zeit benötigt.

Die Initialisierung i = 0 der äußeren Schleife und der (n + 1) st-Test der Bedingung i <n benötigen ebenfalls O (1) Zeit und können vernachlässigt werden. Schließlich beobachten wir, dass wir die äußere Schleife n-mal durchlaufen, wobei wir für jede Iteration eine O (n) -Zeit nehmen, was eine totale O(n^2) -Laufzeit ergibt.

Ein praktischeres Beispiel.




Wenn Ihre Kosten ein Polynom sind, behalten Sie einfach den höchsten Begriff ohne seinen Multiplikator bei. Z.B:

O ((n / 2 + 1) * (n / 2)) = O (n² / 4 + n / 2) = O (n² / 4) = O (n²)

Dies funktioniert nicht für unendliche Reihen, wohlgemerkt. Es gibt kein einzelnes Rezept für den allgemeinen Fall, obwohl für einige häufige Fälle die folgenden Ungleichungen gelten:

O (log N ) <O ( N ) <O ( N log N ) <O ( N 2 ) <0 ( N k ) <O ( en ) <O ( n !)




Im Allgemeinen weniger nützlich, denke ich, aber der Vollständigkeit halber gibt es auch ein großes Omega Ω , das eine Untergrenze für die Komplexität eines Algorithmus definiert, und ein Big Theta Θ , das sowohl eine obere als auch eine untere Grenze definiert.




Vergessen Sie nicht, auch Platzkomplexitäten in Betracht zu ziehen, die ebenfalls Anlass zur Sorge geben können, wenn die Speicherressourcen begrenzt sind. So können Sie zum Beispiel jemanden hören, der einen konstanten Raumalgorithmus wünscht, der im Grunde eine Art ist zu sagen, dass der von dem Algorithmus eingenommene Raum nicht von irgendwelchen Faktoren innerhalb des Codes abhängt.

Sometimes the complexity can come from how many times is something called, how often is a loop executed, how often is memory allocated, and so on is another part to answer this question.

Lastly, big O can be used for worst case, best case, and amortization cases where generally it is the worst case that is used for describing how bad an algorithm may be.




Kleine Erinnerung: Die big O Notation wird verwendet, um asymptotische Komplexität zu bezeichnen ( dh wenn die Größe des Problems unendlich wird), und es verbirgt eine Konstante.

Dies bedeutet, dass zwischen einem Algorithmus in O (n) und einem in O (n 2 ) der schnellste nicht immer der erste ist (obwohl es immer einen Wert von n gibt, so dass für Probleme der Größe> n der erste Algorithmus ist das schnellste).

Beachten Sie, dass die versteckte Konstante sehr von der Implementierung abhängt!

In einigen Fällen ist die Laufzeit auch keine deterministische Funktion der Größe n der Eingabe. Nehmen Sie die Sortierung beispielsweise mit der Schnellsortierung: Die Zeit, die zum Sortieren eines Arrays aus n Elementen benötigt wird, ist keine Konstante, sondern hängt von der Startkonfiguration des Arrays ab.

Es gibt unterschiedliche Zeitkomplexitäten:

  • Worst Case (normalerweise der einfachste, um herauszufinden, obwohl nicht immer sehr sinnvoll)
  • Durchschnittlicher Fall (normalerweise viel schwerer herauszufinden ...)

  • ...

Eine gute Einführung ist eine Einführung in die Analyse von Algorithmen von R. Sedgewick und P. Flajolet.

Wie Sie sagen, ist premature optimisation is the root of all evil , und (wenn möglich) sollte Profiling immer verwendet werden, wenn Code optimiert wird. Es kann Ihnen sogar helfen, die Komplexität Ihrer Algorithmen zu bestimmen.




Große O-Notation ist nützlich, weil es einfach ist, mit unnötigen Komplikationen und Details zu arbeiten und zu verbergen (für einige Definition von unnötig). Eine gute Möglichkeit, die Komplexität von Divide and Conquer-Algorithmen zu berechnen, ist die Tree-Methode. Nehmen wir an, Sie haben eine Version von Quicksort mit der Median-Prozedur, so dass Sie das Array jedes Mal in perfekt ausbalancierte Sub-Arrays aufteilen.

Erstellen Sie nun einen Baum, der allen Arrays entspricht, mit denen Sie arbeiten. An der Wurzel haben Sie das ursprüngliche Array, die Wurzel hat zwei Kinder, die die Subarrays sind. Wiederholen Sie dies, bis Sie einzelne Elementarrays am unteren Rand haben.

Da wir den Median in O (n) Zeit finden und das Array in zwei Teile in O (n) teilen können, ist die Arbeit an jedem Knoten O (k), wobei k die Größe des Arrays ist. Jede Ebene des Baumes enthält (maximal) das gesamte Array, so dass die Arbeit pro Level O (n) ist (die Größen der Subarrays summieren sich zu n, und da wir O (k) pro Level haben, können wir das addieren) . Es gibt nur log (n) Ebenen im Baum seit jeder Halbierung der Eingabe.

Daher können wir die Menge der Arbeit durch O (n * log (n)) begrenzen.

Big O verbirgt jedoch einige Details, die wir manchmal nicht ignorieren können. Erwäge, die Fibonacci-Sequenz mit zu berechnen

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

und nehmen wir einfach an, die a und b sind BigIntegers in Java oder etwas, das mit beliebig großen Zahlen umgehen kann. Die meisten Leute würden sagen, das ist ein O (n) Algorithmus ohne zu zucken. Der Grund dafür ist, dass Sie in der for-Schleife n-Iterationen und in der Schleife o (1) arbeiten.

Aber Fibonacci-Zahlen sind groß, die n-te Fibonacci-Zahl ist exponentiell in n, also wird nur die Speicherung in der Größenordnung von n Bytes erfolgen. Die Addition mit großen Ganzzahlen erfordert O (n) Arbeitsaufwand. Also ist die Gesamtmenge der Arbeit in diesem Verfahren getan

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

Also läuft dieser Algorithmus in Quadradzeit!




Related