big o - que - ¿Cuál es el Big-O de un bucle anidado, donde el número de iteraciones en el bucle interno está determinado por la iteración actual del bucle externo?

iteraciones anidadas

Question

¿Cuál es la complejidad de tiempo de Big-O de los siguientes bucles anidados?

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

¿Sería O (N ^ 2) todavía?

Answer 1

AFAIL, comenzando desde el bucle interno a través de los externos es una forma adecuada para el cálculo de la complejidad del bucle anidado.

Answer 2

Es N al cuadrado si ignoras System.out.println. Si supone que el tiempo empleado en esto será lineal en su producción (que bien puede no ser, por supuesto), sospecho que terminará con O ((N ^ 2) * log N).

Menciono que esto no es quisquilloso, sino solo señalar que no solo se deben tener en cuenta los bucles obvios cuando se trabaja en la complejidad, sino que también se debe tener en cuenta la complejidad de lo que se llama.

Answer 3

Sí, sería N al cuadrado. El número real de pasos sería la suma de 1 a N, que es .5 * (N - 1) ^ 2, si no me equivoco. Big O solo tiene en cuenta el exponente más alto y ninguna constante, y por lo tanto, sigue siendo N al cuadrado.

Answer 4

Sí, sigue siendo O (n ^ 2), tiene un factor constante más pequeño, pero eso no afecta la notación O.

Answer 5

Sí. Recuerde la definición de Big-O: O (f (n)) por definición dice que el tiempo de ejecución T (n) ≤ kf (n) para alguna constante k . En este caso, el número de pasos será (n-1) + (n-2) + ... + 0 , que se reordena a la suma de 0 a n-1; esto es

T (n) = (n-1) ((n-1) +1) / 2 .

Reorganiza eso y puedes ver que T (n) siempre será ≤ 1/2 (n²); por la definición, así T (n) = O (n²) .

Answer 6

Si tuvieras N = 10, tus iteraciones serían: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (esto es: diez iteraciones más nueve iteraciones más ocho iteraciones ... etc.).

Ahora, necesita encontrar en la suma cuántas veces puede obtener una N (10 en el ejemplo):

1: (10), 2: (9 + 1), 3: (8 + 2), 4: (7 + 3), 5: (6 + 4). Que es 5 veces ... y descansa 5 iteraciones.

Ahora sabes que tienes cinco decenas + 5:

10 (5) + 5

En términos de f (n) (o N), podemos ver fácilmente que esto sería:

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 ... esta es exactamente la complejidad de estos bucles anidados.

Pero, considerando el comportamiento asintótico de Big O, podemos deshacernos de los valores menos significativos de f (n), que son el n único y el denominador.

Resultado: O (n ^ 2)