Codzy

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)

Empezar la lección