Come calcolare la complessità della Big-O del seguente algoritmo?

Question

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.

Answer 1

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) $ .