Saltar al contenido
Topos Uranos
Español

El costo de un algoritmo

Resumen

Hasta aquí el curso juzgó los algoritmos por una sola pregunta: ¿hacen lo que dicen? Esta clase añade la segunda, que decide si un programa correcto sirve en la práctica: ¿cuánto cuesta? El costo se mide primero sin reloj, contando cuántas veces se ejecuta la operación dominante, y resulta ser una función del tamaño nn de los datos. Lo que importa de esa función no es su valor para un nn dado, sino cómo crece: una tabla de nn, nlog⁡nn \log n, n2n^2 y 2n2^n muestra que las diferencias entre algoritmos, invisibles con diez datos, se vuelven abismos con un millón. La notación OO se presenta como abreviatura de esos órdenes de crecimiento, sin definición formal, con ejemplos ya vistos en el curso: Euclides, logarítmico; la suma de un vector, lineal; comparar todos los pares, cuadrático; Fibonacci ingenuo, exponencial. Después se mide con el reloj de <chrono>, std::chrono::steady_clock, y se aprende por qué una sola medida engaña, por qué se mide con optimización y sin detectores, y cómo se contrasta una medida con una predicción: al duplicar nn, un algoritmo lineal duplica su tiempo y uno cuadrático lo cuadruplica.

Objetivos de aprendizaje

  1. Contar las operaciones dominantes de un algoritmo con uno o dos bucles en función del tamaño nn de los datos.
  2. Clasificar un algoritmo como constante, logarítmico, lineal, nlog⁡nn \log n o cuadrático, y predecir cómo cambia su tiempo al duplicar nn.
  3. Medir el tiempo de ejecución con std::chrono::steady_clock y comparar la medida con la predicción.
  4. Elegir entre dos algoritmos para un tamaño de datos dado, justificando la elección con el orden de crecimiento.

Contar operaciones

La segunda pregunta

Las clases Diseñar bucles correctos y Recursión enseñaron a probar que un algoritmo es correcto: que termina y que su resultado cumple la poscondición. Ahora bien, la clase Algoritmos numéricos mostró dos pruebas de primalidad igualmente correctas, una con unas nn divisiones y otra con unas n\sqrt{n}, y la clase Recursión, dos maneras correctas de calcular F30F_{30}, una con 2 692 5372\,692\,537 llamadas y otra con 29 sumas. Si esto es así, la corrección no basta para elegir: entre dos algoritmos correctos, uno puede responder en un instante y el otro no terminar antes de que la respuesta deje de importar. La segunda pregunta que se hace a un algoritmo es, por tanto, cuánto cuesta.

El costo podría medirse con un reloj, y la cuarta sección lo hará. Pero el tiempo de una ejecución depende de la máquina, del compilador, de sus opciones y de lo que el computador esté haciendo al mismo tiempo; de él no se sigue nada sobre el algoritmo en otra máquina. Lo que no depende de nada de eso es el número de pasos que el algoritmo da. De ello se sigue la primera decisión de esta clase: medir el costo contando, y dejar el reloj para comprobar la cuenta.

El tamaño y la operación dominante

Contar todos los pasos (cada suma, cada comparación, cada incremento del índice, cada acceso a la memoria) sería tedioso e inútil, porque casi todos acompañan a uno principal en proporción fija. Se elige, por tanto, la operación dominante: la que se ejecuta al menos tantas veces como cualquier otra, salvo un factor constante, y que por eso representa a todas. En una suma de los elementos de un vector es la suma; en la búsqueda de un máximo, la comparación; en una prueba de primalidad, la división. El número de veces que se ejecuta se expresa en función del tamaño de la entrada, que se llama nn: el número de elementos del vector, el número que se prueba, el número de cifras.

Un bucle simple que recorre un vector de nn elementos y hace con cada uno una cantidad fija de trabajo ejecuta su operación dominante nn veces. El máximo de un vector no vacío, en cambio, empieza con el primer elemento como candidato y compara cada uno de los demás: n−1n - 1 comparaciones. La diferencia entre nn y n−1n - 1 es real, pero, como se verá en la tercera sección, no cambia nada de lo que importa.

El peor caso

Algunos algoritmos no ejecutan siempre el mismo número de operaciones con datos del mismo tamaño. La búsqueda de un valor en un vector, recorriéndolo hasta encontrarlo, hace una sola comparación si el valor está en la primera posición y nn si no está. Para hablar de su costo se elige una de las dos situaciones, y la elección habitual es el peor caso: el número máximo de operaciones entre todas las entradas de tamaño nn. La razón es la misma por la que un contrato se escribe para todas las entradas que cumplen la precondición: el peor caso es una garantía, y el mejor caso, una esperanza. De modo que la búsqueda secuencial cuesta nn comparaciones en el peor caso, y cuando esta clase dice «el costo» sin más, dice el del peor caso.

Bucles anidados

La clase Bucles enseñó a contar las vueltas de dos bucles anidados. Si el interior hace siempre mm vueltas por cada una de las nn del exterior, el cuerpo interno se ejecuta n⋅mn \cdot m veces. Si el interior depende del exterior, se suma fila por fila. El caso que más aparece al trabajar con colecciones es el de todos los pares: comparar cada elemento con cada uno de los que le siguen, como cuando se busca si un vector tiene repetidos.

Programa en C++
#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} comparaciones; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}
Salida
n =     10:         45 comparaciones; n(n - 1)/2 = 45n =    100:       4950 comparaciones; n(n - 1)/2 = 4950n =   1000:     499500 comparaciones; n(n - 1)/2 = 499500n =  10000:   49995000 comparaciones; n(n - 1)/2 = 49995000

El contador ocupa el lugar de la comparación que el algoritmo real haría. En la vuelta ii del exterior, el interior va de i+1i + 1 a n−1n - 1 y hace n−1−in - 1 - i vueltas; de modo que el total es (n−1)+(n−2)+⋯+1+0(n - 1) + (n - 2) + \cdots + 1 + 0, la suma de la clase Bucles:

∑i=0n−1(n−1−i)=n(n−1)2\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

La salida confirma la fórmula para cada tamaño. El contador es long long porque desde nn de unos sesenta y cinco mil el número de pares supera el máximo de int, y la fórmula multiplica después de convertir por la misma razón: el contador de un algoritmo cuadrático desborda mucho antes que los datos.

Obsérvese ya lo que la tercera sección generalizará: al multiplicar nn por 10, las comparaciones se multiplican por casi 100. Con diez datos, 45 comparaciones; con diez mil, casi cincuenta millones.