Complejidad en tiempo y en espacio
La complejidad mide cómo crece el tiempo (o la memoria) de un algoritmo cuando los datos aumentan. Se escribe con la notación O grande: O(1) constante, O(log n) como la búsqueda binaria, O(n) un bucle simple, O(n²) dos bucles anidados.
La complejidad en espacio mide la memoria usada. A menudo se cambia un poco de memoria por mucha velocidad: buscar en una lista es O(n), pero buscar en un set o un dict es O(1) de media.
def count_steps(n):
steps = 0
for i in range(n):
for j in range(n):
steps += 1
return steps
for n in [10, 20, 40]:
print(n, "->", count_steps(n), "steps")
names = set(["Ana", "Ben", "Chloe"])
print("Ben" in names)