Komplexitäts ein Stück Code

Question

Ich habe ein Programm aufgestellt, und versucht, seine Komplexität zu berechnen. Ich will sicher sein, ich bin nicht irr

for(int i=4; i<=n; i=i*4) 
{ 
    cout<<"counter for first loop: "<<++count1<<endl; 
    for(int j=i;j>=0;j=j-4) 
    { 
     cout<<"counter for second loop: "<<++count2<<endl; 
     for(int k=0;k<=n;k++) 
     { 
      cout<<"counter for third loop: "<<++count3<<endl; 
     } 
    } 
} 

Hier wird die Komplexität der dritten Schleife ist O (n), dann zusammen mit der zweiten Schleife, die Komplexität wird O (n.log i), und die Komplexität des gesamten Programms ist O (n. (log i)). Bin ich richtig in meiner Antwort? Dank

Answer 1

Die Komplexität der innerste Schleife ist O (n). Die Komplexität des mittleren ist O (i/4), was wiederum O (i) ist. Die Komplexität der äußersten Schleife ist O (log n). Es für die Gesamtkomplexität des Codes ist O (n.i.log 4 n), die mit O gleich (n. (Log n) 2).

Answer 2

können Sie gehen formal wie folgt aus:

Ausführung dieses Fragment:

sum = 0; 
for(i = 4 ; i <= n; i = i * 4) { 
    for(j = i ; j >= 0 ; j = j - 4) { 
     for(k = 0 ; k <= n ; k ++) { 
      sum ++; 
     } 
    } 
} 

Wir erhalten:

Ergebnisse genau kompatibel mit der obigen Formel.

Außerdem beiden inneren Schleifen Laufzeit ist O (n), ..., was bedeutet, dass, wenn sie zusammengeführt, erhalten wir O (n²).