Big O, wie tun Sie berechnen/approximieren Sie es?

https://stackoverflow.com/questions/3255

08-06-2019
|

Frage

Die meisten Menschen mit einem Abschluss in CS wird sicherlich wissen, was Big O steht für.Es hilft uns, zu Messen, wie (in)effizient ein Algorithmus wirklich ist und wenn Sie wissen, in zu welcher Kategorie das problem Sie versuchen zu lösen, legt in können Sie herausfinden, ob es immer noch möglich, um squeeze-out die etwas mehr Leistung.¹

Aber ich bin neugierig, wie Sie berechnen oder approximieren Sie die Komplexität der algorithmen?

¹ _{aber wie Sie sagen, übertreiben Sie es nicht, vorzeitige Optimierung ist die Wurzel allen übels, und Optimierung ohne begründeten Anlass sollte, verdient diesen Namen auch.}

Lösung

Ich werde mein bestes tun, um es zu erklären, hier auf einfachen Bedingungen, aber seien Sie gewarnt, dass dieses Thema nimmt meine Schüler ein paar Monate, bis endlich begreifen.Weitere Informationen finden Sie auf den in Kapitel 2 des Datenstrukturen und Algorithmen in Java Buch.

Es gibt keine mechanische Verfahren kann verwendet werden, um die BigOh.

Als ein "Kochbuch", um die BigOh aus einem Stück von code, Sie müssen zuerst erkennen, dass Sie sind erstellen eine mathematische Formel, um zu zählen, wie viele Schritte der Berechnungen ausgeführt werden, die angesichts einer Eingabe von gewisser Größe.

Der Zweck ist einfach:vergleichen algorithmen aus theoretischer Sicht, ohne die Notwendigkeit, um den code auszuführen.Die kleinere die Anzahl der Schritte, die schneller der Algorithmus.

Für Beispiel, lassen Sie sagen, 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, und wir möchten eine Formel erstellen, um zu zählen computational Komplexität der Funktion:

Number_Of_Steps = f(N)

So haben wir f(N), eine Funktion zum zählen der Anzahl der rechnerische Schritte.Die Eingabe der Funktion wird die Größe der Struktur zu verarbeiten.Es bedeutet, dass diese Funktion aufgerufen wird, wie zum Beispiel:

Number_Of_Steps = f(data.length)

Der parameter N nimmt die data.length Wert.Jetzt müssen wir die eigentliche definition der Funktion f().Dies erfolgt aus dem source-code, in dem jeder interessante Zeile ist nummeriert von 1 bis 4.

Es gibt viele Methoden zur Berechnung der BigOh.Von diesem Punkt an werden wir davon ausgehen, dass jeder Satz, der hängt nicht von der Größe der Eingabe von Daten nimmt einen Konstanten C Anzahl computational Schritte.

Gehen wir zu fügen Sie die individuelle Anzahl der Schritte, die von der Funktion, und weder die lokalen Variablen-Deklaration noch die return-Anweisung hängt ab von der Größe der data array.

Das bedeutet, dass die Linien 1 und 4 C Anzahl der Schritte, die Funktion ist etwas wie dieses:

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

Der nächste Teil ist, definieren Sie den Wert der for Anweisung.Denken Sie daran, dass wir zählen die Anzahl der rechnerische Schritte, was bedeutet, dass der Körper des for - Anweisung ausgeführt N mal.Das ist das gleiche wie das hinzufügen von C, N Zeiten:

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

Es gibt keine mechanische Regel, um zu zählen, wie viele Male der Körper des for ausgeführt wird, müssen Sie es zählen, indem Sie betrachten, was bedeutet der code tun.Um die Rechnungen zu vereinfachen, wir ignorieren die variable Initialisierung, Bedingung, und die Schrittweite Teile das for Anweisung.

Um die tatsächliche BigOh müssen wir die Asymptotische Analyse der Funktion.Das ist in etwa so gemacht wie diese:

Take-away alle Konstanten C.
Von f() Holen Sie sich die polynomium in seiner standard form.
Teilen Sie die Bedingungen der polynomium und Sortieren Sie durch die rate des Wachstums.
Halten Sie die eine, die wächst, wenn N Ansätze infinity.

Unsere f() zwei Bedingungen:

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

Nehmen Sie alle C Konstanten und redundante Teile:

f(N) = 1 + N ^ 1

Da der Letzte term ist die eine, die wächst, wenn f() gegen unendlich (man denke an Grenzen) dies ist die BigOh argument, und die sum() die Funktion hat eine BigOh von:

O(N)

Es gibt ein paar tricks, um lösen einige knifflige lieben:verwenden Summen Wann immer Sie können.

Als ein Beispiel, dieser code kann leicht gelöst werden mit Summen:

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

Das erste, was Sie brauchen, zu Fragen ist die Reihenfolge der Ausführung foo().Während die gewöhnlichen sein O(1), Sie müssen Fragen Sie Ihre Professoren über es. O(1) Mittel (beinahe, fast) Konstante C, unabhängig von der Größe N.

Die for Anweisung für den Satz, Nummer eins ist heikel.Während der index endet am 2 * N, die Inkrement erfolgt durch zwei.Das bedeutet, dass die erste for wird nur ausgeführt, N Schritte, und wir müssen teilen die Zählung von zwei.

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

Der Satz-Nummer zwei ist noch schwieriger, da es hängt vom Wert von i.Werfen Sie einen Blick:der index i nimmt die Werte:0, 2, 4, 6, 8, ..., 2 * N, und die zweite for Ausführung:N Zeiten des ersten N - 2 ist die zweite, N - 4 die Dritte...bis N / 2 von Bühne, auf der sich die zweite for nie wird Sie ausgeführt.

Mit der Formel,, dass bedeutet:

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

Wieder, wir sind zu zählen die Anzahl der Schritte.Und per definition jede Summe sollte beginnen immer mit einer, und am Ende in eine Nummer größer-oder-gleich als eine.

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 nimmt C Schritte.)

Wir haben ein problem hier:wenn i nimmt den Wert N / 2 + 1 nach oben, die innere Summe enden bei einer negativen Zahl!Das ist unmöglich und falsch.Wir müssen uns aufteilen der Summe in zwei, wobei der Dreh-und Angelpunkt der moment i nimmt 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 der entscheidende moment i > N / 2, die innere for wird nicht ausgeführt, und wir sind der Annahme einer Konstanten C Ausführung Komplexität auf seinen Körper.

Jetzt die Summen werden vereinfacht mit einigen Identität Regeln:

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

Die Anwendung der algebra:

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 die BigOh ist:

O(N²)

Andere Tipps

Big O gibt die Obere Schranke für die Zeitkomplexität eines Algorithmus.Es ist in der Regel verwendet in Verbindung mit der Verarbeitung von Daten-Sätzen (Listen), sondern anderweitig eingesetzt werden kann.

Ein paar Beispiele, wie es in C-code.

Sagen wir, wir haben ein array von n Elementen

int array[n];

Wenn wir wollten, um Zugriff auf das erste element des Arrays wäre dies O(1) da ist es egal, wie groß das array ist, dauert es immer die gleiche Konstante Zeit, um das erste Element.

x = array[0];

Wenn wir uns finden wollten, die eine Zahl in die Liste:

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

Dies wäre O(n) da am meisten, die wir sehen müssten, um durch die gesamte Liste finden Sie unsere Nummer.Die Big-O ist immer noch O(n) - auch wenn wir finden, könnten wir die Anzahl unserer ersten versuche und führen Sie durch die Schlaufe einmal, da die Big-O-beschreibt die Obere Grenze für einen Algorithmus (omega ist für die untere Grenze und theta ist für eng-gebunden ist).

Wenn wir zu nested loops:

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

Dies ist O(n^2), da für jeden Durchlauf der äußeren Schleife ( O(n) ) haben wir, zu gehen durch die gesamte Liste erneut, damit die n, multiplizieren, indem Sie uns mit n squared.

Dies ist kaum an der Oberfläche gekratzt, aber wenn Sie die Analyse komplexer algorithmen, komplexe Mathematik mit Beweise ins Spiel kommt.Hoffe, dies macht Sie mit den Grundlagen, mindestens aber.

Während zu wissen, wie um herauszufinden, die Big O Zeit für Ihr spezielles problem ist nützlich, zu wissen, einige Allgemeine Fälle kann gehen einen langen Weg zu helfen, Sie zu machen Entscheidungen in Ihrem Algorithmus.

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

O(1) - der Bestimmung, ob eine Zahl gerade oder ungerade ist;mit eine Konstante Größe lookup-table oder hash-Tabelle

O(logn) - Suche nach einem Element in einem sortierten array mit einer binären Suche

O(n) - Suche nach einem Element in einer unsortierten Liste;hinzufügen von zwei n-stellige zahlen

O(n²) - Die Multiplikation von zwei n-stelligen zahlen, die durch einen einfachen Algorithmus;hinzufügen von zwei n×n Matrizen;bubble-sort oder insertion sort

O(n³) - Multiplikation zweier n×n Matrizen durch einfachen Algorithmus

O(cⁿ) - Finden, das (exakte) Lösung für das traveling salesman problem using dynamic programming;bestimmen, ob zwei logische Aussagen sind äquivalent: brute-force

O(n!) - Die Lösung des traveling salesman problem via brute-force-Suche

O(nⁿ) - Oft verwendet, anstelle von O(n!) die Ableitung einfacher Formeln für asymptotische Komplexität

Kleine Erinnerung:die big O - notation verwendet, um anzugeben, asymptotische Komplexität (, dass ist, wenn die Größe des Problems wächst bis unendlich), und es verbirgt sich eine Konstante.

Dies bedeutet, dass zwischen ein Algorithmus in O(n) und O(n²), der Schnellste ist nicht immer die erste (aber es gibt immer einen Wert von n, so dass für die Probleme der Größe >n, die first-Algorithmus ist der Schnellste).

Beachten Sie, dass die versteckte Konstante hängt sehr stark von der Umsetzung!

Auch, in einigen Fällen, die Laufzeit ist nicht eine deterministische Funktion der Größe n der Eingang.Nehmen Sie die Sortierung mithilfe von quick sort, zum Beispiel:die benötigte Zeit für das Sortieren eines Arrays von n Elementen ist nicht konstant, sondern hängt von der Start-Konfiguration des Arrays.

Es gibt unterschiedliche Zeit-Komplexität:

Schlimmsten Fall (in der Regel die einfachste, um herauszufinden,, wenn auch nicht immer sehr aussagekräftig)
Durchschnittlicher Fall (in der Regel viel schwieriger, herauszufinden,...)
...

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

Wie Sie sagen, premature optimisation is the root of all evil, und (wenn möglich) profiling wirklich sollte immer verwendet werden, wenn die Optimierung von code.Es kann auch Ihnen helfen, bestimmen die Komplexität der algorithmen.

Sehen Sie die Antworten hier ich denke, wir können feststellen, dass die meisten von uns haben in der Tat die Ungefähre Reihenfolge der Algorithmus von suchen an und verwenden Sie gesunden Menschenverstand, anstatt ihn zu berechnen, zum Beispiel, die master-Methode als wir gedacht waren, an der Universität.Mit, dass sagte, ich muss hinzufügen, dass auch der professor ermutigte uns (später) tatsächlich denken über es statt einfach nur Berechnung.

Auch möchte ich hinzufügen, wie es gemacht wird für rekursive Funktionen:

angenommen, wir haben eine Funktion wie (scheme-code):

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

rekursiv berechnet die Fakultät der Zahl angegeben.

Der erste Schritt ist, zu versuchen und zu bestimmen, die Leistung charakteristisch für die Körper der Funktion, nur in diesem Fall, nichts besonderes geschieht im Körper, der nur eine Multiplikation (oder die Rückkehr der Wert 1).

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

Neben versuchen und zu bestimmen, das für die Anzahl der rekursiven Aufrufe.In diesem Fall haben wir n-1 rekursive Aufrufe.

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

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

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

Peter, Antwort Ihr aufgeworfenen Fragen; die Methode, die ich hier beschreibe tatsächlich behandelt dies sehr gut.Aber Bedenken Sie, dass dies immer noch ein Annäherung und nicht auf einen vollständigen mathematisch korrekte Antwort.Die hier beschriebene Methode ist auch eine der Methoden, die wir waren, lehrte an der Universität, und wenn ich mich richtig erinnere, verwendet wurde, für weit mehr erweiterte algorithmen, als der Fakt, die ich in diesem Beispiel verwendet.
Natürlich ist es hängt alles davon ab, wie gut können Sie schätzen die Laufzeit der Körper der Funktion und die Anzahl der rekursiven Aufrufe, aber das ist ebenso wahr, für die andere Methoden.

Wenn Sie Ihre Kosten ist ein Polynom, nur halten die höchsten um-Begriff, ohne Multiplikator.E. g.:

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

Dies funktioniert nicht für die unendlichen Serie, wohlgemerkt.Es gibt kein einziges Rezept für den Allgemeinen Fall, aber für einige häufige Fälle, die folgenden Ungleichungen gelten:

O(log N) < O(N) < O(N anmelden N) < O(N²) < O(N^k) < O(eⁿ) < O(n!)

Ich denke, über es in Bezug auf die Informationen.Jedes problem besteht aus lernen, eine bestimmte Anzahl von bits.

Ihre grundlegende Werkzeug ist das Konzept der Entscheidungspunkte und Ihre Entropie.Die Entropie einer Entscheidung ist der Durchschnitt hat, wird es Euch geben.Zum Beispiel, wenn ein Programm enthält eine Entscheidung mit zwei Niederlassungen, die Entropie ist die Summe der Wahrscheinlichkeit von jedem Zweig mal die log₂ der inversen Wahrscheinlichkeit, dass Zweig.Das ist, wie viel Sie lernen durch die Ausführung der Entscheidung.

Für Beispiel, eine if Erklärung, dass zwei Zweige, die beide gleich wahrscheinlich sind, hat eine Entropie von 1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1.So ist seine Entropie 1 bit.

Angenommen, Sie suchen eine Tabelle von N Elementen, wie N=1024.Das ist ein 10-bit-problem, weil log(1024) = 10 bits.Also, wenn Sie suchen Sie es mit IF-Anweisungen, die wahrscheinlich gleich Ergebnisse, sollte es dauern, 10 Entscheidungen.

Das ist, was Sie erhalten mit binären Suche.

Angenommen, Sie sind dabei lineare Suche.Sie schauen auf das erste element und Fragen, ob es die, die Sie wollen.Die Wahrscheinlichkeiten sind 1/1024, dass es ist, und 1023/1024, dass es nicht so ist.Die Entropie, die Entscheidung ist 1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * 0 = über .01 bit.Sie haben gelernt, sehr wenig!Die zweite Entscheidung ist nicht viel besser.Das ist, warum lineare Suche so langsam.In der Tat, es ist exponentiell in der Anzahl der bits Sie brauchen, um zu lernen.

Angenommen, Sie tun indizieren.Angenommen, die Tabelle ist vorsortiert in eine Menge von Klassen, und verwenden Sie einige der bits im Schlüssel zum index direkt auf den Tabelleneintrag.Wenn es gibt 1024 bins, die Entropie ist 1/1024 * log(1024) + 1/1024 * log(1024) + ...für alle 1024 mögliche Ergebnisse.Dies ist 1/1024 * 10-mal 1024 Ergebnisse, oder 10 bits der Entropie, die man indexing operation.Das ist der Grund, warum die Indizierung Suche schnell.

Jetzt denken Sie über die Sortierung.Sie haben N Elemente, und Sie haben eine Liste.Für jedes Einzelteil, Sie haben zu suchen, wohin der Artikel geht in der Liste, und fügen Sie es der Liste.So Sortieren dauert etwa N-mal die Anzahl der Schritte von der zugrunde liegenden suchen.

So sortiert, basierend auf binären Entscheidungen, die in etwa gleich wahrscheinlich sind alle Ergebnisse dauert etwa O(N log N) Schritte.Ein O(N) Sortieren Algorithmus ist möglich, wenn er basiert auf der Indizierung Suche.

Ich habe herausgefunden, dass fast alle Algorithmische performance-Probleme können angeschaut werden auf diese Weise.

Fangen wir von Anfang an.

Erste von alle, den Grundsatz akzeptieren, dass gewisse einfache Operationen auf den Daten getan werden kann O(1) Zeit,, dass ist, in der Zeit, unabhängig von der Größe der Eingabe.Diese primitiven Operationen in C aus

Arithmetische Operationen (z.B.+ oder %).
Logische Operationen (z.B., &&).
Vergleich-Operationen (z.B., <=).
Struktur Zugriff auf Operationen (z.B.array-Indizierung wie Ein[i] oder Zeiger fol- lowing mit dem - > - operator).
Einfache Zuweisung wie kopieren Sie einen Wert in eine variable.
Aufrufe von Bibliotheksfunktionen (z.B., scanf, printf).

Die Begründung für dieses Prinzip erfordert eine detaillierte Studie über die Maschine Anweisungen, die (primitiv -) Schritte eines typischen computer.Jede der beschriebenen Vorgänge können durchgeführt werden, die mit einigen kleinen Anzahl der Maschine, die Anleitung;oft nur aus einer oder zwei Anweisungen benötigt.Als Folge werden mehrere Arten von Anweisungen in C ausgeführt werden kann O(1) Zeit,, dass ist, in der einige Konstanten Menge von Zeit, unabhängig von der Eingabe.Diese einfache gehören

Zuweisung-Anweisungen, die nicht mit der Funktion fordert in Ihren Ausdrücken.
Lesen Sie Aussagen.
Write-Anweisungen, die nicht erfordern Funktionsaufrufe zu bewerten Argumente.
Der Sprung-Anweisungen break, continue, goto und return-Ausdruck, wo Ausdruck nicht enthält einen Aufruf der Funktion.

In C, viele for-Schleifen werden gebildet durch die Initialisierung der index-variable auf Wert und Inkrementieren Sie die variable um 1 jedes mal in der Schleife.Die for-Schleife endet, wenn der index erreicht Grenzwert.Für 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 index-variable, die ich.Es erhöht i um 1 jedes mal in der Schleife, und die Iterationen stoppen, wenn ich erreicht, n − 1.

Aber für den moment, konzentrieren sich auf die einfache form der for-Schleife, wo die Unterschied zwischen dem letzten und ersten Werte, dividiert durch den Betrag, mit dem die index-variable inkrementiert, sagt uns, wie oft wir gehen, um den loop.Zählen ist genaue, es sei denn, es gibt Möglichkeiten, beenden Sie die Schleife über eine Sprung-Anweisung;es ist eine Obere Schranke für die Anzahl der Iterationen in jedem Fall.

Für Beispiel, die for-Schleife iteriert ((n − 1) − 0)/1 = n − 1 times, ab 0 ist der Anfangswert von i, n − 1 ist der höchste Wert erreicht, indem ich (D. H., wenn ich erreicht n−1, wird die Schleife beendet, und keine iteration tritt mit i = n−1, und 1 ist Hinzugefügt i bei jeder iteration der Schleife.

Im einfachsten Fall, wo die Zeit in der Schleife ist das gleiche für jede iteration multiplizieren wir die big-oh-Obergrenze für den Körper durch die Anzahl der mal um die Schleife.Streng genommen müssen wir uns dann fügen Sie O(1) Zeit zum initialisieren die loop-index und O(1) Zeit für den ersten Vergleich in der Schleife mit dem index limit,, weil wir testen Sie noch einmal, als wir gehen, um die Schlaufe.Jedoch, es sei denn, es ist möglich, die Ausführung der Schleife null mal, die Zeit, die zum initialisieren der loop und test die Grenze einmal ist ein low-Auftrag Begriff, die können gelöscht werden durch die Summierung der Regel.

Nun betrachten Sie dieses Beispiel:

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

Wir wissen, dass line (1) nimmt O(1) Zeit.Klar, wir gehen um die Schleife n-mal, so können wir bestimmen, indem man die untere Grenze von der oberen Grenze gefunden auf-Linie (1) und dann hinzufügen 1.Da der Körper, Zeile (2), O(1) Zeit können wir vernachlässigen die Zeit zu Inkrement-j und die Zeit zum vergleichen von j mit n, beide ebenfalls in O(1).So, die Fahrzeit der Linien (1) und (2) die Produkt von n und O(1), die O(n).

Ebenso können wir verpflichtet, über die Laufzeit der äußeren Schleife bestehend aus Linien (2) bis (4), die

(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) in O(n) Zeit.So können wir vernachlässigen, die O(1) Zeit hochgezählt ich und um zu testen, ob ich < n in jede iteration, die Feststellung, dass jede iteration der äußeren Schleife in O(n) Zeit.

Die Initialisierung i = 0 der äußeren Schleife und die (n + 1)st-test der Bedingung ich < n ebenso nehmen O(1) Zeit und kann vernachlässigt werden.Schließlich beobachten wir, dass wir gehen um die äußere Schleife n-mal, wobei O(n) Zeit, die für jede iteration, was insgesamt O(n^2) Laufzeit.

Beispiel aus der Praxis.

enter image description here

Wenn Sie möchten, schätzen die Reihenfolge des Codes empirisch eher als durch die Analyse der code, Sie könnte stick in eine Reihe von zunehmenden Werten von n und mal deinen code.Zeichnen Sie Ihre Zeiten auf ein log-Skala.Wenn der code O(x^n), sollten die Werte fallen auf eine Linie der Steigung n.

Dies hat mehrere Vorteile gegenüber nur den Quellcode zu untersuchen.Für eine Sache, können Sie sehen, ob Sie in den Bereich, wo die Zeit, die Ansätze seines asymptotischen Ordnung.Auch, Sie können feststellen, dass einige code, den Sie dachte, war O(x) ist O(x^2), da zum Beispiel die Zeit, in der Bibliothek anrufen.

Im Grunde ist die Sache, die Feldfrüchte bis zu 90% der Zeit, ist nur die Analyse von Schleifen.Haben Sie Einzel -, Doppel -, dreifach verschachtelte Schleifen?Sie haben O(n), O(n^2), O(n^3) Zeit läuft.

Sehr selten (es sei denn, Sie werden schriftlich eine Plattform mit einem umfangreichen Basis-Bibliothek (wie beispielsweise das .NET BCL, oder C++, STL), begegnen Sie alles, was schwieriger ist, als nur die Suche an Ihre Schleifen (for-Anweisungen, while, goto, etc...)

Brechen Sie den Algorithmus in Stücke kennen Sie die big O-notation für, und verbinden sich durch die große O Operatoren.Das ist die einzige Möglichkeit, die ich kenne.

Für mehr Informationen, überprüfen Sie die Wikipedia-Seite auf das Thema.

Big O-notation ist nützlich, weil es ist einfach, mit zu arbeiten und versteckt sich unnötige Komplikationen und details (für einige definition von unnötigen).Eine nette Art zu arbeiten heraus, die Komplexität der Teile und herrsche-algorithmen ist der Baum Methode.Angenommen, Sie haben eine version von quicksort mit dem median-Verfahren, so dass Sie teilen Sie das array in perfekt ausgewogene subarrays jedes mal.

Jetzt bauen Sie eine Struktur entsprechend den arrays mit dem Sie arbeiten.An der Wurzel haben Sie das ursprüngliche array, der Stamm hat zwei Kinder, die der subarrays.Wiederholen Sie dies, bis Sie haben Einzel-element-arrays an der Unterseite.

Da finden wir den median in O(n) Zeit und teilen Sie die Reihe in zwei Teile, die in O(n) Zeit, die Arbeit an jedem Knoten ist O(k) wobei k die Größe des Arrays.Jede Ebene der Struktur enthält (höchstens) des gesamten Arrays, also die Arbeit pro Stufe ist O(n) (die Größe des subarrays summieren sich zu n, und da haben wir A(k) pro Ebene können wir hinzufügen aus).Es gibt nur log(n) Ebenen in der Struktur, da jedes mal, wenn wir halbieren die Eingabe.

Daher können wir die Obere Schranke der Menge der Arbeit von O(n*log(n)).

Jedoch, Big O verbirgt einige details, die wir manchmal nicht ignorieren können.Betrachten Berechnung der Fibonacci-Sequenz mit

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

und können annehmen, dass a und b sind BigIntegers in Java oder etwas, das Sie behandeln können beliebig große zahlen.Die meisten Menschen würden sagen, dies ist eine O(n) Algorithmus, der ohne mit der Wimper zu zucken.Die Argumentation ist, dass Sie haben n Iterationen der for-Schleife und O(1) - arbeiten Seite der Schleife.

Aber Fibonacci-zahlen sind groß, die n-te Fibonacci-Zahl ist exponentiell in n, so einfach speichern Sie den Auftrag von n bytes.Performing Zusatz mit großen Ganzzahlen dauert O(n) Aufwand.Also der Gesamtmenge der Arbeit, die in dieses Verfahren ist

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

Damit dieser Algorithmus läuft in quadradic Zeit!

Vertrautheit mit den algorithmen/Datenstrukturen, die ich verwenden und/oder schnellen Blick Analyse der iteration verschachteln.Die Schwierigkeit ist, wenn Sie anrufen, eine Bibliothek-Funktion, möglicherweise mehrfach - oft können Sie unsicher sein, ob Sie die Funktion aufrufen, unnötig an Zeiten oder welche Implementierung Sie verwenden.Vielleicht library-Funktionen sollte eine Komplexität/Effizienz Messen, ob die Big-O-oder eine andere Metrik, die in der Dokumentation oder sogar IntelliSense.

Weniger hilfreich in der Regel, denke ich, aber der Vollständigkeit halber gibt es auch eine Big Omega Ω, definiert einen unteren Grenzwert ein Algorithmus Komplexität, und eine Große Theta Θ, definiert , die sowohl eine Obere und untere Schranke.

Wie in "wie berechnen Sie die" Big-O, dieser ist Teil des Komplexitätstheorie.Für einige (viele) Besondere Fälle, Sie kann in der Lage zu kommen mit einigen einfachen Heuristiken (wie Multiplikation Schleife zählt für nested loops), esp.wenn alle Sie wollen, ist jede Obere Schranke Schätzung, und Sie tun nicht Geist, wenn es ist zu pessimistisch - was ich denke, ist wahrscheinlich das, was Ihre Frage ist.

Wenn Sie wirklich wollen, zu beantworten Ihre Frage für alle Algorithmus-das beste, was Sie tun können, ist das anwenden der Theorie.Neben vereinfachend "worst-case" - Analyse, die ich gefunden habe Amortized analysis sehr nützlich in der Praxis.

Für den 1. Fall, wird die innere Schleife Durchlaufen wird n-i mal, so dass die Gesamtzahl der Hinrichtungen ist die Summe für i Los von 0 zu n-1 (weil geringerer als, nicht niedriger als oder gleich) der n-i.Sie erhalten schließlich n*(n + 1) / 2, so O(n²/2) = O(n²).

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

Zusätzlich zur Verwendung der master-Methode (oder eine seiner Spezialisierungen), ich Teste meine algorithmen experimentell.Dies kann nicht beweisen , dass eine bestimmte Komplexität der Klasse ist erreicht, es kann aber die Gewissheit, dass die mathematische Analyse geeignet ist.Zu helfen, mit dieser Gewissheit, ich verwende die code-coverage-tools in Verbindung mit meiner Experimente, um sicherzustellen, dass ich die Ausübung der alle Fälle.

Als ein sehr einfaches Beispiel, sagen, Sie wollten eine Plausibilitätsprüfung auf die Geschwindigkeit der .NET framework die Liste zu Sortieren.Könnten Sie etwas schreiben wie die folgenden, dann analysieren Sie die Ergebnisse in Excel, um sicherzustellen, dass Sie nicht länger als ein n*log(n) - Kurve.

In diesem Beispiel habe ich Messen die Anzahl der Vergleiche, aber es ist auch ratsam zu prüfen, die tatsächliche Zeitaufwand für die einzelnen sample-Größe.Aber dann müssen Sie noch vorsichtiger sein, dass Sie nur Messen des Algorithmus und nicht darunter Artefakte aus dem test-Infrastruktur.

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);

Vergessen Sie nicht auch Platz Komplexitäten, kann auch ein Grund zur Besorgnis, wenn man beschränkt Speicher-Ressourcen.So zum Beispiel können Sie hören, wie jemand, die eine Konstante Raum-Algorithmus der im Grunde eine Art zu sagen, dass der Platz durch den Algorithmus hängt nicht von Faktoren der code drin.

Manchmal kann die Komplexität kommen Sie aus, wie oft so etwas, wie oft eine Schleife ausgeführt, wie Häufig Speicher reserviert und so weiter ist ein weiterer Teil um diese Frage zu beantworten.

Schließlich, big O kann verwendet werden, für die im schlimmsten Fall, im besten Fall, und Abschreibungen auf Fälle, in denen in der Regel ist es der Schlimmste Fall, die ist verwendet für die Beschreibung, wie schlecht ein Algorithmus sein kann.

Was oft übersehen wird ist die erwartet Verhalten der algorithmen. Es ändert nicht den Big-O von algorithmen, aber Sie tut beziehen sich auf die Anweisung "vorzeitige Optimierung...."

Das erwartete Verhalten Ihres Algorithmus ist -- sehr verdummt-wie schnell können Sie erwarten, dass Ihr Algorithmus, um die Arbeit auf Daten aus, die Sie sind wahrscheinlich zu sehen.

Zum Beispiel, wenn Sie auf der Suche nach einem Wert in einer Liste, es ist O(n), aber wenn Sie wissen, dass die meisten Listen, die Sie sehen müssen Ihren Wert für die vordere, typische Verhalten des Algorithmus ist schneller.

Wirklich nail it down, Sie müssen in der Lage sein, zu beschreiben die Wahrscheinlichkeitsverteilung von Ihrem "input space" (wenn Sie brauchen, zu Sortieren einer Liste, wie oft ist diese Liste schon sortiert?wie oft ist es komplett Umgekehrt?wie oft ist es meistens sortiert?) Nicht immer ist es machbar, dass Sie wissen, dass, aber manchmal tun Sie.

gute Frage!

Haftungsausschluss:diese Antwort enthält falsche Aussagen siehe die Kommentare unten.

Wenn Sie die Big-O, sprechen wir über die schlechtesten Fall (mehr darüber, was das bedeutet, wird später).Darüber hinaus ist es Hauptstadt theta für den durchschnittlichen Fall und eine große omega für den besten Fall.

Schauen Sie sich diese Website für einen schönen formalen definition von Groß O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) bedeutet, es gibt positive Konstanten c und k, so dass 0 ≤ f(n) ≤ cg(n) für alle n ≥ k.Die Werte von c und k befestigt werden muss für die Funktion f und darf nicht davon abhängen, n.

Ok, so nun, was meinen wir mit "best-case" und "worst-case" - Komplexität?

Dies ist wahrscheinlich am deutlichsten illustriert durch Beispiele.Zum Beispiel, wenn wir sind mit linearer Suche zu finden, eine Zahl in einer sortierten array, dann die worst case ist, wenn wir entscheiden, zu Suche nach dem letzten element das array würde Sie nehmen, wie viele Schritte gibt es Elemente in dem array.Die best case wäre, wenn wir suchen für die erstes element da würden wir nach dem ersten check.

Der Punkt, der all diese Adjektiv-case-Komplexität ist, dass wir auf der Suche nach einem Weg, um Graphen die Zeit, die eine hypothetische Programm läuft bis zur Fertigstellung im Hinblick auf die Größe der betreffenden Variablen.Doch für viele algorithmen können Sie argumentieren, dass es nicht ein einziges mal für einen bestimmten Größe von Eingang.Beachten Sie, dass dies im Widerspruch mit der grundsätzlichen Anforderung einer Funktion, jeder Eingang sollte nicht mehr als einen Ausgang.Also wir kommen mit mehrere Funktionen zur Beschreibung eines Algorithmus Komplexität.Nun, auch wenn die Suche ein array der Größe n kann nehmen unterschiedliche Mengen an Zeit benötigen, abhängig von, was Sie suchen im array und je proportional zu n, wir erstellen eine informative Beschreibung des Algorithmus anhand von best-case, average-case-und worst-case-Klassen.

Sorry das ist so schlecht geschrieben, und es fehlt viel technischen Informationen.Hoffentlich aber werde es mal machen Komplexität Klassen leichter zu denken.Sobald Sie sich bequem mit diesen wird es eine einfache Sache zu analysieren, die durch Ihr Programm und auf der Suche nach Sachen wie for-Schleifen, die abhängig von array-Größen und-Begründung auf der Grundlage der Daten-Strukturen, welche Art von input, würde das Ergebnis in trivialen Fällen, und was-Eingang wäre die Folge, im schlimmsten Fällen.

Ich weiß nicht, wie programmatisch lösen, aber das erste, was die Leute tun, ist, dass wir eine Probe der Algorithmus für bestimmte Muster in der Anzahl der Operationen, sagen 4n^2 + 2n + 1 wir haben 2 Regeln:

Wenn wir eine Summe von Termen, die den term mit dem größten Wachstum rate ist gehalten, mit der anderen Begriffe verzichtet.
Wenn wir ein Produkt von mehreren Faktoren Konstante Faktoren sind weggelassen.

Wenn wir vereinfachen, f(x), wobei f(x) die Formel für die Anzahl der Operationen, (4n^2 + 2n + 1 wie oben erklärt), so erhalten wir die big-O-Wert [O(n^2) in diesem Fall].Aber dies hätte zu Konto für die Lagrange-interpolation im Programm, die möglicherweise schwer zu implementieren.Und was, wenn die wirkliche big-O-Wert von O(2^n), und wir haben vielleicht so etwas wie O(x^n), so dass dieser Algorithmus würde wahrscheinlich nicht programmierbar.Aber wenn jemand beweist mir, gib mir den code ....

Für code Ein, der äußeren Schleife wird ausgeführt für n+1 mal die '1', heißt der Prozess, der prüft, ob ich immer noch die Anforderungen erfüllt.Und die innere Schleife läuft n Zeiten, n-2 Zeiten....So0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

Für code B, obwohl die innere Schleife würde nicht Schritt, und führen Sie den foo(), die innere Schleife ausgeführt werden, die für n-mal hängen von äußeren Schleife Ausführung Zeit, die O(n)

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

Big-O ist nur zu vergleichen, die Komplexität der Programme, die bedeutet, wie schnell werden Sie wachsen, wenn die Eingänge erhöhen und nicht die exakte Zeit verbringen zu tun.

IMHO in der big-O-Formeln, die Sie besser nicht zu verwenden, komplexere Gleichungen (Sie können nur stick auf diejenigen, die in der folgenden Abbildung.) Allerdings könnten Sie noch verwenden andere genauere Formel (3^n, n^3, ...), aber mehr als das kann manchmal irreführend!Also besser halten Sie es so einfach wie möglich.

Ich möchte noch einmal betonen, dass wir das hier nicht wollen, um eine genaue Formel für unseren Algorithmus.Wir wollen nur zeigen, wie es wächst, wenn die Eingänge sind wachsenden und vergleichen Sie mit den anderen algorithmen in diesem Sinne.Sonst würden Sie besser verwenden unterschiedliche Methoden, wie bench-marking.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow