¿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?
¿Cuál es la complejidad temporal 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);
}
}
¿Seguiría siendo O(N^2) ?
Sí, sigue siendo O(n^2), tiene un factor constante más pequeño, pero eso no afecta la notación O.
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 reorganiza en la suma de 0 a n-1; esto es
T(n)=(n-1)((n-1)+1)/2 .
Reorganice eso y podrá ver que T(n) siempre será ≤ 1/2(n²); por definición, entonces T(n) = O(n²) .
Tracemos el número de veces que se ejecuta cada bucle en cada iteración.
for (int i = 0; i < N; i++) { // outer loop
for (int j = i + 1; j < N; j++) { // inner loop
System.out.println("i = " + i + " j = " + j);
}
}
En la primera iteración del bucle externo (i = 0), el bucle interno se ejecuta N - 1veces.
En la segunda iteración del bucle externo (i = 1), el bucle interno se ejecuta N - 2veces.
En la tercera iteración del bucle exterior (i = 2), el bucle interior se ejecuta N - 3veces.
. . .
En la N - 2tercera iteración del bucle externo (i = N - 3), el bucle interno se ejecuta 2veces.
En la N - 1tercera iteración del bucle externo (i = N - 2), el bucle interno ejecuta 1el tiempo.
En la última ( Nésima) iteración del bucle externo (i = N - 1), el bucle interno se ejecuta 0veces.
Por lo tanto, el número total de veces que se ejecuta este código es
N - 1+ N - 2+ N - 3+ … + 2+ 1+0
= 0+ 1+ 2+ … + N - 3+ N - 2+N - 1
Sustituyendo esto en la fórmula de suma de números naturales,
=(N - 1)((N - 1) + 1) / 2
=(N - 1)(N) / 2
=((N^2) - N) / 2
= O(N^2), asumiendo que System.out.printlnse ejecuta en tiempo constante O(1).
——————
Además, echa un vistazo a estos
- https://stackoverflow.com/a/71805214/17112163
- https://stackoverflow.com/a/71146522/17112163
- https://stackoverflow.com/a/69821878/17112163
- https://stackoverflow.com/a/72046825/17112163
- https://stackoverflow.com/a/72046933/17112163
