Complexité temporelle O (N) des boucles imbriquées avec if-statement: O (N^4)?

Question

J'essaie de comprendre un virage serré lié en termes de grand-O pour cet extrait:

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

Si nous commençons par la plupart boucle interne, il sera dans le pire des cas courir k = n^2 fois, qui représente O (N^2). L'instruction if sera vraie à chaque fois j = m * i, où m est une constante arbitraire. Puisque j va de 1 à i^2, cela se produira quand m = {1, 2, ..., i}, ce qui signifie que ce sera vrai i fois, et je peux tout au plus être n, donc le pire sera soit m = {1,2, ..., n} = n fois. La deuxième boucle devrait avoir un cas plus grave de O (N^2) si i = n. La boucle externe a une complexité de O (N) dans le pire des cas. Je soutiens que cela se combinera de la façon suivante: O (N^2) pour la boucle interne * O (N^2) pour la deuxième boucle * O (N) pour la boucle externe donne le pire des cas complexité de O (N^5)

Cependant, l'instruction if garantit que nous atteindrons seulement la boucle interne n fois, pas n^2. Mais indépendamment de cela, nous devons toujours passer par les boucles externes n * n^2 fois. Est-ce que le test if influence la complexité du temps le plus défavorable pour l'extrait?

Édition: Corrigé pour j à i^2, pas i.

Answer 1

Vous pouvez simplifier l'analyse par la réécriture de vos boucles sans if, comme suit:

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

Ceci élimine les étapes dans lesquelles les skips conditionnelles sur la « charge utile » de la boucle. La complexité de ce système de boucles équivalent est O (n).

Answer 2

I analyse your question in a more straightfroward way 
    we first start by fix i as a costant, 
    for example, assume it to be k, 
    so j=1~k^2, when j=k,2k,3k,...,k^2, assume j to be c*k (c=1~k) 
    the next loop will be executed c^2 times, 
    so the complexity for a fix i can be expressed as=> 
    (1+.....+1)+(1+1+...+2^2)+(1+1+...+3^2)+.....+(1+1+...+k^2) 
    = O(k^3) 
    so now we set k to be 1~n, so the total complexity will be O(n^4)