``Java int suma = 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++) { suma++; } } } }
No entiendo cómo cuando j = i, 2i, 3i... el último bucle `for` se ejecuta n veces. Supongo que no entiendo cómo llegamos a esa conclusión basándonos en la sentencia `if`.
Edición: Sé cómo calcular la complejidad de todos los bucles, excepto por el hecho de que el último bucle se ejecuta i veces basándose en el operador mod... Simplemente no veo cómo es i. Básicamente, ¿por qué j % i no puede llegar a i * i en lugar de i?
Vamos a etiquetar los bucles A, B y C:
int suma = 0;
// bucle A
for(int i = 1; i < n; i++) {
// bucle B
for(int j = 1; j < i * i; j++) {
if(j % i == 0) {
// bucle C
for(int k = 0; k < j; k++) {
suma++;
}
}
}
}
j % i == 0
se evalúa, lo que lleva O(1) tiempo.Multiplicando todo esto, obtenemos O(n × i2 × (1 + i)) = O(n × i3). Como i es en promedio O(n), esto es O(n4).
La parte complicada de esto es decir que la condición "si" sólo se cumple 1/i de las veces:
Básicamente, ¿por qué j % i no puede llegar a i * i en lugar de i?
De hecho, j
llega hasta j < i * i
, no sólo hasta j < i
. Pero la condición j % i == 0
es verdadera si y sólo 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.
n*n
iteraciones. Imagina el caso en que i=n
, entonces j=n*n
.n
iteraciones porque se ejecuta sólo i
veces, donde i
está limitado a n
en el peor caso.Así, la complejidad del código es O(n×n×n×n).
Espero que esto te ayude a entenderlo.
Todas las demás respuestas son correctas, sólo quiero corregir 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 de O(n⁴).
Así que escribí lo siguiente:
para (int n = 1; n < 363; ++n) {
int sum = 0;
for(int i = 1; i < n; ++i) {
para(int j = 1; j < i * i; ++j) {
si(j % i == 0) {
para(int k = 0; k < j; ++k) {
suma++;
}
}
}
}
largo cúbico = (largo) Math.pow(n, 3);
largo hipCúbico = (largo) Math.pow(n, 4);
doble relativo = (doble) (suma / (doble) hipCúbico);
System.out.println("n = " + n + ": iteraciones = " + suma +
", n³ = " + cúbico + ", n⁴ = " + hipCúbico + ", rel = " + relativo);
}
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: iteraciones = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iteraciones = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iteraciones = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iteraciones = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iteraciones = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iteraciones = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iteraciones = 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 alrededor de "0.124..." (en realidad 0.125). Aunque no nos da el valor exacto, podemos deducir, lo siguiente:
La complejidad temporal es "n⁴/8 ~ f(n)` donde "f" es su función/método.
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, excedemos el espacio largo y el valor relativo se vuelve negativo).
El usuario kaya3 averiguó 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.
Veamos los dos primeros bucles.
El primero es sencillo, va de 1 a n. El segundo es más interesante. Va de 1 a i 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 bucles i y j
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)
.
Tienes un último "bucle k" que va de 0 a "j" si y sólo si "j % i == 0". Como j
va de 1 a i^2
, j % i == 0
es cierto para i
veces. Como el bucle i
itera sobre n
, tienes un O(n)
extra.
Así que tienes O(n^3)
de los bucles i y j
y otro O(n)
del bucle k
para un total de O(n^4)
.
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ás confundido por el "si" y el "módulo", puedes refactorizarlos, con "j" saltando directamente de "i" a "2i" a "3i"... :
Para facilitar aún más el cálculo de la complejidad, puedes introducir una variable intermedia "j2", de modo que cada variable del 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;
}
Puedes usar la depuración o la vieja escuela System.out.println
para comprobar que i, j, k
triplete es siempre el mismo en cada método.
Como ya se ha mencionado, se puede utilizar el hecho de que la suma de los primeros n
números enteros es igual a n * (n+1) / 2
(ver números triangulares). Si usas esta simplificación para cada bucle, obtienes :
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 buscas en Google los primeros términos, puedes notar que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731
aparecen en "Números de Stirling de la primera clase: s(n+2, n).", con dos 0
s añadidos al principio. Significa que "suma" es el número de Stirling de la primera clase s(n, n-2)
.