Estructuras y rendimiento

Python · Unidad 22: Complejidad

x in lista mira uno por uno: en el peor caso recorre toda la lista, O(n).

x in conjunto no recorre nada, porque el valor le dice a Python dónde buscarlo: O(1). Con las llaves de un diccionario pasa lo mismo.

nombres = ["Ana", "Luis", "Sofia"]
amigos = set(nombres)
print("Luis" in nombres)
print("Luis" in amigos)

Imprime

True
True

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
El contador cuenta cuántos números hubo que mirar para encontrar el 7. ¿Qué imprime?
2. Opción múltiple
equipo es una lista con 1000 nombres y socios es un conjunto con esos mismos nombres. ¿Qué diferencia hay entre x in equipo y x in socios?
3. Predice la salida
¿Qué imprime este código?
4. Completa el código
Completa para dejar los socios listos para buscar muchas veces.
5. Ordena las líneas
Ordena una función que cuente cuántos de los números están en el conjunto vistos.
6. Encuentra el bug
Debería decir cuántos nombres distintos hay, o sea 2. ¿Qué línea tiene el error?
7. Predice la salida
Recuerda que fib(5) costó 15 llamadas. ¿Cuántas cuesta fib(10)?
8. Opción múltiple
Cada reto de la app trae una etiqueta: O(1), O(log n), O(n), O(n log n), O(n²) o O(2ⁿ). ¿Qué te dice esa etiqueta?

Se abre en el navegador. Esta lección es del plan completo; la primera unidad de cada curso es gratis.