Complejidad de un algoritmo: contar pasos

La complejidad de un algoritmo mide cuántos pasos da cuando los datos crecen. Sirve para saber si un programa seguirá siendo rápido con diez veces más datos.

Una universidad guarda 1.000 nombres de alumnos. Buscar uno mirando la lista de principio a fin puede costar 1.000 pasos. Con 10.000 alumnos costará 10.000. Otra forma de buscar apenas notaría el cambio. Esta lección te enseña a contar y a ver la diferencia.

Para comparar algoritmos no medimos segundos. Contamos pasos. Un paso es una operación sencilla: comparar dos números, sumar o guardar un valor.

Contamos solo lo que se repite con los datos. Si el programa mira cada precio una vez, hay un paso por precio. Si la lista crece, el número de pasos crece con ella. Ese número depende de n, el tamaño de la entrada.

# Buscar el precio más alto de una lista, contando los pasos.
prices = [12, 7, 30, 18, 25]
steps = 0
biggest = prices[0]
for price in prices:
    steps = steps + 1
    if price > biggest:
        biggest = price
print("Precio más alto:", biggest)
print("Pasos:", steps)
# Añade cinco precios más a la lista y vuelve a ejecutar.

Un algoritmo constante da siempre los mismos pasos, como mirar el primer elemento. Uno lineal da un paso por dato. Uno cuadrático compara cada dato con todos los demás, así que da n por n pasos.

Uno logarítmico parte los datos por la mitad en cada paso. Con un millón de datos solo da 19 pasos.

python3 -c "import math; print(math.floor(math.log2(1000000)))"

python3 -c "print(1000000 ** 2)"

Un bucle dentro de otro repite el bucle de dentro una vez por cada vuelta del de fuera. Si comparas cada línea de un registro con todas las que van después, haces n por n menos uno, entre dos, comparaciones.

Con cuatro líneas son 6. Con diez son 45. El crecimiento sigue siendo cuadrático.

# Comparar cada línea del registro con todas las que van después.
lines = ["a", "b", "c", "d"]
steps = 0
for i in range(len(lines)):
    for j in range(i + 1, len(lines)):
        steps = steps + 1
print("Comparaciones:", steps)
# Cambia la lista a seis líneas y mira cómo salta el número.

La orden time mide los segundos de una sola ejecución en una sola máquina. Otro ordenador, u otro momento, da otro número.

Los pasos no cambian: son los mismos en cualquier máquina. Por eso un algoritmo se compara por sus pasos. El siguiente Run imprime la suma, y después tres líneas llamadas real, user y sys, con tiempos que cambian cada vez.

time python3 -c "print(sum(range(1000000)))"