Complessità computazionale di un pezzo di codice

Question

Ho un programma e cerco di calcolare la sua complessità. Voglio essere sicuro che non mi sbaglio

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

Qui, la complessità del terzo ciclo è O (n), poi insieme con il secondo ciclo, la complessità diventa O (n.log i), e la complessità dell'intero programma è O (n. (log i)). Ho ragione nella mia risposta? Grazie

Answer 1

La complessità del ciclo più interno è O (n). La complessità di quello medio è O (i/4), che a sua volta è O (i). La complessità del loop più esterno è O (log n). Lì per la complessità totale del codice è O (n.i.log n) che è uguale a O (n. (Log _4n)).

Answer 2

È possibile procedere formalmente simile al seguente:

L'esecuzione di questo frammento:

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

Otteniamo:

risultati esattamente compatibili con la formula di cui sopra.

Inoltre, il runtime di entrambi i loop interni è O (n) ... il che significa che, quando vengono eseguiti insieme, otteniamo O (n²).