int sum = 0;
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++;
            }
        }
    }
}

No entiendo cómo cuando j = i, 2i, 3i ... el último forciclo se ejecuta n veces. Supongo que simplemente no entiendo cómo llegamos a esa conclusión en base a la ifdeclaración.

Editar: Sé cómo calcular la complejidad de todos los bucles, excepto por qué el último bucle se ejecuta i veces en función del operador mod ... Simplemente no veo cómo es i. Básicamente, ¿por qué no puedo j% i subir a i * i en lugar de i?

Etiquetemos los bucles A, B y C:

int sum = 0;
// loop A
for(int i = 1; i < n; i++) {
    // loop B
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            // loop C
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

• El bucle A itera O ( n ) veces.
• Loop B itera O ( i ² ) veces por iteración de A . Para cada una de estas iteraciones:
  • j % i == 0 se evalúa, lo que lleva O (1) tiempo.
  • En 1 / i de estas iteraciones, el bucle C itera j veces, haciendo O (1) trabajo por iteración. Como j es O ( i ² ) en promedio, y esto solo se hace para las iteraciones 1 / i del bucle B, el costo promedio es O ( i ²  /  i ) = O ( i ).

Multiplicando todo esto juntos, obtenemos O ( n  ×  i ²  × (1 +  i )) = O ( n  ×  i ³ ). Como i es en promedio O ( n ), este es O ( n ⁴ ).

La parte difícil de esto es decir que la ifcondición solo es cierta 1 / i de las veces:

Básicamente, ¿por qué no puedo j% i subir a i * i en lugar de i?

De hecho, jsube j < i * i, no solo sube j < i. Pero la condición j % i == 0es verdadera si y solo si jes un múltiplo de i.

Los múltiplos de identro de la gama son i, 2*i, 3*i, ..., (i-1) * i. Hay i - 1de estos, por lo que se alcanza el ciclo C a i - 1pesar de los i * i - 1tiempos de iteración del ciclo B.

• El primer ciclo consume niteraciones.
• El segundo ciclo consume n*niteraciones. Imagina el caso cuando i=n, entonces j=n*n.
• El tercer ciclo consume niteraciones porque se ejecuta solo iveces, donde iestá limitado nen el peor de los casos.

Por lo tanto, la complejidad del código es O (n × n × n × n).

Espero que esto te ayude a entender.

Todas las otras respuestas son correctas, solo quiero enmendar lo siguiente. Quería ver si la reducción de las ejecuciones del bucle k interno era suficiente para reducir la complejidad real a continuación. O(n⁴).Entonces escribí lo siguiente:

for (int n = 1; n < 363; ++n) {
    int sum = 0;
    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++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n⁴ = " + hypCubic + ", rel = " + relative);
}

Después de ejecutar esto, se hace evidente que la complejidad es de hecho n⁴. Las últimas líneas de salida se ven así:

n = 356: iterations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

Lo que esto muestra es que la diferencia relativa real entre n⁴la complejidad real y este segmento de código es un factor asintótico hacia un valor cercano 0.124...(en realidad 0,125). Si bien no nos da el valor exacto, podemos deducir lo siguiente:

La complejidad del tiempo es n⁴/8 ~ f(n)donde festá su función / método.

• La página de wikipedia sobre la notación Big O establece en las tablas de 'Familia de las notaciones de Bachmann-Landau' que ~el límite definido de los dos lados del operando es igual. O:

  f es igual a g asintóticamente

(Elegí 363 como límite superior excluido, porque n = 362es el último valor para el que obtenemos un resultado razonable. Después de eso, superamos el espacio largo y el valor relativo se vuelve negativo).

El usuario kaya3 descubrió lo siguiente:

La constante asintótica es exactamente 1/8 = 0.125, por cierto; Aquí está la fórmula exacta a través de Wolfram Alpha .

Eliminar ify módulo sin cambiar la complejidad

Aquí está el método original:

public static long f(int n) {
    int sum = 0;
    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++;
                }
            }
        }
    }
    return sum;
}

Si usted está confundido por el ify módulo, sólo puede refactorizar a la basura, con jsaltar directamente de ia 2*ia 3*i...:

public static long f2(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < i * i; j = j + i) {
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Para que sea aún más fácil calcular la complejidad, puede introducir una j2variable intermedia , de modo que cada variable de bucle se incremente en 1 en cada iteración:

public static long f3(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j2 = 1; j2 < i; j2++) {
            int j = j2 * i;
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Puede usar la depuración o la vieja escuela System.out.printlnpara verificar que el i, j, ktriplete sea siempre el mismo en cada método.

Expresión de forma cerrada

Como lo mencionaron otros, puede usar el hecho de que la suma de los primeros n enteros es igual a n * (n+1) / 2(ver números triangulares ). Si usa esta simplificación para cada ciclo, obtiene:

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

Obviamente, no es la misma complejidad que el código original, pero devuelve los mismos valores.

Si googleas los primeros términos, puedes notar que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731aparecen en "Números de Stirling del primer tipo: s (n + 2, n)". , con dos 0s agregados al principio. Significa que sumes el número de Stirling del primer tipo s(n, n-2) .

Echemos un vistazo a los dos primeros bucles.

El primero es simple, está pasando de 1 a n. El segundo es más interesante. Va de 1 a 1 al cuadrado. Veamos algunos ejemplos:

e.g. n = 4    
i = 1  
j loops from 1 to 1^2  
i = 2  
j loops from 1 to 2^2  
i = 3  
j loops from 1 to 3^2  

En total, los i and j loopscombinados tienen 1^2 + 2^2 + 3^2.
Hay una fórmula para la suma de los primeros n cuadrados n * (n+1) * (2n + 1) / 6, que es aproximadamente O(n^3).

Tienes un último k loopque recorre de 0 a jif y solo if j % i == 0. Como jva del 1 al i^2, j % i == 0es cierto para los itiempos. Como la i loopiteración termina n, tienes uno extra O(n).

Entonces tienes O(n^3)de i and j loopsy otro O(n)de k looppara un gran total deO(n^4)