algorithm - Big O, wie berechnet / approximiert man es?

Translate

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

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

1 aber wie sie sagen, übertreibe es nicht,Vorzeitige Optimierung ist die Wurzel allen Übelsund Optimierung ohne berechtigten Grund sollte diesen Namen ebenfalls verdienen.

This question and all comments follow the "Attribution Required."

Alle Antworten

vz0
Translate

Ich werde mein Bestes tun, um es hier in einfachen Worten zu erklären, aber seien Sie gewarnt, dass meine Schüler ein paar Monate brauchen, um dieses Thema endlich zu verstehen. Weitere Informationen finden Sie in Kapitel 2 derDatenstrukturen und Algorithmen in JavaBuch.


Es gibt keinmechanischer Vorgangdas kann verwendet werden, um das BigOh zu bekommen.

Als "Kochbuch", um die zu erhaltenBigOhAus einem Teil des Codes müssen Sie zunächst erkennen, dass Sie eine mathematische Formel erstellen, um zu zählen, wie viele Berechnungsschritte bei einer Eingabe einer bestimmten Größe ausgeführt werden.

Der Zweck ist einfach: Algorithmen aus theoretischer Sicht zu vergleichen, ohne den Code ausführen zu müssen. Je geringer die Anzahl der Schritte ist, desto schneller ist der Algorithmus.

Angenommen, Sie haben diesen Code:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

Diese Funktion gibt die Summe aller Elemente des Arrays zurück, und wir möchten eine Formel erstellen, um die zu zählenRechenkomplexitätdieser Funktion:

Number_Of_Steps = f(N)

Also haben wirf(N), eine Funktion zum Zählen der Anzahl von Rechenschritten. Die Eingabe der Funktion ist die Größe der zu verarbeitenden Struktur. Dies bedeutet, dass diese Funktion wie folgt aufgerufen wird:

Number_Of_Steps = f(data.length)

Der ParameterNnimmt diedata.lengthWert. Jetzt brauchen wir die eigentliche Definition der Funktionf(). Dies geschieht aus dem Quellcode, in dem jede interessante Zeile von 1 bis 4 nummeriert ist.

Es gibt viele Möglichkeiten, den BigOh zu berechnen. Von diesem Punkt an gehen wir davon aus, dass jeder Satz, der nicht von der Größe der Eingabedaten abhängt, eine Konstante hatCAnzahl Rechenschritte.

Wir werden die einzelne Anzahl von Schritten der Funktion hinzufügen, und weder die lokale Variablendeklaration noch die return-Anweisung hängen von der Größe der abdataArray.

Das bedeutet, dass die Zeilen 1 und 4 jeweils C Schritte umfassen, und die Funktion ist ungefähr so:

f(N) = C + ??? + C

Der nächste Teil besteht darin, den Wert von zu definierenforErklärung. Denken Sie daran, dass wir die Anzahl der Rechenschritte zählen, was bedeutet, dass der Körper desforAnweisung wird ausgeführtNmal. Das ist das gleiche wie das HinzufügenC, Nmal:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

Es gibt keine mechanische Regel, um zu zählen, wie oft der Körper desforWird es ausgeführt, müssen Sie es zählen, indem Sie sich ansehen, was der Code tut. Um die Berechnungen zu vereinfachen, ignorieren wir die Variableninitialisierungs-, Bedingungs- und Inkrementteile derforErklärung.

Um das eigentliche BigOh zu bekommen, brauchen wir dasAsymptotische Analyseder Funktion. Dies geschieht ungefähr so:

  1. Nehmen Sie alle Konstanten wegC.
  2. Vonf()bekommen dasPolynomin seinemstandard form.
  3. Teilen Sie die Begriffe des Polynoms und sortieren Sie sie nach der Wachstumsrate.
  4. Behalte die, die größer wird, wennNnähert sichinfinity.

Unseref()hat zwei Begriffe:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

Alle wegnehmenCKonstanten und redundante Teile:

f(N) = 1 + N ^ 1

Da ist der letzte Begriff derjenige, der größer wird, wennf()nähert sich der Unendlichkeit (denken Sie weiterGrenzen) Dies ist das BigOh-Argument und dassum()Funktion hat eine BigOh von:

O(N)

Es gibt ein paar Tricks, um einige knifflige zu lösen: VerwendenSummationenwann immer du kannst.

Dieser Code kann beispielsweise einfach mithilfe von Summierungen gelöst werden:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

Das erste, was Sie gefragt werden mussten, ist die Reihenfolge der Ausführung vonfoo(). Während das Übliche sein sollO(1)müssen Sie Ihre Professoren danach fragen.O(1)bedeutet (fast, meistens) konstantC, unabhängig von der GrößeN.

DasforAussage zum ersten Satz ist schwierig. Während der Index endet bei2 * Nwird das Inkrement um zwei gemacht. Das heißt, dass die ersteforwird nur ausgeführtNSchritte, und wir müssen die Anzahl durch zwei teilen.

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

Die Satznummerzweiist noch schwieriger, da es vom Wert von abhängti. Schauen Sie mal: Der Index i nimmt die Werte an: 0, 2, 4, 6, 8, ..., 2 * N und der zweiteforausgeführt werden: N mal die erste, N - 2 die zweite, N - 4 die dritte ... bis zur N / 2 Stufe, auf der die zweiteforwird nie hingerichtet.

Auf der Formel bedeutet das:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

Wieder zählen wirdie Anzahl der Schritte. Und per Definition sollte jede Summierung immer bei eins beginnen und bei einer Zahl enden, die größer oder gleich eins ist.

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(Wir gehen davon ausfoo()istO(1)und nimmtCSchritte.)

Wir haben hier ein Problem: wanninimmt den WertN / 2 + 1nach oben endet die innere Summation mit einer negativen Zahl! Das ist unmöglich und falsch. Wir müssen die Summe in zwei Teile teilen, da sie im Moment der Dreh- und Angelpunkt istinimmtN / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

Seit dem entscheidenden Momenti > N / 2, das Innereforwird nicht ausgeführt, und wir gehen von einer konstanten Komplexität der C-Ausführung in seinem Körper aus.

Jetzt können die Summierungen mithilfe einiger Identitätsregeln vereinfacht werden:

  1. Summe (w von 1 bis N) (C) = N * C.
  2. Summation (w von 1 bis N) (A (+/-) B) = Summation (w von 1 bis N) (A) (+/-) Summation (w von 1 bis N) (B)
  3. Summation (w von 1 bis N) (w * C) = C * Summation (w von 1 bis N) (w) (C ist eine Konstante, unabhängig vonw)
  4. Summe (w von 1 bis N) (w) = (N * (N + 1)) / 2

Algebra anwenden:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

Und das BigOh ist:

O(N²)
Quelle
Translate

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 an anderer Stelle verwendet werden.

Einige Beispiele für die Verwendung in C-Code.

Angenommen, wir haben ein Array von n Elementen

int array[n];

Wenn wir auf das erste Element des Arrays zugreifen möchten, ist dies O (1), da es egal ist, wie groß das Array ist, es dauert 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 unsere Zahl möglicherweise beim ersten Versuch finden und einmal durch die Schleife laufen, weil Big-O die Obergrenze für einen Algorithmus beschreibt (Omega steht für Untergrenze und Theta für Enge). .

Wenn wir zu verschachtelten Schleifen kommen:

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

Dies ist O (n ^ 2), da wir für jeden Durchgang der äußeren Schleife (O (n)) die gesamte Liste erneut durchgehen müssen, damit sich die n multiplizieren und wir mit n im Quadrat zurückbleiben.

Dies kratzt kaum an der Oberfläche, aber wenn Sie komplexere Algorithmen analysieren, kommt die komplexe Mathematik mit Beweisen ins Spiel. Ich hoffe, dies macht Sie zumindest mit den Grundlagen vertraut.

Quelle
Translate

Obwohl es hilfreich ist, die Big O-Zeit für Ihr spezielles Problem zu ermitteln, kann es hilfreich sein, einige allgemeine Fälle zu kennen, um Entscheidungen in Ihrem Algorithmus zu treffen.

Hier sind einige der häufigsten Fälle, aus denen herausgehoben wurdehttp://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O (1) - Bestimmen, ob eine Zahl gerade oder ungerade ist; Verwenden einer Nachschlagetabelle oder Hash-Tabelle mit konstanter Größe

O (logn) - Suchen eines Elements in einem sortierten Array mit einer binären Suche

O (n) - Suchen eines Elements in einer unsortierten Liste; Hinzufügen von zwei n-stelligen Zahlen

Auf2) - Multiplizieren von zwei n-stelligen Zahlen mit einem einfachen Algorithmus; Hinzufügen von zwei n × n Matrizen; Blasensortierung oder Einfügesortierung

Auf3) - Multiplizieren von zwei n × n Matrizen mit einem einfachen Algorithmus

O (cn) - Finden der (genauen) Lösung für das Problem des Handlungsreisenden durch dynamische Programmierung; Bestimmen, ob zwei logische Anweisungen mit Brute Force äquivalent sind

O (n!) - Lösen des Problems mit Handlungsreisenden durch Brute-Force-Suche

Aufn) - Wird häufig anstelle von O (n!) Verwendet, um einfachere Formeln für die asymptotische Komplexität abzuleiten

Quelle
Translate

Kleine Erinnerung: diebig ONotation wird verwendet, um zu bezeichnenasymptotischKomplexität (dh wenn die Größe des Problems unendlich wird),undes verbirgt eine Konstante.

Dies bedeutet, dass zwischen einem Algorithmus in O (n) und einem in O (n)2) ist der schnellste nicht immer der erste (obwohl es immer einen Wert von n gibt, so dass bei Problemen mit einer Größe> n der erste Algorithmus der schnellste ist).

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

In einigen Fällen ist die Laufzeit auch keine deterministische Funktion derGrößen der Eingabe. Nehmen wir zum Beispiel die Sortierung mit der Schnellsortierung: Die zum Sortieren eines Arrays von n Elementen benötigte Zeit ist keine Konstante, sondern hängt von der Startkonfiguration des Arrays ab.

Es gibt verschiedene zeitliche Komplexitäten:

  • Schlimmster Fall (normalerweise am einfachsten herauszufinden, aber nicht immer sehr aussagekräftig)
  • Durchschnittlicher Fall (normalerweise viel schwieriger herauszufinden ...)

  • ...

Eine gute Einführung istEine Einführung in die Analyse von Algorithmenvon R. Sedgewick und P. Flajolet.

Wie du sagst,premature optimisation is the root of all evilund (wenn möglich)Profilerstellungsollte wirklich immer bei der Optimierung von Code verwendet werden. Es kann Ihnen sogar helfen, die Komplexität Ihrer Algorithmen zu bestimmen.

Quelle
Translate

Wenn wir die Antworten hier sehen, können wir daraus schließen, dass die meisten von uns tatsächlich die Reihenfolge des Algorithmus durch annähernsuchenund verwenden Sie den gesunden Menschenverstand, anstatt es zum Beispiel mit dem zu berechnenMaster-Methodewie wir an der Universität gedacht wurden. Vor diesem Hintergrund muss ich hinzufügen, dass sogar der Professor uns (später) dazu ermutigt hatÜberlegendarüber, anstatt es nur zu berechnen.

Außerdem möchte ich hinzufügen, wie es gemacht wirdrekursive Funktionen:

Angenommen, wir haben eine Funktion wie (Schema-Code):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

die rekursiv die Fakultät der gegebenen Zahl berechnet.

Der erste Schritt besteht darin, das Leistungsmerkmal für zu bestimmennur der Körper der FunktionIn diesem Fall wird im Körper nichts Besonderes getan, nur eine Multiplikation (oder die Rückgabe des Wertes 1).

Also dieLeistung für den Körper ist: O (1)(Konstante).

Versuchen Sie als nächstes, dies für die zu bestimmenAnzahl der rekursiven Aufrufe. In diesem Fall haben wir n-1 rekursive Aufrufe.

Also dieLeistung für die rekursiven Aufrufe ist: O (n-1)(Ordnung ist n, da wir die unbedeutenden Teile wegwerfen).

Dann setzen Sie diese beiden zusammen und Sie haben dann die Leistung für die gesamte rekursive Funktion:

1 * (n-1) = O (n)


Peter, AntwortenIhre aufgeworfenen Fragen;Die hier beschriebene Methode handhabt dies tatsächlich recht gut. Aber denken Sie daran, dass dies immer noch eine istAnnäherungund keine vollständige mathematisch korrekte Antwort. Die hier beschriebene Methode ist auch eine der Methoden, die uns an der Universität beigebracht wurden, und wenn ich mich recht erinnere, wurde sie für weitaus fortgeschrittenere Algorithmen verwendet als die in diesem Beispiel verwendete Fakultät.
Natürlich hängt alles davon ab, wie gut Sie die Laufzeit des Funktionskörpers und die Anzahl der rekursiven Aufrufe abschätzen können, aber das gilt auch für die anderen Methoden.

Quelle
Translate

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

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

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

O (logN) <O (N) <O (NLogN) <O (N2) <O (Nk) <O (en) <O (n!)

Quelle
Translate

Ich denke darüber in Bezug auf Informationen nach. Jedes Problem besteht darin, eine bestimmte Anzahl von Bits zu lernen.

Ihr grundlegendes Werkzeug ist das Konzept der Entscheidungspunkte und ihrer Entropie. Die Entropie eines Entscheidungspunkts ist die durchschnittliche Information, die er Ihnen gibt. Wenn ein Programm beispielsweise einen Entscheidungspunkt mit zwei Zweigen enthält, ist seine Entropie die Summe der Wahrscheinlichkeit jedes Zweigs multipliziert mit dem Protokoll2der inversen Wahrscheinlichkeit dieses Zweigs. So viel lernen Sie, wenn Sie diese Entscheidung treffen.

Zum Beispiel einifAussage mit zwei Zweigen, beide gleich wahrscheinlich, hat eine Entropie von 1/2 * log (2/1) + 1/2 * log (2/1) = 1/2 * 1 + 1/2 * 1 = 1. Also seine Entropie beträgt 1 Bit.

Angenommen, Sie durchsuchen eine Tabelle mit N Elementen wie N = 1024. Dies ist ein 10-Bit-Problem, da log (1024) = 10 Bit ist. Wenn Sie es also mit IF-Anweisungen durchsuchen können, deren Ergebnisse gleich wahrscheinlich sind, sollten 10 Entscheidungen getroffen werden.

Das bekommen Sie mit der binären Suche.

Angenommen, Sie führen eine lineare Suche durch. Sie schauen sich das erste Element an und fragen, ob es das ist, das Sie wollen. Die Wahrscheinlichkeiten sind 1/1024, dass es ist, und 1023/1024, dass es nicht ist. Die Entropie dieser Entscheidung ist 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * ungefähr 0 = ungefähr 0,01 Bit. Du hast sehr wenig gelernt! Die zweite Entscheidung ist nicht viel besser. Deshalb ist die lineare Suche so langsam. Tatsächlich ist die Anzahl der zu lernenden Bits exponentiell.

Angenommen, Sie führen eine Indizierung durch. Angenommen, die Tabelle ist in viele Bins vorsortiert, und Sie verwenden einige der Bits im Schlüssel, um direkt auf den Tabelleneintrag zu indizieren. Wenn 1024 Bins vorhanden sind, beträgt die Entropie 1/1024 * log (1024) + 1/1024 * log (1024) + ... für alle 1024 möglichen Ergebnisse. Dies sind 1/1024 * 10 mal 1024 Ergebnisse oder 10 Entropiebits für diese eine Indizierungsoperation. Deshalb ist die Indizierungssuche schnell.

Denken Sie jetzt über das Sortieren nach. Sie haben N Elemente und Sie haben eine Liste. Für jedes Element müssen Sie suchen, wo sich das Element in der Liste befindet, und es dann der Liste hinzufügen. Das Sortieren dauert also ungefähr das N-fache der Anzahl der Schritte der zugrunde liegenden Suche.

Sortierungen, die auf binären Entscheidungen mit ungefähr gleich wahrscheinlichen Ergebnissen basieren, erfordern alle ungefähr O (N log N) Schritte. Ein O (N) -Sortieralgorithmus ist möglich, wenn er auf der Indizierungssuche basiert.

Ich habe festgestellt, dass fast alle algorithmischen Leistungsprobleme auf diese Weise betrachtet werden können.

Quelle
Translate

Fangen wir von vorne an.

Akzeptieren Sie zunächst das Prinzip, dass bestimmte einfache Operationen an Daten in ausgeführt werden könnenO(1)Zeit, 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 (z. B. &&).
  3. Vergleichsoperationen (zB <=).
  4. Strukturzugriffsoperationen (z. B. Array-Indizierung wie A [i] oder Zeiger nach dem Operator ->).
  5. Einfache Zuordnung wie das Kopieren eines Wertes in eine Variable.
  6. Ruft Bibliotheksfunktionen auf (z. B. scanf, printf).

Die Begründung für dieses Prinzip erfordert eine detaillierte Untersuchung der Maschinenanweisungen (primitiven Schritte) eines typischen Computers. Jede der beschriebenen Operationen kann mit einer kleinen Anzahl von Maschinenanweisungen ausgeführt werden; oft werden nur ein oder zwei Anweisungen benötigt. Infolgedessen können verschiedene Arten von Anweisungen in C in ausgeführt werdenO(1)Zeit, dh in einer konstanten Zeitspanne, unabhängig von der Eingabe. Diese einfachen gehören

  1. Zuweisungsanweisungen, die keine Funktionsaufrufe in ihren Ausdrücken enthalten.
  2. Aussagen lesen.
  3. Schreiben Sie Anweisungen, für die keine Funktionsaufrufe erforderlich sind, um Argumente auszuwerten.
  4. Die Sprunganweisungen brechen, setzen fort, gehen zu und geben den Ausdruck zurück, wobei der Ausdruck keinen Funktionsaufruf enthält.

In C werden viele for-Schleifen gebildet, indem eine Indexvariable auf einen bestimmten Wert initialisiert und diese Variable jedes Mal um die Schleife um 1 erhöht wird. Die for-Schleife endet, wenn der Index eine Grenze 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. Es erhöht i jedes Mal um die Schleife um 1, und die Iterationen hören auf, wenn i n - 1 erreicht.

Konzentrieren Sie sich im Moment jedoch auf die einfache Form der for-Schleife, bei der dieDie Differenz zwischen dem End- und dem Anfangswert, geteilt durch den Betrag, um den die Indexvariable erhöht wird, gibt an, 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 Obergrenze für die Anzahl der Iterationen.

Zum Beispiel iteriert die for-Schleife((n − 1) − 0)/1 = n − 1 timesDa 0 der Anfangswert von i ist, ist n - 1 der höchste von i erreichte Wert (dh wenn i n - 1 erreicht, stoppt die Schleife und es tritt keine Iteration mit i = n - 1 auf), und 1 wird addiert i bei jeder Iteration der Schleife.

Im einfachsten Fall, wenn die im Schleifenkörper verbrachte Zeit für jede Iteration gleich ist,Wir können die Big-Oh-Obergrenze für den Körper mit der Häufigkeit multiplizieren, mit der die Schleife umrundet wird. Genau genommen müssen wir dannAddiere O (1) Zeit, um den Schleifenindex zu initialisieren, und O (1) Zeit für den ersten Vergleich des Schleifenindex mit dem Grenzwert, weil wir noch einmal testen, als wir um die Schleife gehen. Sofern es nicht möglich ist, die Schleife nullmal auszuführen, ist die Zeit zum Initialisieren der Schleife und zum einmaligen Testen des Grenzwerts ein Term niedriger Ordnung, der durch die Summierungsregel gelöscht werden kann.


Betrachten Sie nun dieses Beispiel:

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

Wir wissen dasLinie 1)nimmtO(1)Zeit. Es ist klar, dass wir die Schleife n-mal umgehen, wie wir feststellen können, indem wir die Untergrenze von der Obergrenze in Zeile (1) subtrahieren und dann 1 addieren. Da der Körper, Zeile (2), O (1) Zeit benötigt, wir können die Zeit zum Inkrementieren von j und die Zeit zum Vergleichen von j mit n vernachlässigen, die beide auch O (1) sind. Somit ist die Laufzeit der Zeilen (1) und (2) dieProdukt von n und O (1), welches istO(n).

In ähnlicher Weise 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 Zeilen (3) und (4) O (n) Zeit benötigt. Somit können wir die O (1) -Zeit vernachlässigen, um i zu erhöhen 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) -te Test der Bedingung i <n dauern ebenfalls O (1) und können vernachlässigt werden. Schließlich beobachten wir, dass wir n-mal um die äußere Schleife herumgehen und für jede Iteration O (n) -Zeit nehmen, was eine Summe ergibtO(n^2)Laufzeit.


Ein praktischeres Beispiel.

enter image description here

Quelle
Translate

Wenn Sie die Reihenfolge Ihres Codes empirisch schätzen möchten, anstatt den Code zu analysieren, können Sie eine Reihe ansteigender Werte für n und die Zeit Ihres Codes eingeben. Zeichnen Sie Ihre Timings auf einer Protokollskala. Wenn der Code O (x ^ n) ist, sollten die Werte auf eine Linie der Steigung n fallen.

Dies hat mehrere Vorteile gegenüber dem bloßen Studium des Codes. Zum einen können Sie sehen, ob Sie sich in dem Bereich befinden, in dem sich die Laufzeit ihrer asymptotischen Reihenfolge nähert. Möglicherweise stellen Sie auch fest, dass ein Code, von dem Sie dachten, er sei die Reihenfolge O (x), tatsächlich die Reihenfolge O (x ^ 2) ist, beispielsweise aufgrund der Zeit, die für Bibliotheksaufrufe aufgewendet wurde.

Quelle
Translate

Grundsätzlich werden in 90% der Fälle nur Schleifen analysiert. Haben Sie einfache, doppelte oder dreifach verschachtelte Schleifen? Die haben Sie O (n), O (n ^ 2), O (n ^ 3) Laufzeit.

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

Quelle
Gustave Lee
Translate

Die Big O-Notation ist nützlich, da sie einfach zu bearbeiten ist und unnötige Komplikationen und Details verbirgt (für eine Definition von unnötig). Eine gute Möglichkeit, die Komplexität von Divide- und Conquer-Algorithmen zu ermitteln, ist die Baummethode. Angenommen, Sie haben eine Version von Quicksort mit der Medianprozedur, sodass Sie das Array jedes Mal in perfekt ausbalancierte Subarrays 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 untergeordnete Elemente, die die Subarrays sind. Wiederholen Sie diesen Vorgang, bis Sie unten einzelne Elementarrays haben.

Da wir den Median in O (n) -Zeit finden und das Array in O (n) -Zeit in zwei Teile teilen können, ist die an jedem Knoten geleistete Arbeit O (k), wobei k die Größe des Arrays ist. Jede Ebene des Baums enthält (höchstens) das gesamte Array, sodass die Arbeit pro Ebene O (n) beträgt (die Größen der Subarrays addieren sich zu n, und da wir O (k) pro Ebene haben, können wir dies addieren). . Es gibt nur log (n) Ebenen im Baum, da jedes Mal, wenn wir die Eingabe halbieren.

Daher können wir den Arbeitsaufwand durch O (n * log (n)) nach oben begrenzen.

Big O verbirgt jedoch einige Details, die wir manchmal nicht ignorieren können. Erwägen Sie die Berechnung der Fibonacci-Sequenz mit

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

und nehmen wir einfach an, dass a und b BigInteger in Java sind oder etwas, das beliebig große Zahlen verarbeiten kann. Die meisten Leute würden sagen, dass dies ein O (n) -Algorithmus ist, ohne zusammenzuzucken. Der Grund dafür ist, dass Sie n Iterationen in der for-Schleife haben und O (1) neben der Schleife arbeiten.

Aber Fibonacci-Zahlen sind groß, die n-te Fibonacci-Zahl ist in n exponentiell, so dass nur das Speichern in der Größenordnung von n Bytes erfolgt. Das Durchführen einer Addition mit großen ganzen Zahlen erfordert O (n) Arbeit. Der Gesamtaufwand für dieses Verfahren beträgt also

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

Dieser Algorithmus läuft also in quadratischer Zeit!

Quelle
Translate

Allgemein weniger nützlich, denke ich, aber der Vollständigkeit halber gibt es auch eineBig Omega Ω, die eine Untergrenze für die Komplexität eines Algorithmus definiert, und aBig Theta Θ, die sowohl eine Ober- als auch eine Untergrenze definiert.

Quelle
Translate

Teilen Sie den Algorithmus in Teile auf, für die Sie die große O-Notation kennen, und kombinieren Sie sie durch große O-Operatoren. Das ist der einzige Weg, den ich kenne.

Weitere Informationen finden Sie unterWikipedia-Seitezum Thema.

Quelle
Translate

Vertrautheit mit den von mir verwendeten Algorithmen / Datenstrukturen und / oder schnelle Analyse der Iterationsverschachtelung. Die Schwierigkeit besteht darin, dass Sie eine Bibliotheksfunktion möglicherweise mehrmals aufrufen. Oft können Sie sich nicht sicher sein, ob Sie die Funktion manchmal unnötig aufrufen oder welche Implementierung sie verwenden. Möglicherweise sollten Bibliotheksfunktionen ein Komplexitäts- / Effizienzmaß haben, sei es Big O oder eine andere Metrik, die in der Dokumentation oder sogar verfügbar istIntelliSense.

Quelle
Translate

Dies ist ein Teil von "Wie berechnet man Big O?"Computational Complexity Theory. Für einige (viele) Sonderfälle können Sie möglicherweise einige einfache Heuristiken verwenden (z. B. das Multiplizieren der Anzahl der Schleifen für verschachtelte Schleifen), insbesondere wenn alles, was Sie wollen, eine Schätzung der Obergrenze ist und es Ihnen nichts ausmacht, wenn sie zu pessimistisch ist - worum es bei Ihrer Frage wahrscheinlich geht.

Wenn Sie Ihre Frage für einen Algorithmus wirklich beantworten möchten, können Sie die Theorie am besten anwenden. Neben der simplen "Worst-Case" -Analyse habe ich gefundenAmortisierte Analysesehr nützlich in der Praxis.

Quelle
Translate

Für den 1. Fall wird die innere Schleife ausgeführtn-imal, also ist die Gesamtzahl der Hinrichtungen die Summe fürigehen von0zun-1(weil niedriger als, nicht niedriger als oder gleich) dern-i. Du bekommst endlichn*(n + 1) / 2, damitO(n²/2) = O(n²).

Für die 2. Schleifeiist zwischen0undnenthalten für die äußere Schleife; dann wird die innere Schleife ausgeführt, wennjist streng größer alsn, was dann unmöglich ist.

Quelle
Translate

Zusätzlich zur Verwendung der Master-Methode (oder einer ihrer Spezialisierungen) teste ich meine Algorithmen experimentell. Das kann nichtbeweisendass eine bestimmte Komplexitätsklasse erreicht wird, aber es kann die Gewissheit geben, dass die mathematische Analyse angemessen ist. Um diese Sicherheit zu gewährleisten, verwende ich in Verbindung mit meinen Experimenten Tools zur Codeabdeckung, um sicherzustellen, dass ich alle Fälle ausführe.

Als sehr einfaches Beispiel sagen Sie, Sie wollten eine Überprüfung der Geschwindigkeit der Listensortierung des .NET Frameworks durchführen. Sie können Folgendes schreiben und dann die Ergebnisse in Excel analysieren, um sicherzustellen, dass sie eine n * log (n) -Kurve nicht überschreiten.

In diesem Beispiel messe ich die Anzahl der Vergleiche, aber es ist auch ratsam, die tatsächliche Zeit zu untersuchen, die für jede Stichprobengröße erforderlich ist. Dann müssen Sie jedoch noch vorsichtiger sein, dass Sie nur den Algorithmus messen und keine Artefakte aus Ihrer Testinfrastruktur einbeziehen.

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);
Quelle
Translate

Vergessen Sie nicht, auch Platzkomplexitäten zu berücksichtigen, die auch bei begrenzten Speicherressourcen Anlass zur Sorge geben können. So können Sie beispielsweise jemanden hören, der einen Algorithmus mit konstantem Speicherplatz wünscht. Dies bedeutet im Grunde, dass der vom Algorithmus belegte Speicherplatz nicht von Faktoren im Code abhängt.

Manchmal hängt die Komplexität davon ab, wie oft etwas aufgerufen wird, wie oft eine Schleife ausgeführt wird, wie oft Speicher zugewiesen wird usw. Ein weiterer Teil zur Beantwortung dieser Frage.

Schließlich kann großes O für Worst-Case-, Best-Case- und Amortisationsfälle verwendet werden, bei denen im Allgemeinen der Worst-Case verwendet wird, um zu beschreiben, wie schlecht ein Algorithmus sein kann.

Quelle
Translate

Was oft übersehen wird, ist daserwartetVerhalten Ihrer Algorithmen.Das Big-O Ihres Algorithmus wird dadurch nicht geändert, aber es bezieht sich auf die Aussage "vorzeitige Optimierung ..."

Das erwartete Verhalten Ihres Algorithmus ist - sehr niedergeschlagen - wie schnell Sie erwarten können, dass Ihr Algorithmus mit Daten arbeitet, die Sie am wahrscheinlichsten sehen.

Wenn Sie beispielsweise nach einem Wert in einer Liste suchen, ist dies O (n). Wenn Sie jedoch wissen, dass die meisten Listen, die Sie sehen, Ihren Wert im Voraus haben, ist das typische Verhalten Ihres Algorithmus schneller.

Um es wirklich zu verstehen, müssen Sie in der Lage sein, die Wahrscheinlichkeitsverteilung Ihres "Eingabebereichs" zu beschreiben (wenn Sie eine Liste sortieren müssen, wie oft wird diese Liste bereits sortiert? Wie oft wird sie vollständig umgekehrt? Wie oft ist es meistens sortiert?) Es ist nicht immer machbar, dass du das weißt, aber manchmal tust du es.

Quelle
Translate

tolle Frage!

Haftungsausschluss: Diese Antwort enthält falsche Aussagen, siehe Kommentare unten.

Wenn Sie das Big O verwenden, sprechen Sie über den schlimmsten Fall (mehr dazu später). Zusätzlich gibt es Kapital Theta für den Durchschnittsfall und ein großes Omega für den besten Fall.

Auf dieser Website finden Sie eine schöne formale Definition von Big O:https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f (n) = O (g (n)) bedeutet, dass es positive Konstanten c und k gibt, so dass 0 ≤ f (n) ≤ cg (n) für alle n ≥ k ist. Die Werte von c und k müssen für die Funktion f festgelegt werden und dürfen nicht von n abhängen.


Ok, was meinen wir nun mit "Best-Case" - und "Worst-Case" -Komplexität?

Dies wird wahrscheinlich am deutlichsten anhand von Beispielen veranschaulicht. Wenn wir beispielsweise die lineare Suche verwenden, um eine Zahl in einem sortierten Array zu finden, wird dieschlimmsten Fallist, wenn wir uns dazu entscheidenSuche nach dem letzten Elementdes Arrays, da dies so viele Schritte erfordern würde, wie Elemente im Array vorhanden sind. DasI'm besten fallwäre, wenn wir nach dem suchenerstes Elementda wären wir nach der ersten überprüfung fertig.

Der Sinn all dieserAdjektiv-komplexität ist, dass wir nach einer Möglichkeit suchen, die Zeitspanne, die ein hypothetisches Programm bis zur Fertigstellung durchläuft, in Bezug auf die Größe bestimmter Variablen grafisch darzustellen. Für viele Algorithmen kann man jedoch argumentieren, dass es für eine bestimmte Eingabegröße keine einzige Zeit gibt. Beachten Sie, dass dies der Grundvoraussetzung einer Funktion widerspricht. Jeder Eingang sollte nicht mehr als einen Ausgang haben. Also kommen wir aufmehrereFunktionen zur Beschreibung der Komplexität eines Algorithmus. Obwohl das Durchsuchen eines Arrays der Größe n je nach dem, wonach Sie im Array suchen, und proportional zu n unterschiedlich lange dauern kann, können wir eine informative Beschreibung des Algorithmus im besten Fall und im Durchschnittsfall erstellen und Worst-Case-Klassen.

Entschuldigung, das ist so schlecht geschrieben und es fehlen viele technische Informationen. Aber hoffentlich wird es einfacher, über Zeitkomplexitätsklassen nachzudenken. Sobald Sie sich mit diesen vertraut gemacht haben, müssen Sie nur noch Ihr Programm analysieren und nach For-Loops suchen, die von der Arraygröße und den Überlegungen abhängen, die auf Ihren Datenstrukturen basieren. Welche Art von Eingabe würde zu trivialen Fällen führen und welche Eingabe würde sich ergeben im schlimmsten Fall.

Quelle
Translate

Ich weiß nicht, wie ich das programmgesteuert lösen soll, aber das erste, was die Leute tun, ist, dass wir den Algorithmus für bestimmte Muster in der Anzahl der durchgeführten Operationen abtasten, sagen wir 4n ^ 2 + 2n + 1, wir haben 2 Regeln:

  1. Wenn wir eine Summe von Begriffen haben, wird der Begriff mit der größten Wachstumsrate beibehalten, wobei andere Begriffe weggelassen werden.
  2. Wenn wir ein Produkt aus mehreren Faktoren haben, werden konstante Faktoren weggelassen.

Wenn wir f (x) vereinfachen, wobei f (x) die Formel für die Anzahl der durchgeführten Operationen ist (4n ^ 2 + 2n + 1, wie oben erläutert), erhalten wir hier den Big-O-Wert [O (n ^ 2) Fall]. Dies müsste jedoch die Lagrange-Interpolation im Programm berücksichtigen, die möglicherweise schwer zu implementieren ist. Und was wäre, wenn der echte Big-O-Wert O (2 ^ n) wäre und wir möglicherweise so etwas wie O (x ^ n) hätten, sodass dieser Algorithmus wahrscheinlich nicht programmierbar wäre. Aber wenn mir jemand das Gegenteil beweist, gib mir den Code. . . .

Quelle
Translate

Für Code A wird die äußere Schleife für ausgeführtn+1mal bedeutet die '1' Zeit den Prozess, der prüft, ob ich die Anforderung noch erfülle. Und die innere Schleife läuftnmal,n-2mal .... also0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Für Code B wird, obwohl die innere Schleife nicht einspringen und foo () ausführen würde, die innere Schleife n-mal ausgeführt, abhängig von der Ausführungszeit der äußeren Schleife, die O (n) ist.

Quelle
HmT
Translate

Ich möchte das Big-O in einem etwas anderen Aspekt erklären.

Big-O dient nur dazu, die Komplexität der Programme zu vergleichen, dh wie schnell sie wachsen, wenn die Eingaben zunehmen, und nicht die genaue Zeit, die für die Ausführung der Aktion aufgewendet wird.

IMHO in den Big-O-Formeln sollten Sie besser keine komplexeren Gleichungen verwenden (Sie können sich einfach an die in der folgenden Grafik halten). Sie können jedoch auch andere präzisere Formeln verwenden (wie 3 ^ n, n ^ 3, .. .) aber mehr als das kann manchmal irreführend sein! Also besser so einfach wie möglich zu halten.

enter image description here

Ich möchte noch einmal betonen, dass wir hier keine genaue Formel für unseren Algorithmus erhalten wollen. Wir wollen nur zeigen, wie es wächst, wenn die Eingaben wachsen, und mit den anderen Algorithmen in diesem Sinne vergleichen. Andernfalls verwenden Sie besser verschiedene Methoden wie das Benchmarking.

Quelle