Che cos'è l'analisi Big O di questo algoritmo?

Question

Sto lavorando su un corso di strutture di dati e non sono sicuro di come procedere w/questo Big analisi O:

sum = 0; 
for(i = 1; i < n; i++) 
    for(j = 1; j < i*i; j++) 
     if(j % i == 0) 
      for(k = 0; k < j; k++) 
        sum++; 

mia idea iniziale è che questo è O (n^3) dopo la riduzione, poiché il ciclo più interno verrà eseguito solo quando j/i non ha resto e la regola di moltiplicazione non è applicabile. Il mio ragionamento è corretto qui?

Answer 1

Ignoriamo il ciclo esterno per un secondo qui e analizziamolo in termini di i.

Il ciclo metà corre i^2 volte, e invoca il ciclo interno ogni volta j%i == 0, significa che si esegue su i, 2i, 3i, ...,i^2, e ad ogni volta che si esegue fino a quando il relativo j, questo significa che il ciclo somma interna di tempo di esecuzione è :

i + 2i + 3i + ... + (i-1)*i = i(1 + 2 + ... + i-1) = i* [i*(i-1)/2] 

L'ultima uguaglianza viene da sum of arithmetic progression.
Quanto sopra riportato è O(i^3).

ripetere questo per il ciclo esterno che corre 1-n e si otterrà il tempo di O(n^4) esecuzione, dal momento che in realtà hanno:

C*1^3 + C*2^3 + ... + C*(n-1)^3 = C*(1^3 + 2^3 + ... + (n-1)^3) = 
= C/4 * (n^4 - 2n^3 + n^2) 

L'ultima equazione viene da sum of cubes
E quanto sopra è in O(n^4), che è la vostra complessità.