So finden Sie die zeitliche Komplexität eines Algorithmus

Die Frage

Wie finde ich die zeitliche Komplexität eines Algorithmus?

Was habe ich getan, bevor ich eine Frage zu SO gestellt habe?

Ich habe dies , dieses und viele andere Links durchgesehen

Aber nirgends konnte ich eine klare und direkte Erklärung für die Berechnung der Zeitkomplexität finden.

Was weiß ich ?

Sagen Sie für einen Code, der so einfach ist wie der folgende:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

Sagen Sie für eine Schleife wie die folgende:

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; Dies wird nur einmal ausgeführt . Die Zeit wird tatsächlich berechnet i=0und nicht die Erklärung.

i <N; Dies wird N + 1 Mal ausgeführt

i ++; Dies wird N- mal ausgeführt

Die Anzahl der Operationen, die für diese Schleife erforderlich sind, beträgt also

{1+ (N + 1) + N} = 2N + 2

Hinweis: Dies kann immer noch falsch sein, da ich nicht sicher bin, ob ich die Berechnung der Zeitkomplexität verstehe

Was ich wissen will ?

Ok, also diese kleinen Grundberechnungen glaube ich zu kennen, aber in den meisten Fällen habe ich die zeitliche Komplexität als gesehen

O (N), O (n2), O (log n), O (n!) .... und viele andere ,

Kann mir jemand helfen zu verstehen, wie man die zeitliche Komplexität eines Algorithmus berechnet? Ich bin sicher, es gibt viele Neulinge wie mich, die das wissen wollen.

So finden Sie die zeitliche Komplexität eines Algorithmus

Sie addieren die Anzahl der Maschinenbefehle, die in Abhängigkeit von der Größe der Eingabe ausgeführt werden, und vereinfachen dann den Ausdruck auf den größten (wenn N sehr groß ist) Term und können einen beliebigen vereinfachenden konstanten Faktor enthalten.

Lassen Sie uns zum Beispiel sehen, wie wir 2N + 2Maschinenanweisungen vereinfachen , um dies als gerecht zu beschreiben O(N).

Warum entfernen wir die beiden 2s?

Wir sind an der Leistung des Algorithmus interessiert, wenn N groß wird.

Betrachten Sie die beiden Begriffe 2N und 2.

Welchen relativen Einfluss haben diese beiden Terme, wenn N groß wird? Angenommen, N ist eine Million.

Dann ist die erste Amtszeit 2 Millionen und die zweite Amtszeit ist nur 2.

Aus diesem Grund lassen wir alle bis auf die größten Begriffe für große N fallen.

Also, jetzt sind wir von 2N + 2zu gegangen 2N.

Traditionell sind wir nur an Leistung bis zu konstanten Faktoren interessiert .

Dies bedeutet, dass es uns egal ist, ob es ein konstantes Vielfaches des Leistungsunterschieds gibt, wenn N groß ist. Die Einheit von 2N ist überhaupt nicht gut definiert. Wir können also mit einem konstanten Faktor multiplizieren oder dividieren, um zum einfachsten Ausdruck zu gelangen.

So 2Nwird gerecht N.

Dies ist ein ausgezeichneter Artikel: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Die folgende Antwort wird von oben kopiert (falls der ausgezeichnete Link kaputt geht)

Die gebräuchlichste Metrik zur Berechnung der Zeitkomplexität ist die Big O-Notation. Dies entfernt alle konstanten Faktoren, so dass die Laufzeit in Bezug auf N geschätzt werden kann, wenn N gegen unendlich geht. Im Allgemeinen kann man sich das so vorstellen:

statement;

Ist konstant. Die Laufzeit der Anweisung ändert sich in Bezug auf N nicht.

for ( i = 0; i < N; i++ )
     statement;

Ist linear. Die Laufzeit der Schleife ist direkt proportional zu N. Wenn sich N verdoppelt, verdoppelt sich auch die Laufzeit.

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

Ist quadratisch. Die Laufzeit der beiden Schleifen ist proportional zum Quadrat von N. Wenn sich N verdoppelt, erhöht sich die Laufzeit um N * N.

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

Ist logarithmisch. Die Laufzeit des Algorithmus ist proportional zu der Häufigkeit, mit der N durch 2 geteilt werden kann. Dies liegt daran, dass der Algorithmus den Arbeitsbereich bei jeder Iteration in zwei Hälften teilt.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Ist N * log (N). Die Laufzeit besteht aus N logarithmischen Schleifen (iterativ oder rekursiv), daher ist der Algorithmus eine Kombination aus linear und logarithmisch.

Im Allgemeinen ist es linear, etwas mit jedem Element in einer Dimension zu tun, etwas mit jedem Element in zwei Dimensionen zu tun, und die Aufteilung des Arbeitsbereichs in zwei Hälften ist logarithmisch. Es gibt andere Big O-Kennzahlen wie Kubik, Exponential und Quadratwurzel, aber sie sind bei weitem nicht so häufig. Big O - Notation wird wie folgt beschrieben , O ( <type> )wo <type>ist das Maß. Der Quicksort-Algorithmus würde beschrieben als O ( N * log ( N ) ).

Beachten Sie, dass bei alledem die besten, durchschnittlichen und schlechtesten Maßnahmen nicht berücksichtigt wurden. Jeder hätte seine eigene Big O-Notation. Beachten Sie auch, dass dies eine SEHR vereinfachende Erklärung ist. Big O ist am häufigsten, aber es ist auch komplexer, als ich gezeigt habe. Es gibt auch andere Notationen wie Big Omega, Little O und Big Theta. Sie werden ihnen wahrscheinlich nicht außerhalb eines Kurses zur Algorithmusanalyse begegnen. ;)

Von hier aus - Einführung in die zeitliche Komplexität eines Algorithmus

1. Einleitung

In der Informatik quantifiziert die zeitliche Komplexität eines Algorithmus die Zeit, die ein Algorithmus benötigt, um in Abhängigkeit von der Länge der Zeichenfolge, die die Eingabe darstellt, ausgeführt zu werden.

2. Big O-Notation

Die zeitliche Komplexität eines Algorithmus wird üblicherweise unter Verwendung der Big-O-Notation ausgedrückt, die Koeffizienten und Terme niedrigerer Ordnung ausschließt. Auf diese Weise ausgedrückt wird die Zeitkomplexität als asymptotisch beschrieben, dh wenn die Eingabegröße gegen unendlich geht.

Wenn beispielsweise die Zeit, die ein Algorithmus für alle Eingaben der Größe n benötigt, höchstens 5n ³ + 3n beträgt, beträgt die asymptotische Zeitkomplexität O (n ³ ). Dazu später mehr.

Einige weitere Beispiele:

• 1 = O (n)
• n = O (n ² )
• log (n) = O (n)
• 2 n + 1 = O (n)

3. O (1) Konstante Zeit:

Ein Algorithmus läuft in konstanter Zeit, wenn er unabhängig von der Eingabegröße dieselbe Zeit benötigt.

Beispiele:

• Array: Zugriff auf ein beliebiges Element
• Stapel mit fester Größe: Push- und Pop-Methoden
• Warteschlange mit fester Größe: Enqueue- und Dequeue-Methoden

4. O (n) lineare Zeit

Ein Algorithmus läuft in linearer Zeit, wenn seine Zeitausführung direkt proportional zur Eingabegröße ist, dh die Zeit wächst linear mit zunehmender Eingabegröße.

Betrachten Sie die folgenden Beispiele, unten suche ich linear nach einem Element, dies hat eine zeitliche Komplexität von O (n).

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

Mehr Beispiele:

• Array: Lineare Suche, Durchlaufen, Minimum finden usw.
• ArrayList: enthält Methode
• Warteschlange: enthält Methode

5. O (log n) Logarithmische Zeit:

Ein Algorithmus läuft in logarithmischer Zeit, wenn seine Zeitausführung proportional zum Logarithmus der Eingabegröße ist.

Beispiel: Binäre Suche

Erinnern Sie sich an das Spiel "Zwanzig Fragen" - die Aufgabe besteht darin, den Wert einer versteckten Zahl in einem Intervall zu erraten. Jedes Mal, wenn Sie eine Vermutung anstellen, wird Ihnen mitgeteilt, ob Ihre Vermutung zu hoch oder zu niedrig ist. Das Spiel mit 20 Fragen impliziert eine Strategie, bei der die Anzahl der Intervalle anhand Ihrer Schätzzahl halbiert wird. Dies ist ein Beispiel für die allgemeine Problemlösungsmethode, die als binäre Suche bekannt ist

6. O (n ² ) Quadratische Zeit

Ein Algorithmus läuft in quadratischer Zeit, wenn seine Zeitausführung proportional zum Quadrat der Eingabegröße ist.

Beispiele:

• Blasensortierung
• Auswahl Sortieren
• Sortieren durch Einfügen

7. Einige nützliche Links

• Big-O-Missverständnisse
• Bestimmung der Komplexität des Algorithmus
• Big O Spickzettel

Obwohl es einige gute Antworten auf diese Frage gibt. Ich möchte hier eine weitere Antwort mit einigen Beispielen von geben loop.

• O (n) : Die Zeitkomplexität einer Schleife wird als O (n) betrachtet, wenn die Schleifenvariablen um einen konstanten Betrag inkrementiert / dekrementiert werden. Zum Beispiel haben folgende Funktionen eine O (n) -Zeitkomplexität.

  // Here c is a positive integer constant   
  for (int i = 1; i <= n; i += c) {  
      // some O(1) expressions
  }
  
  for (int i = n; i > 0; i -= c) {
      // some O(1) expressions
  }
  

• O (n ^ c) : Die zeitliche Komplexität verschachtelter Schleifen entspricht der Häufigkeit, mit der die innerste Anweisung ausgeführt wird. Zum Beispiel haben die folgenden Beispielschleifen eine O (n ^ 2) -Zeitkomplexität

  for (int i = 1; i <=n; i += c) {
     for (int j = 1; j <=n; j += c) {
        // some O(1) expressions
     }
  }
  
  for (int i = n; i > 0; i += c) {
     for (int j = i+1; j <=n; j += c) {
        // some O(1) expressions
  }
  

  Zum Beispiel haben Auswahlsortierung und Einfügesortierung eine zeitliche Komplexität von O (n ^ 2) .

• O (Logn) Zeitkomplexität einer Schleife wird als O (Logn) betrachtet, wenn die Schleifenvariablen durch einen konstanten Betrag geteilt / multipliziert werden.

  for (int i = 1; i <=n; i *= c) {
     // some O(1) expressions
  }
  for (int i = n; i > 0; i /= c) {
     // some O(1) expressions
  }
  

  Zum Beispiel hat die binäre Suche eine O (Logn) -Zeitkomplexität .

• O (LogLogn) Zeitkomplexität einer Schleife wird als O (LogLogn) betrachtet, wenn die Schleifenvariablen exponentiell um einen konstanten Betrag verringert / erhöht werden.

  // Here c is a constant greater than 1   
  for (int i = 2; i <=n; i = pow(i, c)) { 
     // some O(1) expressions
  }
  //Here fun is sqrt or cuberoot or any other constant root
  for (int i = n; i > 0; i = fun(i)) { 
     // some O(1) expressions
  }
  

Ein Beispiel für eine Zeitkomplexitätsanalyse

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

Analyse :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Die Gesamtzeitkomplexität des obigen Algorithmus ist also (n + n/2 + n/3 + … + n/n), was wirdn * (1/1 + 1/2 + 1/3 + … + 1/n)

Das Wichtige an Serien (1/1 + 1/2 + 1/3 + … + 1/n)ist gleich O (Logn) . Die zeitliche Komplexität des obigen Codes ist also O (nLogn) .

Ref: 1 2 3

Zeitliche Komplexität mit Beispielen

1 - Grundlegende Operationen (Arithmetik, Vergleiche, Zugriff auf Array-Elemente, Zuordnung): Die Laufzeit ist immer konstant O (1)

Beispiel:

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 - If then else-Anweisung: Nur die maximale Laufzeit von zwei oder mehr möglichen Anweisungen.

Beispiel:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

Die Komplexität des obigen Pseudocodes ist also T (n) = 2 + 1 + max (1, 1 + 2) = 6. Somit ist sein großes oh immer noch konstant T (n) = O (1).

3 - Schleifen (für, während, wiederholen): Die Laufzeit für diese Anweisung ist die Anzahl der Schleifen multipliziert mit der Anzahl der Operationen innerhalb dieser Schleifen.

Beispiel:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

Seine Komplexität ist also T (n) = 1 + 4n + 1 = 4n + 2. Somit ist T (n) = O (n).

4 - Verschachtelte Schleife (Schleife innerhalb der Schleife): Da es mindestens eine Schleife innerhalb der Hauptschleife gibt, wurde für die Laufzeit dieser Anweisung O (n ^ 2) oder O (n ^ 3) verwendet.

Beispiel:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

Gemeinsame Laufzeit

Bei der Analyse eines Algorithmus gibt es einige häufige Laufzeiten:

1. O (1) - Konstante Zeit Konstante Zeit bedeutet, dass die Laufzeit konstant ist und nicht von der Eingabegröße beeinflusst wird .

2. O (n) - Lineare Zeit Wenn ein Algorithmus n Eingabegrößen akzeptiert, würde er auch n Operationen ausführen.

3. O (log n) - Der logarithmische Zeitalgorithmus mit der Laufzeit O (log n) ist geringfügig schneller als O (n). Im Allgemeinen unterteilt der Algorithmus das Problem in Unterprobleme mit derselben Größe. Beispiel: binärer Suchalgorithmus, binärer Konvertierungsalgorithmus.

4. O (n log n) - Linearithmische Zeit Diese Laufzeit wird häufig in "Divide & Conquer-Algorithmen" verwendet, die das Problem rekursiv in Unterprobleme unterteilen und diese dann in n Zeit zusammenführen. Beispiel: Sortieralgorithmus zusammenführen.

5. O (n ² ) - Quadratischer Time Look Bubble Sort-Algorithmus!

6. O (n ³ ) - Kubische Zeit Es hat das gleiche Prinzip wie bei O (n ² ).

7. O (2 ⁿ ) - Exponentialzeit Es ist sehr langsam, wenn die Eingabe größer wird. Wenn n = 1000.000 ist, wäre T (n) 21000.000. Der Brute-Force-Algorithmus hat diese Laufzeit.

8. O (n!) - Faktorielle Zeit DIE LANGSAMSTE !!! Beispiel: Travel Salesman Problem (TSP)

Aus diesem Artikel entnommen . Sehr gut erklärt sollte man lesen.

Wenn Sie Code analysieren, müssen Sie ihn Zeile für Zeile analysieren, jede Operation zählen / Zeitkomplexität erkennen. Am Ende müssen Sie ihn summieren, um ein vollständiges Bild zu erhalten.

Sie können beispielsweise eine einfache Schleife mit linearer Komplexität haben , aber später in demselben Programm können Sie eine Dreifachschleife mit kubischer Komplexität haben , sodass Ihr Programm eine kubische Komplexität aufweist . Hier kommt die funktionale Wachstumsordnung ins Spiel.

Schauen wir uns an, welche Möglichkeiten für die zeitliche Komplexität eines Algorithmus bestehen. Sie können die oben erwähnte Reihenfolge des Wachstums sehen:

• Konstante Zeit hat eine Reihenfolge des Wachstums1, zum Beispiel :a = b + c.

• Die logarithmische Zeit hat eine WachstumsordnungLogN. Sie tritt normalerweise auf, wenn Sie etwas in zwei Hälften teilen (binäre Suche, Bäume, sogar Schleifen) oder etwas auf die gleiche Weise multiplizieren.

• Die lineare Wachstumsordnung istNzum Beispiel

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• Die lineare Wachstumsordnungn*logNtritt normalerweise bei Divide- und Conquer-Algorithmen auf.

• Kubisch , Reihenfolge des WachstumsN^3, klassisches Beispiel ist eine Dreifachschleife, in der Sie alle Drillinge überprüfen:

  int x = 0;
  for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            x = x + 2
  

• Exponentielle Wachstumsreihenfolge2^Ntritt normalerweise auf, wenn Sie eine umfassende Suche durchführen, z. B. Teilmengen einer Gruppe überprüfen.

Die Komplexität der Zeit ist eine Möglichkeit, zusammenzufassen, wie die Anzahl der Operationen oder die Laufzeit eines Algorithmus mit zunehmender Eingabegröße zunimmt.

Wie die meisten Dinge im Leben kann uns eine Cocktailparty helfen, das zu verstehen.

AUF)

Wenn Sie auf der Party ankommen, müssen Sie jedem die Hand schütteln (führen Sie eine Operation an jedem Gegenstand durch). Wenn die Anzahl der Teilnehmer Nzunimmt, steigt die Zeit / Arbeit, die Sie benötigen, um allen die Hand zu schütteln O(N).

Warum O(N)und nicht cN?

Es gibt Unterschiede in der Zeit, die benötigt wird, um Menschen die Hand zu geben. Sie können dies mitteln und in einer Konstanten erfassen c. Aber die grundlegende Operation hier - Händeschütteln mit allen - wäre immer proportional zu O(N), egal was cwar. Wenn wir darüber diskutieren, ob wir zu einer Cocktailparty gehen sollen, sind wir oft mehr daran interessiert, dass wir alle treffen müssen, als an den winzigen Details, wie diese Treffen aussehen.

O (N ^ 2)

Der Gastgeber der Cocktailparty möchte, dass Sie ein albernes Spiel spielen, bei dem jeder auf alle anderen trifft. Deshalb müssen Sie N-1andere Leute treffen , und weil die nächste Person Sie bereits getroffen hat, müssen sie N-2Leute treffen und so weiter. Die Summe dieser Serie ist x^2/2+x/2. Wenn die Anzahl der Teilnehmer wächst, wird der x^2Begriff schnell groß , sodass wir einfach alles andere fallen lassen.

O (N ^ 3)

Sie müssen alle anderen treffen und während jeder Besprechung über alle anderen im Raum sprechen.

O (1)

Der Gastgeber möchte etwas ankündigen. Sie trinken ein Weinglas und sprechen laut. Jeder hört sie. Es stellt sich heraus, dass es keine Rolle spielt, wie viele Teilnehmer es gibt. Dieser Vorgang dauert immer genauso lange.

O (log N)

Der Gastgeber hat alle am Tisch in alphabetischer Reihenfolge angeordnet. Wo ist Dan? Sie argumentieren, dass er irgendwo zwischen Adam und Mandy sein muss (schon gar nicht zwischen Mandy und Zach!). Ist er angesichts dessen zwischen George und Mandy? Nein, er muss zwischen Adam und Fred und zwischen Cindy und Fred sein. Und so weiter ... wir können Dan effizient lokalisieren, indem wir die Hälfte des Sets und dann die Hälfte dieses Sets betrachten. Letztendlich betrachten wir O (log_2 N) Individuen.

O (N log N)

Mit dem obigen Algorithmus können Sie herausfinden, wo Sie sich an den Tisch setzen können. Wenn eine große Anzahl von Personen nacheinander an den Tisch kam und alle dies taten, würde dies O (N log N) Zeit in Anspruch nehmen . Es stellt sich heraus, wie lange es dauert, eine Sammlung von Elementen zu sortieren, wenn sie verglichen werden müssen.

Bester / schlechtester Fall

Sie kommen auf der Party an und müssen Inigo finden - wie lange wird es dauern? Es hängt davon ab, wann Sie ankommen. Wenn alle herumlaufen, haben Sie den schlimmsten Fall getroffen: Es wird einige O(N)Zeit dauern . Wenn sich jedoch alle an den Tisch setzen, dauert es nur eine O(log N)Weile. Oder vielleicht können Sie die Weinglas-Schreikraft des Gastgebers nutzen und es wird nur einige O(1)Zeit dauern .

Angenommen, der Host ist nicht verfügbar, können wir sagen, dass der Inigo-Finding-Algorithmus eine Untergrenze von O(log N)und eine Obergrenze von hat O(N), abhängig vom Status der Partei, wenn Sie ankommen.

Raum & Kommunikation

Dieselben Ideen können angewendet werden, um zu verstehen, wie Algorithmen Raum oder Kommunikation nutzen.

Knuth hat ein schönes Papier über das erstere mit dem Titel "The Complexity of Songs" geschrieben .

Satz 2: Es gibt beliebig lange Lieder der Komplexität O (1).

Beweis: (wegen Casey und der Sunshine Band). Betrachten Sie die durch (15) definierten Songs Sk, aber mit

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

für alle k.

Ich weiß, dass diese Frage einen langen Weg zurückreicht und es hier einige ausgezeichnete Antworten gibt. Dennoch wollte ich ein weiteres Stück für die mathematisch denkenden Menschen teilen, die in diesem Beitrag stolpern werden. Das Master-Theorem ist eine weitere nützliche Sache, die Sie beim Studium der Komplexität wissen sollten. Ich habe es in den anderen Antworten nicht erwähnt gesehen.

O (n) ist eine große O-Notation, die zum Schreiben der Zeitkomplexität eines Algorithmus verwendet wird. Wenn Sie die Anzahl der Ausführungen in einem Algorithmus addieren, erhalten Sie einen Ausdruck im Ergebnis wie 2N + 2, in diesem Ausdruck ist N der dominierende Term (der Term, der den größten Einfluss auf den Ausdruck hat, wenn sein Wert zunimmt oder abnimmt). Jetzt ist O (N) die Zeitkomplexität, während N den Term dominiert. Beispiel

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

Hier beträgt die Gesamtzahl der Ausführungen für die innere Schleife n + 1 und die Gesamtzahl der Ausführungen für die äußere Schleife n (n + 1) / 2, sodass die Gesamtzahl der Ausführungen für den gesamten Algorithmus n + 1 + n (n + 1/2) beträgt ) = (n ^ 2 + 3n) / 2. hier ist n ^ 2 der dominierende Term, daher ist die zeitliche Komplexität für diesen Algorithmus O (n ^ 2)