Was ist die Komplexität dieses verschachtelten Triple for Loop?

Question

Ich habe ein wenig auf StackOverflow gesucht und die Komplexität bis zu dem Punkt der J-Schleife verstanden, die O(n2) ist. Bei der verschachtelten Addition der k-Schleife bin ich jedoch verwirrt, warum die Komplexität O(n3) wird. Kann mir jemand helfen, das zu verstehen?

Aus meiner Sicht haben die i-Schleife n Iterationen und die J-Schleife haben 1 + 2 + 3 + ... + n Iterationen n*(n+1)/2, die O(n2) ist.

for(i = 1; i < n; i++) { 
    for(j = i+1; j <= n; j++) { 
     for(k = i; k <= j; k++) { 
      // Do something here... 
     } 
    } 
} 

EDIT: Vielen Dank für Ihre Hilfe Jungs :) Balthazar, ich habe ein Stück Code geschrieben, der Zähler zählt hoch, je nachdem, welche Schleife sie sind, irgendwie eine rohe Art und Weise von Schritt-für- Schritt:

#include <iostream> 

int main(int argc, const char * argv[]) 
{ 
    int n = 9; 
    int index_I = 0; 
    int index_J = 0; 
    int index_K = 0; 
    for (int i = 1; i < n; i++) { 
     for (int j = i+1; j <= n; j++) { 
      for (int k = i; k <= j; k++) { 
       index_K++; 
      } 
      index_J++; 
     } 
     index_I++; 
    } 
    std::cout << index_I << std::endl; 
    std::cout << index_J << std::endl; 
    std::cout << index_K << std::endl; 
    return 0; 
} 

lief ich diesen Code von n = 2 bis n = 9 mit Schritten von 1 und haben die folgende Sequenz erhielt:

Aus den Zählern ist daher ersichtlich: i = n-1, was die Komplexität von O (n) und j = ((n-1) * n)/2 ergibt, was die Komplexität O(n2) ergibt. Ein Muster für K war schwer zu erkennen, aber es ist bekannt, dass K auf J abhängt, deshalb:

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 gibt eine Komplexität von O(n3)

ich hoffe, diese Menschen in der Zukunft helfen wird.

EDIT2: Dank Dukeling für die Formatierung :) Auch einen Fehler in der letzten Zeile gefunden, korrigiert nun

Answer 1

einen Blick auf this Beispiel Nehmen Sie für den ungünstigsten Fall Komplexität zu bewerten.

Im Wesentlichen, wenn Sie es Zeile für Zeile auswerten, erhalten Sie etwas wie O (n^3/C), wobei C eine Konstante ist, normalerweise in solchen Bewertungen übersprungen, was zu O (n^3) .

Answer 2

die k-Schleife hat O (ji) Komplexitäts

der j-Schleife hat O ((ni) · (ni)) Komplexität

die i-Schleife hat O (n * n * n) = O (n^3) Komplexität

Wie auch immer, Sie wissen, dass es nicht O (n^2) ist, weil die ersten beiden Schleifen O (n^2) sind und nicht mehr als O (n^3) da es nur 3 Schleifen gibt

Answer 3

Dies ist ziemlich schwierig ohne Diagramme zu erklären, aber jede verschachtelte Schleife iteriert "n" mal, bevor die Iteration an die pa zurückgegeben wird Miete.

So wie Jambono darauf hinweist, erfordert jede verschachtelte Schleife Vergleich/Auswertung für jede Iteration von "n". Also wird "n" mit den lokalen Variablen in jeder Schleife (n * n * n) verglichen, was O (n^3) ergibt.

Schritt den Code in einem Debugger für eine visuelle Anzeige, wie diese Komplexität von der Maschine verarbeitet wird.

Answer 4

Wenn Sie Sigma Notation gewöhnt sind, ist hier eine formale Möglichkeit, die Zeit Komplexität des Algorithmus (die Ebene verschachtelten Schleifen, genau) ableiten:

NB: Die Formel Vereinfachungen könnte Fehler enthalten. Wenn Sie etwas entdecken, lassen Sie es mich wissen.

Answer 5

Zunächst betrachten wir Schleifen, bei denen die Anzahl der Iterationen der inneren Schleife unabhängig vom Wert des Index der äußeren Schleife ist. Beispiel:

for (i = 0; i < N; i++) { 
     for (j = 0; j < M; j++) { 
      sequence of statements 
     } 
    } 

Die äußere Schleife wird N-mal ausgeführt. Jedes Mal, wenn die äußere Schleife ausgeführt wird, führt die innere Schleife M-mal aus. Als Ergebnis führen die Anweisungen in der inneren Schleife insgesamt N · M-mal aus.
Somit ist die Gesamtkomplexität für die beiden Schleifen O (N2).
Ähnlich ist die Komplexität für die drei Schleifen O (N3)