Obliczeniowa złożoność kawałka kodu

Question

Mam program i próbuję obliczyć jego złożoność. Chcę mieć pewność, że nie mylę

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; 
     } 
    } 
} 

Tutaj złożoność trzeciej pętli jest O (n), a następnie razem z drugą pętlę, złożoność staje O (n.log I) a złożoność całego programu to O (n. (log i)). Czy mam rację w mojej odpowiedzi? Dzięki

Answer 1

Złożoność najbardziej wewnętrznej pętli to O (n). Złożoność środkowej jest O (i/4), która z kolei jest O (i). Złożoność najbardziej zewnętrznej pętli to O (log n). Tam dla całkowitej złożoności kodu jest O (n.i.log n), który jest równy O (n. (Log n)).

Answer 2

można przystąpić formalnie tak:

Wykonanie tego fragmentu:

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 ++; 
     } 
    } 
} 

Otrzymujemy:

wyników dokładnie zgodne z powyższym wzorem.

Poza tym, oba środowiska wykonawcze pętli wewnętrznej to O (n) ... co oznacza, że ​​po wykonaniu razem otrzymamy O (n²).