O-notation avec for-loop avec modulo condition

Question

Ma question est comment calculer la notation O à cette opération, où les deux boucles externes iront O (n^3) fois. Ma question est de savoir ce que la notation o va être quand modulo est utilisé dans une condtion et la boucle for interne court juste quand i est un facteur dans j.

for(int i = 1 ; i <= n ; i++) { 
    for(int j =1; j <= i ∗ i ; j++) { 
     if(j % i == 0) { 
     for(int k = 0 ; k < j ; k++){ 
      sum++; 
     } 
     } 
    } 
} 

Answer 1

C'est O(n^4).

L'astuce avec celui-ci est le if (j % i == 0). Depuis i est à peu près n et j va aller à n^2 nous savons que cette déclaration sera vraie n + (n-1) + ... + 1 fois qui va simplifier à (n+1)(n+2)/2 ou O(n^2) qui, à son tour lancer une boucle qui court n^2 fois. Nous avons ensuite besoin de le traiter comme un ajout, donc nous avons n^3 + n^2 * n^2, cela se simplifie à O(n^4).

S'il y a un défaut dans mon raisonnement, signalez-le, je suis un peu rouillé.