En general, la complejidad cambiaría de O (n ^ 2) a O (n), pero de manera crucial, esperaría obtener un resultado diferente .
Por ejemplo, supongamos que tenemos este código:
n = 100
para i en rango (n):
imprimir “hola”
para j en el rango (n):
imprimir “hola”
- Cómo detener un algoritmo que alguien más que yo ha establecido en WhatsApp
- ¿Son factibles los problemas NP-difíciles?
- ¿Cómo se ordenan las matrices para que los valores altos y bajos se distribuyan en diagonal?
- ¿Debo usar una matriz o un objeto para implementar una clase de cola de JavaScript?
- ¿Cuánto estrés se le da a los algoritmos y las estructuras de datos en el curso de pregrado en CMI? ¿Se enseña programación competitiva allí?
¿Cuántas veces esperarías ver “hola” impreso en tu pantalla? 100 * 100 + 100 = 10100, ¿verdad?
Ahora, hagamos lo que usted proponga, mueva el bucle interno y haga que se ejecute solo:
n = 100
para i en rango (n):
imprimir “hola”
para j en el rango (n):
imprimir “hola”
Ahora, ¿cuántas veces vemos “hola”? 100 + 100 = 200.
Entonces los resultados son diferentes.
Sin embargo, en la mayoría de los casos, el cálculo interno probablemente sea una función de la variable del bucle interno y la variable del bucle externo. En estos casos, sacar el lazo interno simplemente no tendría ningún sentido.
Por ejemplo:
n = 100
# Versión 1
para i en rango (n):
para j en el rango (n):
hacer algo (i, j)
# Versión 2
para i en rango (n):
pasar
para j en el rango (n):
hacer algo (i, j)
Pero, ¿cuál es exactamente la variable que se supone que soy en la versión 2? No hay una respuesta correcta, por lo que este tipo de técnica no tiene mucho valor para los algoritmos reales.