Frage Big O, wie berechnen / approximieren Sie es?


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

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

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


784
2017-08-06 10:18


Ursprung


Antworten:


Ich bin Professor Assistant an meiner lokalen Universität auf dem Kurs Datenstrukturen und Algorithmen. Ich werde mein Bestes geben, um es hier mit einfachen Worten zu erklären, aber sei gewarnt, dass dieses Thema meine Schüler ein paar Monate braucht, um es endlich zu begreifen. Weitere Informationen finden Sie im Kapitel 2 des Datenstrukturen und Algorithmen in Java Buch.


Es gibt kein mechanischer Vorgang das kann verwendet werden, um den BigOh zu bekommen.

Als "Kochbuch", um die BigOh Von einem Codeabschnitt müssen Sie zuerst erkennen, dass Sie eine mathematische Formel erstellen, um zu zählen, wie viele Berechnungsschritte bei einer Eingabe von einiger Größe ausgeführt werden.

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

Nehmen wir zum Beispiel an, Sie haben dieses Stück 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 zum Zählen der Rechenkomplexität von dieser Funktion:

Number_Of_Steps = f(N)

Also haben wir f(N)eine Funktion zum Zählen der Anzahl der Rechenschritte. 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 Parameter N nimmt die data.length Wert. Jetzt brauchen wir die eigentliche Definition der Funktion f(). Dies geschieht aus dem Quellcode, in dem jede interessante Zeile von 1 bis 4 nummeriert ist.

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

Wir werden die individuelle Anzahl der Schritte der Funktion hinzufügen, und weder die lokale Variablendeklaration noch die return - Anweisung hängen von der Größe der data Array.

Das bedeutet, dass in den Zeilen 1 und 4 jeweils C Schritte gezählt werden und die Funktion etwa so lautet:

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

Der nächste Teil ist, den Wert des zu definieren for Erklärung. Denken Sie daran, dass wir die Anzahl der Rechenschritte zählen, was bedeutet, dass der Körper der for Anweisung wird ausgeführt N mal. Das ist das Gleiche wie das Hinzufügen C, 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 der for Wird ausgeführt, Sie müssen es zählen, indem Sie sehen, was der Code tut. Um die Berechnungen zu vereinfachen, ignorieren wir die Variablen Initialisierung, Bedingung und Teile des for Erklärung.

Um das eigentliche BigOh zu bekommen, brauchen wir das Asymptotische Analyse der Funktion. Dies geschieht grob wie folgt:

  1. Entferne alle Konstanten C.
  2. Von f() bekommen das Polynom in seinem standard form.
  3. Teile die Polynombegriffe und sortiere sie nach der Wachstumsrate.
  4. Behalte den, der größer wird, wenn N Ansätze infinity.

Unser f() hat zwei Begriffe:

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

Alle wegnehmen C Konstanten und redundante Teile:

f(N) = 1 + N ^ 1

Seit dem letzten Semester ist derjenige, der größer wird, wenn f() nähert sich der Unendlichkeit (denken Sie an Grenzen) Dies ist das BigOh Argument, und die sum() Funktion hat einen BigOh von:

O(N)

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

Als Beispiel kann dieser Code einfach mit 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 müssen, ist die Reihenfolge der Ausführung von foo(). Während das Übliche sein soll O(1)Du musst deine Professoren danach fragen. O(1) bedeutet (fast, meistens) konstant Cunabhängig von der Größe N.

Das for Aussage über den Satz Nummer eins ist schwierig. Während der Index endet bei 2 * N, das Inkrement wird von zwei gemacht. Das bedeutet, dass der erste for wird nur ausgeführt N Schritte, und wir müssen die Zählung durch zwei teilen.

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

Die Satznummer zwei ist noch schwieriger, da es auf den Wert von hängt i. Schau mal: der Index i nimmt die Werte: 0, 2, 4, 6, 8, ..., 2 * N, und die zweite for ausgeführt werden: N mal die erste, N - 2 die zweite, N - 4 die dritte ... bis zur N / 2 Stufe, auf der die zweite for wird nie ausgeführt.

Auf Formel bedeutet das:

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

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

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

(Wir gehen davon aus, dass foo() ist O(1) und dauert C Schritte.)

Wir haben ein Problem hier: wann i nimmt den Wert an N / 2 + 1 nach oben endet die innere Summe bei einer negativen Zahl! Das ist unmöglich und falsch. Wir müssen die Summe in zwei Teile aufteilen, da sie den Dreh- und Angelpunkt bilden i dauert N / 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 Moment i > N / 2, das Innere for wird nicht ausgeführt, und wir nehmen eine konstante C-Ausführungskomplexität an seinem Körper an.

Jetzt können die Summierungen mit einigen Identitätsregeln vereinfacht werden:

  1. Summation (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 nach N) (w * C) = C * Summation (w von 1 nach N) (w) (C ist eine Konstante, unabhängig von w)
  4. Summation (w von 1 bis N) (w) = (N * (N + 1)) / 2

Etwas 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 der BigOh ist:

O(N²)

1390
2018-01-31 15:33



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.


190
2017-08-06 13:34



Wenn Sie wissen, wie Sie die Big O-Zeit für Ihr spezielles Problem berechnen können, ist es hilfreich, einige allgemeine Fälle zu kennen, die Ihnen dabei helfen können, Entscheidungen in Ihrem Algorithmus zu treffen.

Hier sind einige der häufigsten Fälle, aus gehoben http://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) - Finden eines Artikels in einem sortierten Array mit einer binären Suche

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

Auf2) - Multiplikation zweier n-stelliger Zahlen mit einem einfachen Algorithmus; Addieren von zwei n × n Matrizen; Blasensortierung oder Einfügesortierung

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

O (cn) - Finden der (genauen) Lösung für das Problem des reisenden Verkäufers mittels dynamischer Programmierung; Ermitteln, ob zwei logische Anweisungen mit roher Gewalt gleichwertig sind

O (n!) - Das Problem des reisenden Verkäufers durch Brute-Force-Suche lösen

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


87
2017-09-05 19:09



Kleine Erinnerung: die big O Notation wird verwendet, um zu bezeichnen asymptotisch Komplexität (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 (n2), der schnellste ist nicht immer der erste (obwohl es immer einen Wert von n gibt, so dass bei Problemen der Größe> n der erste Algorithmus der schnellste ist).

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 du sagst, premature optimisation is the root of all evilund (wenn möglich) Profilierung sollte wirklich immer verwendet werden, wenn Code optimiert wird. Es kann Ihnen sogar helfen, die Komplexität Ihrer Algorithmen zu bestimmen.


40
2017-08-23 20:43



Wenn ich die Antworten hier sehe, denke ich, können wir schlussfolgern, dass die meisten von uns tatsächlich die Reihenfolge des Algorithmus annähern schauend und benutze den gesunden Menschenverstand, anstatt ihn zu berechnen, zum Beispiel mit dem Master-Methode wie wir an der Universität gedacht haben. Damit muss ich hinzufügen, dass uns sogar der Professor (später) dazu ermutigt hat denken darüber, anstatt es nur zu berechnen.

Ich möchte auch hinzufügen, wie es gemacht wird rekursive Funktionen:

Angenommen wir haben eine Funktion wie (Schemacode):

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

welches rekursiv die Fakultät der gegebenen Zahl berechnet.

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

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

Als nächstes versuchen und dies für die Anzahl der rekursiven Aufrufe. In diesem Fall haben wir n-1 rekursive Aufrufe.

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

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

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


Peter, Antworten Ihre erhobenen Probleme; die Methode, die ich hier beschreibe, geht das eigentlich gut an. Aber bedenke, dass dies immer noch eine ist Annäherung und nicht eine vollständige mathematisch korrekte Antwort. Die hier beschriebene Methode ist auch eine der Methoden, die wir an der Universität gelernt haben, und wenn ich mich richtig erinnere, wurde sie für weit fortgeschrittenere Algorithmen verwendet als die Fakultät, die ich in diesem Beispiel verwendet habe.
Natürlich hängt alles davon ab, wie gut Sie die Laufzeit des Rumpfes der Funktion und die Anzahl der rekursiven Aufrufe schätzen können, aber das gilt auch für die anderen Methoden.


26
2017-08-07 08:10



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 (n2/ 4 + n / 2) = O (n2/ 4) = O (n2)

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 (N2) <O (Nk) <O (en) <O (n!)


25
2018-01-31 13:30



Ich denke darüber nach Informationen. 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 es Ihnen geben wird. Zum Beispiel, wenn ein Programm einen Entscheidungspunkt mit zwei Zweigen enthält, ist es die Entropie ist die Summe der Wahrscheinlichkeit jedes Zweigs mal das Protokoll2 der umgekehrten Wahrscheinlichkeit dieser Verzweigung. So viel lernen Sie, wenn Sie diese Entscheidung treffen.

Zum Beispiel if Aussage 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. So seine Entropie ist 1 Bit.

Angenommen, Sie suchen nach einer Tabelle mit N Elementen, z. B. N = 1024. Das ist ein 10-Bit-Problem, weil log (1024) = 10 Bits. Wenn Sie also IF-Anweisungen mit ähnlich wahrscheinlichen Ergebnissen suchen können, sollten Sie 10 Entscheidungen treffen.

Das bekommen Sie mit der binären Suche.

Angenommen, Sie führen eine lineare Suche durch. Sie betrachten das erste Element und fragen, ob es das ist, was Sie wollen. Die Wahrscheinlichkeiten sind 1/1024, die es ist, und 1023/1024, die es nicht ist. Die Entropie dieser Entscheidung ist 1/1024 * log (1024/1) + 1023/1024 * log (1024/1023) = 1/1024 * 10 + 1023/1024 * etwa 0 = etwa 0,01 Bit. Du hast sehr wenig gelernt! Die zweite Entscheidung ist nicht viel besser. Deshalb ist die lineare Suche so langsam. In der Tat ist es exponentiell in der Anzahl der Bits, die Sie lernen müssen.

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 zum 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 ist 1/1024 * 10 mal 1024 Ergebnisse oder 10 Bits Entropie für diese eine Indexierungsoperation. Deshalb ist die Indexsuche 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, wohin das Element in der Liste geht, und es dann zur Liste hinzufügen. Die Sortierung dauert also ungefähr N mal die Anzahl der Schritte der zugrunde liegenden Suche.

Sortierungen, die auf binären Entscheidungen basieren, die ungefähr gleich wahrscheinlich Ergebnisse haben, benötigen alle ungefähr O (N log N) Schritte. Ein O (N) -Sortieralgorithmus ist möglich, wenn er auf der Indexsuche basiert.

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


19
2018-03-10 13:24



Fangen wir von vorne an.

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

  1. Arithmetische Operationen (z.B. + oder%).
  2. Logische Operationen (z.B. &&).
  3. Vergleichsoperationen (z.B. <=)
  4. Strukturzugriffsoperationen (z. B. Array-Indizierung wie A [i] oder Zeigerfolgen mit 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 Konsequenz können verschiedene Arten von Anweisungen in C ausgeführt werden O(1) Zeit, das heißt, in einer konstanten Zeit unabhängig von der Eingabe. 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 wo Ausdruck enthält keinen Funktionsaufruf.

In C werden viele for-Schleifen gebildet, indem eine Indexvariable auf einen Wert und initialisiert wird Inkrementieren dieser Variable jedes Mal um die Schleife um 1. Die for-Schleife endet wann Der Index erreicht eine Grenze. 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 jedes Mal um die Schleife und die Iterationen um 1 Hör auf, wenn ich n - 1 erreiche.

Konzentrieren Sie sich im Moment jedoch auf die einfache Form der For-Schleife, wobei die Die Differenz zwischen dem End- und Initialwert geteilt durch den Betrag, um den die Indexvariable inkrementiert 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 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, ist n - 1 der höchste Wert, der von i erreicht wird (d. h. wenn i erreicht n-1, die Schleife stoppt und es findet keine Iteration mit i = n-1 statt, und 1 wird hinzugefügt zu i bei jeder Iteration der Schleife.

Im einfachsten Fall, wo die im Schleifenkörper verbrachte Zeit für jeden gleich ist Iteration, wir können die große obere Grenze für den Körper mit der Anzahl von multiplizieren mal um die Schleife. Genau genommen müssen wir dann Füge O (1) Zeit hinzu, um zu initialisieren der Schleifenindex und O (1) Zeit für den ersten Vergleich des Schleifenindex mit dem Grenze, weil wir noch einmal testen, als wir um die Schleife gehen. Jedoch, es sei denn Es ist möglich, die Schleifen-Null-Zeiten auszuführen, die Zeit, um die Schleife zu initialisieren und zu testen Das Limit einmal ist ein niederwertiger Ausdruck, 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 das Linie 1) dauert O(1) Zeit. Klar, wir gehen n-mal um die Schleife, als wir können durch Subtrahieren der unteren Grenze von der oberen Grenze, die auf der Linie gefunden wird, bestimmen (1) und dann addiere 1. Da der Körper, Linie (2), O (1) Zeit braucht, können wir die. Vernachlässigen Zeit zum Inkrementieren von j und die Zeit zum Vergleichen von j mit n, wobei beide auch O (1) sind. Somit ist die Laufzeit der Zeilen (1) und (2) die Produkt von n und O (1), welches ist O(n).

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

(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 erhöhen und zu testen, ob i <n in ist jede Iteration, mit der Schlussfolgerung, 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 Ich nehme ebenfalls O (1) Zeit und kann vernachlässigt werden. Schließlich beobachten wir, dass wir gehen um die äußere Schleife n mal, wobei für jede Iteration eine O (n) Zeit genommen wird, was eine Summe ergibt O(n^2) Laufzeit.


Ein praktischeres Beispiel.

enter image description here


17
2018-02-02 15:30



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

Dies hat mehrere Vorteile gegenüber dem bloßen Studium des Codes. Zum einen können Sie sehen, ob Sie in dem Bereich sind, in dem die Laufzeit sich ihrer asymptotischen Reihenfolge nähert. Möglicherweise stellen Sie auch fest, dass Code, den Sie für Ordnung O (x) hielten, in Wirklichkeit Ordnung O (x ^ 2) ist, zum Beispiel wegen der Zeit, die in Bibliotheksaufrufen verbracht wurde.


11
2017-12-11 20:49