So finden Sie die zeitliche Komplexität eines Algorithmus

889

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.

Yasser Shaikh
quelle
138
Bonus für Interessierte: The Big O Spickzettel bigocheatsheet.com
msanford
4
Schauen Sie sich diesen Blog an: mohalgorithmsorbit.blogspot.com . Es behandelt sowohl rekursive als auch (insbesondere) iterative Algorithmen.
Mohamed Ennahdi El Idrissi
1
Warum ist Console.Write ('Hallo Welt!'); keine maschinenanweisung?
Chetan
Verwandte / vielleicht doppelte: Big O, wie berechnet / approximiert man es?
Bernhard Barker
1
@Chetan Wenn Sie meinen, dass Sie Console.Writebei der Berechnung der Komplexität berücksichtigen sollten , ist dies wahr, aber in diesem Fall auch etwas irrelevant, da dies nur einen konstanten Faktor ändert, den Big-O ignoriert (siehe die Antworten), sodass das Endergebnis immer noch erhalten bleibt eine Komplexität von O (N).
Bernhard Barker

Antworten:

394

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.

Andrew Tomazos
quelle
53
Hey, danke, dass du mich wissen lässt, warum O (2N + 2) bis O (N) sehr schön erklärt wurde, aber dies war nur ein Teil der größeren Frage. Ich wollte, dass jemand auf einen Link zu einer versteckten Ressource oder in hinweist Allgemein Ich wollte wissen, wie man am Ende Zeitkomplexitäten wie O (N), O (n2), O (log n), O (n!) usw. hat. Ich weiß, dass ich vielleicht viel frage, aber trotzdem kann ich versuchen: {)
Yasser Shaikh
3
Nun, die Komplexität in den Klammern ist nur, wie lange der Algorithmus dauert, vereinfacht mit der von mir erläuterten Methode. Wir berechnen, wie lange der Algorithmus dauert, indem wir einfach die Anzahl der Maschinenanweisungen addieren, die er ausführen wird. Wir können vereinfachen, indem wir nur die am stärksten frequentierten Schleifen betrachten und durch konstante Faktoren dividieren, wie ich erklärt habe.
Andrew Tomazos
4
Ein Beispiel für eine Antwort zu geben, hätte für zukünftige Leser sehr geholfen. Nur einen Link zu übergeben, für den ich mich anmelden muss, hilft mir nicht wirklich, wenn ich nur einen gut erklärten Text durchgehen möchte.
bad_keypoints
2
Ich würde vorschlagen, sich Videos von Dr. Naveen Garg (IIT Delhi Prof.) anzusehen, wenn Sie gute Kenntnisse über DS und Zeitkomplexität erhalten möchten. Überprüfen Sie den Link. nptel.ac.in/courses/106102064
Rohit Bandil
2
(Forts.) Diese Hierarchie hätte eine Höhe in der Größenordnung von log N. Was O (N!) betrifft, werden meine Analogien sie wahrscheinlich nicht schneiden, aber die Permutationen liegen in dieser Reihenfolge - sie sind unerschwinglich steiler als jedes Polynom oder exponentiell. Es sind genau 10! Sekunden in sechs Wochen, aber das Universum ist weniger als 20! Sekunden alt.
John P
389

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

Achow
quelle
10
Der Quicksort- Algorithmus hat im schlimmsten Fall eine Laufzeit von N ^ 2, obwohl dieses Verhalten selten ist.
nbro
2
IIRC, Little O und Big Omega werden für die beste und durchschnittliche Fallkomplexität verwendet (wobei Big O der Worst Case ist), also "Best-, Average- und Worst Case-Kennzahlen. Jede würde ihre eigene Big O-Notation haben." wäre falsch. Es gibt noch mehr Symbole mit spezifischeren Bedeutungen, und CS verwendet nicht immer das am besten geeignete Symbol. All dies lernte ich übrigens unter dem Namen Landau-Symbole . +1 sowieso b / c beste Antwort.
hiergiltdiestfu
@hiergiltdiestfu Big-O, Big-Omega usw. können auf jede der besten, durchschnittlichen oder schlechtesten Laufzeiten eines Algorithmus angewendet werden. Wie hängen O und Ω mit dem schlechtesten und besten Fall zusammen?
Bernhard Barker
Wenn jemand nach einer Möglichkeit
OhadM
Eine der besten Erklärungen.
Shivaraj Patil
172

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 3 + 3n beträgt, beträgt die asymptotische Zeitkomplexität O (n 3 ). Dazu später mehr.

Einige weitere Beispiele:

  • 1 = O (n)
  • n = O (n 2 )
  • 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 2 ) Quadratische Zeit

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

Beispiele:

7. Einige nützliche Links

Yasser Shaikh
quelle
17
Hinweis: Der erste Link ist unterbrochen.
Ziezi
2
O (n2) sollte O (n ^ 2) geschrieben werden, um Verwirrung zu vermeiden.
Rizki Hadiaturrasyid
100

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

zangw
quelle
1
@ Simon, Könnten Sie bitte herausfinden, welcher Teil falsch ist?
Zangw
Danke für die Frage. Ich habe den Code falsch verstanden. Ich habe meinen Kommentar gelöscht. Es tut uns leid!
Simon
74

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 2 ) - Quadratischer Time Look Bubble Sort-Algorithmus!

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

  7. O (2 n ) - 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.

Yasser Shaikh
quelle
In Ihrem zweiten Beispiel schrieb sie visitors = visitors + 1heißt 1 + 1 = 2. Könnten Sie mir bitte erklären, warum Sie das getan haben?
Sajib Acharya
3
@Sajib Acharya Schau es von rechts nach links. Erster Schritt: Berechnen visitors + 1 Zweiter Schritt: Weisen Sie dem ersten Schritt einen Wert zu visitors . Der obige Ausdruck besteht aus zwei Anweisungen. erster Schritt + zweiter Schritt => 1 + 1 = 2
Bozidar Sikanjic
@nbro Warum es 1 + 1 inage = read(x) // (1+1) = 2
Humty
@BozidarSikanjic Warum es 1 + 1 inage = read(x) // (1+1) = 2
Humty
1
@Humty Überprüfen Sie den Anfang dieser Antwort: read(x) // O(1) a = 10; // O(1)Erstens ist Funktionsaufruf => O (1) ///// Zweitens ist Zuweisung, wie nbro sagte, aber 10 ist konstant, also ist zweitens => O (1) ...
Bozidar Sikanjic
41

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.

Aleksandar Makragić
quelle
Wenn dies der Fall wäre, wie komplex wäre das? für (int i = 0; i <N; i ++) für (int j = i + 1; j <N; j ++) für (int k = j + 1; k <N; k ++) x = x + 2
user3156040
35

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.

Richard
quelle
Du hast es geschafft. Wenn ich jetzt zu einer Cocktailparty gehe, werde ich unbewusst versuchen, die zeitliche Komplexität aller lustigen Ereignisse zu finden. Vielen Dank für solch ein humorvolles Beispiel.
Sabunkar Tejas Sahailesh
5

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.

Enzian Kasa
quelle
2

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)

ifra khan
quelle