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 bucle for se ejecuta n veces. Supongo que simplemente no entiendo cómo llegamos a esa conclusión basándonos en la declaración if .
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é j % i no puede subir a i * i en lugar de i?
n iteraciones.n*n iteraciones. Imagine el caso cuando i=n , luego j=n*n .n iteraciones porque se ejecuta solo i veces, donde i está limitado a n en el peor de los casos.Por tanto, la complejidad del código es O(n×n×n×n).
Espero que esto te ayude a entender.
Echemos un vistazo a los dos primeros bucles.
El primero es simple, es un bucle de 1 a n. El segundo es más interesante. Va de 1 a i al cuadrado. Veamos algunos ejemplos:
eg 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 loops combinados 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) .
Tiene un último k loop que pasa de 0 a j si y solo si j % i == 0 . Dado que j va de 1 a i^2 , j % i == 0 es cierto para i veces. Dado que el i loop itera sobre n , tiene un O(n) adicional.
Así que tienes O(n^3) de los i and j loops y otro O(n) del k loop para un gran total de O(n^4)
Identifiquemos 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++; } } } }j % i == 0 , lo que requiere un tiempo O(1).Multiplicando todo esto, obtenemos O( n × i 2 × (1 + i )) = O( n × i 3 ). Dado que i es en promedio O( n ), esto es O( n 4 ).
La parte complicada de esto es decir que la condición if solo es verdadera 1/ i de las veces:
Básicamente, ¿por qué j % i no puede subir a i * i en lugar de i?
De hecho, j sube hasta j < i * i , no solo hasta j < i . Pero la condición j % i == 0 es verdadera si y solo si j es un múltiplo de i .
Los múltiplos de i dentro del rango son i , 2*i , 3*i , ..., (i-1) * i . Hay i - 1 de estos, por lo que el bucle C se alcanza i - 1 veces a pesar de que el bucle B itera i * i - 1 veces.
Todas las demás respuestas son correctas, solo quiero modificar lo siguiente. Quería ver si la reducción de las ejecuciones del k-loop interno era suficiente para reducir la complejidad real por debajo O(n⁴). Así que 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 vuelve obvio 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 el n⁴ real y la complejidad de este segmento de código es un factor asintótico hacia un valor de alrededor de 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 f es su función/método.
~ define que el límite 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 = 362 es el último valor para el que obtenemos un resultado sensato. 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 .
if y modulo 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 está confundido por if y modulo, simplemente puede refactorizarlos, con j saltando directamente de i a 2*i a 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 variable intermedia j2 , de modo que cada variable de ciclo 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 System.out.println de la vieja escuela para verificar que el triplete i, j, k sea siempre el mismo en cada método.
Como 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 tiene la misma complejidad que el código original, pero devuelve los mismos valores.
Si busca en Google los primeros términos, puede notar que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 aparece en "Números de Stirling del primer tipo: s(n+2, n)". , con dos 0 añadidos al principio. Significa que sum es el número de Stirling de primera especie s(n, n-2) .