algorithm - loop - ¿Cuál es el análisis Big O de este algoritmo?

for loop complexity

Question

Estoy trabajando en un curso de estructuras de datos y no estoy seguro de cómo proceder con este análisis de Big 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++;

Mi idea inicial es que esto es O (n ^ 3) después de la reducción, porque el ciclo más interno solo se ejecutará cuando j / i no tenga residuo y la regla de multiplicación no sea aplicable. ¿Mi razonamiento es correcto aquí?

Answer 1

Vamos a ignorar el bucle externo por un segundo aquí, y vamos a analizarlo en términos de i .

El ciclo medio se ejecuta i^2 veces, y está invocando el ciclo interno siempre que j%i == 0 , eso significa que lo ejecuta en i, 2i, 3i, ...,i^2 , y en cada momento ejecuta hasta la j relevante, esto significa que la suma del ciclo interno del tiempo de ejecución es:

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

La última igualdad proviene de la suma de la progresión aritmética .
Lo anterior está en O(i^3) .

repite esto en el ciclo externo que va de 1 a n y obtendrás tiempo de ejecución de O(n^4) , ya que en realidad tienes:

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)

La última ecuación viene de la suma de cubos
Y lo anterior está en O(n^4) , que es su complejidad.