Big O, wie kann Sie berechnen/approximieren?

Ich werde mein bestes tun, um es hier erklären auf einfache Begriffe, 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 von der Datenstrukturen und Algorithmen in Java Buch.

---

Gibt es keine mechanische Verfahren, die verwendet werden können, um die BigOh.

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

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

Zum Beispiel, sagen wir, 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 liefert die Summe aller Elemente des Arrays, und wir möchten, erstellen Sie eine Formel zum zählen der 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. Der Eingang der Funktion wird die Größe der Struktur zu verarbeiten. Es bedeutet, dass diese Funktion aufgerufen wird, wie:

Number_Of_Steps = f(data.length)

Den 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 von 1 bis 4 nummeriert.

Gibt es viele Wege, um die Berechnung der BigOh. Von diesem Punkt gehen wir davon aus, dass jeder Satz, der nicht abhängig von der Größe der Eingabedaten braucht eine Konstante C Anzahl rechnerische Schritte.

Werden wir die individuelle Anzahl der Schritte von der Funktion, und weder die lokale Variablendeklaration noch die return-Anweisung hängt 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

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

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

Es gibt keine mechanische Regel, zu zählen, wie viele Male die Körper der 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 einfach die Variablen-Initialisierung, Bedingung und Inkrement Teile der for - Anweisung.

Wird die tatsächliche BigOh wir müssen die Asymptotische Analyse der Funktion. Das ist in etwa so geschehen:

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

Unserer f() hat zwei Bedingungen:

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

Nehmen 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 (glaube auf Grenzen) dies ist die BigOh argument, und die sum() Funktion hat eine BigOh:

O(N)

---

Gibt es ein paar tricks zu lösen, einige tricky ones: verwenden Summen, Wann immer Sie können.

Als 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 der foo(). Während der üblichen ist O(1) Sie müssen Fragen Sie Ihre Professoren darüber. O(1) bedeutet (fast, nahezu) konstant C unabhängig von der Größe N.

Den for Aussage auf den Satz Nummer eins ist heikel. Während der index endet auf 2 * N der Schrittweite erfolgt durch zwei. Das bedeutet, dass die ersten for wird nur ausgeführt N Schritte, und wir müssen, teilen Sie die Anzahl von zwei.

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

Den Satz Anzahl zwei ist noch schwieriger, da kommt es auf den Wert der i. Werfen Sie einen Blick: 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 Bühne, auf der sich die zweite for wird nie ausgeführt.

Formel, das bedeutet:

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

Wieder, wir zählen die Anzahl der Schritte. Und per definition, jede Summe sollte beginnen immer mit einer, und am Ende 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 hier ein problem: wenn i nimmt den Wert N /2 + 1 nach oben, die innere Summe endet bei einer negativen Zahl! Das ist unmöglich und falsch. Wir müssen, teilen Sie die 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 )

Da 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.

Nun die Summen vereinfacht werden können, mit einigen identity-Regeln:

1. Summation(w von 1 bis N)( C ) = N * C
2. Summation(w von 1 bis N)( A (+/-) B ) = Summe(w von 1 bis N)( A ) (+/-) Summe(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 von w)
4. Summation(w von 1 bis N)( w ) = (N * (N + 1)) /2

Anwendung einiger 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²)

InformationsquelleAutor vz0

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 können gehen einen langen Weg zu helfen, Sie Entscheidungen treffen, die in Ihrem Algorithmus.

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

O(1) - der Bestimmung, ob eine Zahl gerade oder ungerade ist; die Verwendung eines konstant-Größe lookup-Tabelle oder eine hash-Tabelle

O(logn) - suchen eines Elements in ein sortiertes array mit binärer Suche

O(n) - suchen eines Elements in einer unsortierten Liste, das hinzufügen von zwei n-stelligen zahlen

O(n²) - Multiplizieren von zwei n-stelligen zahlen, die durch einen einfachen Algorithmus, um zwei n×n-Matrizen; bubble sort oder insertion sort

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

O - (cⁿ) - Finden die (exakte) Lösung des traveling salesman Problems mittels dynamischer Programmierung; 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!) zur Ableitung einfacher Formeln für die asymptotische Komplexität

InformationsquelleAutor Giovanni Galbo

Sehen die Antworten hier, ich denke, wir können feststellen, dass die meisten von uns tun, in der Tat annähernd die Reihenfolge der Algorithmus von suchen Sie an und verwenden Sie gesunden Menschenverstand, anstatt ihn zu berechnen, zum Beispiel, die master-Methode, wie wir waren, dachten an der Universität.
Mit dieser sagte ich muss hinzufügen, dass sogar der professor hat uns ermutigt, (später) tatsächlich denke über es, anstatt nur die Berechnung.

Ich würde auch gerne hinzufügen, wie es gemacht wird für rekursive Funktionen:

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

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

welche rekursiv berechnet die Fakultät der Zahl angegeben.

Der erste Schritt ist, zu versuchen und zu bestimmen, die performance-Charakteristik für die Körper der Funktion nur in diesem Fall, nichts besonderes getan wird, in der Körper, nur eine Multiplikation (oder die Rückgabe des Wertes 1).

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

Nächsten versuchen und zu bestimmen, das 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 n ist, wie wir wegwerfen, die unwesentlichen teilen).

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

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

---

Peter, zu beantworten Ihre aufgeworfenen Fragen; die Methode, die ich hier beschreibe tatsächlich behandelt das sehr gut. Aber Bedenken Sie, dass dies ist immer noch ein Annäherung und nicht eine vollständige 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, wurde für weit mehr fortschrittliche algorithmen, als die Fakultät, die ich in diesem Beispiel verwendet.

Natürlich ist es hängt alles davon ab, wie gut Sie schätzen können, die Laufzeit der Körper der Funktion und die Anzahl der rekursiven Aufrufe, aber das gilt nicht nur für die anderen Methoden.

InformationsquelleAutor sven

Ich denke, über die 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 deren Entropie. Die Entropie einer Entscheidung ist der Durchschnitt, wird es geben Sie. Zum Beispiel, wenn ein Programm enthält eine Entscheidung mit zwei Niederlassungen, die Entropie ist die Summe der Wahrscheinlichkeit jedes Zweigs mal die log₂ der inversen Wahrscheinlichkeit, dass dieser Zweig. Das ist, wie viel Sie lernen durch die Ausführung der Entscheidung.

Beispielsweise eine if - Anweisung mit zwei Zweigen, 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. Also seine Entropie 1 bit.

Angenommen, Sie sind auf der Suche eine Tabelle von N Elementen, wie N=1024. Das ist ein 10-bit-problem, weil log(1024) = 10 bit. Also, wenn Sie können, suchen Sie es mit, WENN Aussagen, Ergebnisse gleich wahrscheinlich sind, sollte es nehmen 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 * melden(1024/1023) = 1/1024 * 10 + 1023/1024 * über 0 = über 01 bit. Sie haben gelernt, sehr wenig! Die zweite Entscheidung ist auch nicht viel besser. Deshalb ist die lineare Suche ist so langsam. In der Tat, es ist exponentiell in der Anzahl der bits, die Sie brauchen, um zu lernen.

Nehme an, Sie tun Indizierung. Nehmen wir an, die Tabelle ist vorsortiert in einer Menge von Behältern, und verwenden Sie einige der alle bits in dem Schlüssel-index direkt auf den Tabelleneintrag. Wenn es 1024 bins, die Entropie ist 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, die eine Indizierung Betrieb. Deshalb ist die Indizierung Suche schnell.

Denken Sie jetzt an das Sortieren. Sie haben N Elemente, und Sie haben eine Liste. Für jedes Element, die Sie haben zu suchen, wo das Element geht in die 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 etwa gleich wahrscheinlich, Ergebnisse alle etwa O(N log N) Schritte. Ein O(N) sort-Algorithmus ist möglich, wenn es sich auf die Indizierung der Suche.

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

InformationsquelleAutor Mike Dunlavey

Wenn Sie wollen, zu schätzen, die Reihenfolge der code-empirisch eher als durch die Analyse des Codes konnte-stick in einer Reihe von zunehmenden Werten von n und time code. Zeichnen Sie Ihre Zeiten auf einer log-Skala. Wenn der code O(x^n), die Werte fallen sollten auf einer Linie der Steigung n.

Diese 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 Laufzeit nähert sich seinem asymptotische Ordnung. Auch, Sie können feststellen, dass einige der code, den Sie dachte, war die Ordnung O(x) ist O(x^2), zum Beispiel, weil die Zeit, in der Bibliothek anrufen.

InformationsquelleAutor John D. Cook

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

Weitere Informationen, überprüfen Sie die Wikipedia-Seite auf das Thema.

InformationsquelleAutor Lasse Vågsæther Karlsen

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

InformationsquelleAutor Matt Mitchell

Als "wie berechnen Sie die" Big O, das ist ein Teil von Komplexitätstheorie. Für einige (viele) in besonderen Fällen können Sie in der Lage zu kommen mit einigen einfachen Heuristiken (wie Multiplikation Schleife zählt für verschachtelte Schleifen), esp. wenn alle Sie wollen, ist jeder upper bound-Schätzung, und es Sie nicht stört, wenn er zu pessimistisch - ich glaube, das ist wahrscheinlich das, was Ihre Frage ist.

Wenn Sie wirklich wollen, um Ihre Frage zu beantworten, die für jeden Algorithmus die beste Sie tun können, ist die Anwendung der Theorie. Neben der simpel "worst-case" - Analyse, die ich gefunden habe Amortisierten Analyse sehr nützlich in der Praxis.

InformationsquelleAutor Suma

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

Als ein sehr einfaches Beispiel, sagen, Sie wollten eine überprüfung auf die Geschwindigkeit des .NET framework ist die Liste Sortieren. Könnten Sie etwas schreiben wie das folgende, dann analysieren Sie die Ergebnisse in Excel, um sicherzustellen, dass Sie nicht mehr als eine n*log(n) - Kurve.

In diesem Beispiel habe ich Messen die Zahl der Vergleiche, aber es ist auch ratsam zu prüfen, den tatsächlichen Zeitaufwand für die einzelnen sample-Größe. Aber dann müssen Sie noch vorsichtiger sein, dass Sie nur die Messung der Algorithmus und nicht einschließlich 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);

InformationsquelleAutor Eric

Was oft übersehen wird ist die erwartet Verhalten der algorithmen. Es nicht ändern, dass die Big-O Ihres Algorithmus, aber es nicht beziehen sich auf die Aussage "vorzeitige Optimierung. . .."

Erwartete Verhalten des Algorithmus ist -- sehr verdummt-wie schnell können Sie erwarten, dass Ihre algorithmen arbeiten auf Daten, die Sie 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, haben Ihren Wert vorne, typisches Verhalten des Algorithmus schneller ist.

Wirklich Nagel es sich, Sie müssen in der Lage sein zu beschreiben, in dem die Wahrscheinlichkeitsverteilung von Ihrem "input-Raum" (wenn Sie brauchen, um Sortieren eine Liste, wie oft wird diese Liste schon sortiert ist? wie oft ist es komplett Umgekehrt? wie oft ist es meist sortiert?) Es ist nicht immer machbar, dass Sie wissen, dass, aber manchmal tun Sie.

InformationsquelleAutor Baltimark

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

1. Wenn wir eine Summe von Termen der Begriff mit der größten Wachstumsrate ist gehalten, mit anderen Bezeichnungen weggelassen.
   
2. Wenn wir ein Produkt haben, von mehreren Faktoren Konstante Faktoren werden weggelassen.

Wenn wir vereinfachen f(x), wobei f(x) ist 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 zur Rechenschaft für die Lagrange-interpolation im Programm, die vielleicht schwer zu implementieren. Und was ist, wenn der echte 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 mich falsch, gib mir den code . . . .

InformationsquelleAutor Gavriel Feria

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

Big-O ist nur zum Vergleich der Komplexität der Programme, das heißt, wie schnell werden Sie wachsen, wenn die Eingänge werden immer mehr und nicht die genaue Zeit verbringen zu tun.

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

Möchte ich noch einmal betonen, dass wir das hier nicht wollen, um eine exakte Formel für unseren Algorithmus. Wir wollen nur zeigen, wie es wächst, wenn die Eingänge wachsen und vergleichen Sie mit den anderen algorithmen in diesem Sinn. Sonst würden Sie besser verwenden verschiedene Methoden wie bench-marking.

InformationsquelleAutor HmT