O(n²)
Python · Unidad 22: Complejidad
- Plan completo
- Python
- 8 ejercicios
Comparar todos contra todos es un ciclo dentro de otro sobre la misma lista: n por n pasos.
Esa etiqueta es O(n²), y crece feo: con 10 nombres son 100 pasos, con 100 ya son 10 000.
def parejas(nombres):
pasos = 0
for a in nombres:
for b in nombres:
pasos += 1
return pasos
print(parejas(["Ana", "Luis"]))Imprime
4
El resto de la explicación está en la lección, que es del plan completo.
Ejercicios de esta lección
Se hacen en la app, que los corrige al momento y explica por qué.
1. Predice la salida
¿Qué imprime este código?
2. Opción múltiple
Una función O(n²) hace 10 000 pasos con n = 100. ¿Cuántos hará con n = 200?
3. Predice la salida
¿Qué imprime este código?
4. Completa el código
Completa para que cada par se cuente una sola vez.
5. Encuentra el bug
Debería decir cuántas parejas de números iguales hay en la lista, o sea 1. ¿Qué línea tiene el error?
6. Predice la salida
¿Qué imprime este código?
7. Ordena las líneas
Ordena una función O(n²) que diga si hay algún número repetido comparando cada par.
8. Opción múltiple
Las dos cuentan cuántos números distintos hay. ¿Qué etiqueta le toca a cada una?
Se abre en el navegador. Esta lección es del plan completo; la primera unidad de cada curso es gratis.