Cuánto tarda un algoritmo: contar pasos

Para comparar dos algoritmos no basta con decir que uno es "más rápido". Hay que decir cuánto crece su trabajo cuando los datos crecen. A eso se le llama eficiencia, y se mide contando pasos.

Una app con 10 usuarios funciona con cualquier programa. Con un millón, solo funciona el que crece despacio.

Un segundo no sirve para comparar. Tu móvil y el ordenador del colegio dan tiempos distintos con el mismo programa, y hasta tu móvil cambia de una vez a otra.

Un paso sí es siempre el mismo. Si el programa compara 173 veces, compara 173 veces en cualquier máquina.

def count_linear(items, target):
    steps = 0
    for item in items:
        steps = steps + 1
        if item == target:
            return steps
    return steps

numbers = list(range(1, 101))
print(count_linear(numbers, 1))
print(count_linear(numbers, 100))
print(count_linear(numbers, 500))

El programa imprime 1, 100 y 100. Si el dato es el primero, es un paso. Si es el último o no está, son 100: tantos como elementos.

Llamamos n al número de elementos. En el peor caso, la búsqueda lineal hace n pasos. Se dice que es de orden n, y se escribe O(n).

No importa si son 173 pasos o 175. Importa cómo cambia el número cuando n crece.

La búsqueda binaria es O(log n): cada paso descarta la mitad. La lineal es O(n). La burbuja es O(n²), que se lee "n al cuadrado": compara casi cada elemento con todos los demás. La mezcla es O(n log n).

docker exec jupyter python3 -c "print([(n, n * (n - 1) // 2) for n in (10, 100, 1000)])"

docker exec jupyter python3 -c "print([(n, n.bit_length()) for n in (10, 100, 1000)])"

El primer Run imprime [(10, 45), (100, 4950), (1000, 499500)]. Con diez veces más datos, la burbuja hace cien veces más comparaciones.

El segundo imprime [(10, 4), (100, 7), (1000, 10)]. La binaria casi no se entera: con mil datos solo hace 10 pasos.

Un bucle dentro de otro repite el de dentro una vez por cada vuelta del de fuera. Por eso la burbuja crece tanto.

Con 4 elementos hace 3 + 2 + 1 = 6 comparaciones. Con 10 hace 9 + 8 + ... + 1 = 45. Ese es el número de parejas distintas.

def count_pairs(n):
    comparisons = 0
    for turn in range(n - 1):
        for at in range(n - 1 - turn):
            comparisons = comparisons + 1
    return comparisons

for n in [4, 10, 100]:
    print(n, count_pairs(n))

docker exec jupyter python3 -c "import csv; h=[int(r['hires']) for r in csv.DictReader(open('hires.csv'))]; print(len(h) * (len(h) - 1) // 2, len(h) * len(h).bit_length())"

El Run imprime 66430 3285. Ordenar los 365 alquileres con la burbuja hace 66430 comparaciones. La mezcla hace unas 3285.

Con una lista de un millón de datos, la burbuja haría unos quinientos mil millones de comparaciones. La mezcla, unos veinte millones.

En el cuaderno, escribe una celda con %timeit para ordenar 1000 números y otra para ordenar 2000. Mira cuánto cambia el tiempo.

Repite la medida y apunta lo que ves. El tiempo cambia de una vez a otra. El número de pasos de la tabla no cambia nunca.