Come calcolare la complessità della Big-O del seguente algoritmo?
-
29-09-2020 - |
Domanda
Ho cercato di calcolare il Big-O del seguente algoritmo e sta arrivando ad essere o (n ^ 5) per me. Non so cosa sia la risposta corretta, ma la maggior parte dei miei colleghi stanno ottenendo o (n ^ 3).
for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}
.
Quello che ho fatto è stato partenza dal loop più intimo. Quindi ho calcolato che il ciclo più interno eseguirà tempi n/2
, poi sono andato al secondo nidificato per il ciclo che eseguirà tempi i^2
e dal ciclo più esterno eseguirà tempi i
come i
varia da 1
a n
. Ciò significherebbe che il secondo nidificato per loop eseguirà un totale di Sigma(i^2) from i=1 to i=n
in modo da un totale di tempi n*(n+1)*(2n+1)/6
. Quindi l'importo totale che il codice sarebbe uscito per essere nell'ordine di n^5
, quindi ho concluso che l'ordine deve essere O(n^5)
. C'è qualcosa di sbagliato con questo approccio e la risposta che ho calcolato?
Ho appena iniziato con DSA e questo è stato il mio primo incarico, quindi ci scusa per tutti gli errori di base che avrei potuto fare.
Soluzione
for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}
.
Il ciclo triplo nidificato è equivalente alla sommazione $$ \ sum_ {i= 1} ^ {n} \ sum_ {j= 1} ^ {i ^ 2} \ sum_ {k= 1} ^ {n / 2} 1$$ $$=frac {n} {2} (\ sum_ {i= 1} ^ {n} \ sum_ {j= 1} ^ {I ^ 2} 1) $$ $$=frac {n} {2} (\ sum_ {i= 1} ^ {n} I ^ 2) $$ $$=frac {n} {2} \ cdot (\ frac {1} {6} n (n + 1) (2n + 1)) $$ $$= o (n ^ 4) $$
.
In termini di effettivo efficienza del codice, poiché x=y+z
è invariante nel ciclo, qualsiasi buon compilatore ottimizzante estrarrà l'istruzione fuori dal ciclo (in compilatore-parlare, sollevando la dichiarazione per il prerogatore del loop), quindi effettuare il codice compilato in $ o (1) $ .