Auftrag des Wachstums als Worst-Case-Zeit als Funktion der N

Question

mit dem folgenden Codefragment ausgeführt wird:

int sum = 0; 
for (int i = 1; i <= N; i++) 
    for (int j = 1; j <= i*i; j++) 
     for (int k = 1; k <= j*j; k++) 
      sum++; 

Meine Vermutung:

• Äußere Schleife: O (N)
• Mittelschleife : O (N * N)
• innerste Schleife: O (N * N)

Daher sollte die Gesamtlaufzeit O (N^5) sein, oder?

Answer 1

Einleitend

sum(k=1,p,k^2) = p(p+1)(2p+1)/6 = O(p^3) 
sum(k=1,p,k^6) = O(p^7) 

Computation of Komplexität

1. Die innere Schleife aus k=1 läuft an j^2 es so tut genau j^2 Operationen.
2. Die mittlere Schleife läuft von j=1 zu i^2 und bei jedem Schritt tun wir j^2 Operationen. Nach meiner vorläufigen Beobachtung können wir durch Einsetzen von p=i^2 in die erste Gleichung die Gesamtoperationen als i^2(i^2+1)(2*i^2+1)/6 für jeden Wert von i berechnen. Dies ist eine O((i^2)^3) = O(i^6) Anzahl von Operationen.
3. Die äußere Schleife läuft von i=1 bis n und macht O(i^6) Operationen bei jedem Schritt. So haben wir O(n^7) Operationen.

Referenzen

• http://www.math.com/tables/expansion/power.htm

Answer 2

Lässt sich öffnen, wie oft jede Schleife ausgeführt wird.

First loop 1, 2, 3, 4, 5, ...., N 
Second loop 1, 4, 9, 16, 25, ...., (N*N)    // N^2 
Third loop 1, 16, 81, 256, 625, ...., ((N*N)*(N*N)) // N^4 

Also, ich denke, die Komplexität sollte N^sein 4

EDIT 1

Basierend auf einem Kommentar, ich glaube, die Komplexität Summe der Reihe sein wird

1, 16, 81, 256, 625, ...., ((N*N)*(N*N)) 

EDIT 2

Ich glaube wir haben beim Öffnen der Loops einen Fehler gemacht (Danke an CodeYogi). Versuchen wir es noch einmal.

First loop 1, 2, 3, 4, 5, ...., N 
Second loop 1, 4(1,2,3, 4), 9 (1,2,....9), 16, 25, ...., (N*N) 
Third loop 1, 30(1+4+9+16), 285(1+4+...81), and so on.......... 

Answer 3

Ich denke, dass die endgültige O ist auf jeden Fall höher als O(n^4) und etwas höher als O(n^5), aber da diese Big O-Notation ist, können wir sagen, dass es O (n^5) ist. Letzte Schleife wird diese Menge an Zeit ausführen:

1 + 2^4 + 3^4 + 4^4 + ... + n^4 

Wolframalpha stellt es als:

Bitte beachten Sie erweiterte Version für n>0:

Edit:

Ich habe gerade festgestellt, dass es eine Lücke in meiner Antwort gibt, denn die meisten inneren Schleifen werden öfter ausgeführt als ich angenommen habe. Betrachtet man die Ergebnisse dieser dreifachen Schleife und zeichnet sie auf, scheint es höher zu sein als O(n^6). Ich werde darauf zurückkommen.

Bearbeiten 2: Wie ich schon sagte, lag ich falsch. Kann es nicht besser erklären als @fjardon in seinem answer.