2.2. ¿Qué es análisis de algoritmos?¶
Es muy común que los estudiantes principiantes de ciencias de la computación comparen sus programas entre sí. También usted puede haber notado que es común que los programas de computadora se vean muy similares, especialmente los más simples. A menudo surge una pregunta interesante. Cuando dos programas resuelven el mismo problema pero se ven diferentes, ¿es un programa mejor que el otro?
Con el fin de responder esta pregunta, tenemos que recordar que hay una diferencia importante entre un programa y el algoritmo subyacente que el programa está representando. Como dijimos en el Capítulo 1, un algoritmo es una lista genérica, paso a paso, de instrucciones para resolver un problema. Es un método para resolver cualquier caso del problema de tal manera que dada una entrada particular, el algoritmo produzca el resultado deseado. Un programa, por otro lado, es un algoritmo que ha sido codificado en algún lenguaje de programación. Pueden existir muchos programas para el mismo algoritmo, dependiendo del programador y del lenguaje de programación que se esté utilizando.
Para explorar aún más esta diferencia, considere la función que se muestra en el ActiveCode 1. Esta función resuelve un problema familiar: calcular la suma de los primeros n enteros. El algoritmo utiliza la idea de una variable acumuladora que se inicializa en 0. La solución itera entonces a través de los n enteros, agregando cada uno a la variable acumuladora.
Ahora mire la función en el ActiveCode 2. A primera vista puede parecer extraña, pero después de una inspección más profunda se puede ver que esta función está haciendo esencialmente lo mismo que la anterior. La razón por la que esto no es obvio es la deficiente codificación. No usamos buenos nombres de identificación para facilitar la lectura, y usamos una instrucción de asignación extra durante el paso de acumulación que no era realmente necesaria.
La pregunta que planteamos anteriormente consistía en responder si una función es mejor que la otra. La respuesta depende de sus criterios. La función sumaDeN es ciertamente mejor que la función cosa si usted está interesado en la legibilidad. De hecho, probablemente haya visto muchos ejemplos de esto en su curso de programación introductoria, ya que una de los propósitos de dicho curso es ayudar a escribir programas que sean fáciles de leer y de entender. No obstante, en este curso también estamos interesados en caracterizar el propio algoritmo. (Esperamos ciertamente que usted continúe esforzándose por escribir código legible y comprensible.)
El análisis de algoritmos se ocupa de compararlos con base en la cantidad de recursos computacionales que utiliza cada algoritmo. Queremos ser capaces de considerar dos algoritmos y decir que uno es mejor que el otro, porque es más eficiente en su uso de esos recursos o simplemente tal vez porque utiliza una menor cantidad. Desde esta perspectiva, las dos funciones anteriores parecen muy similares. Ambos usan en esencia el mismo algoritmo para resolver el problema de la sumatoria.
En este punto, es importante pensar más en lo que realmente queremos decir con recursos computacionales. Hay dos formas diferentes de ver esto. Una forma es considerar la cantidad de espacio o memoria que un algoritmo requiere para resolver el problema. La cantidad de espacio requerida por una solución suele ser dictada por el caso particular del problema. De vez en cuando, sin embargo, hay algoritmos que tienen requisitos de espacio muy específicos, y en esos casos seremos muy cuidadosos al explicar las variaciones.
Como alternativa a los requerimientos de espacio, podemos analizar y comparar algoritmos basados en la cantidad de tiempo que requieren para ejecutarse. Esta medida se denomina a veces “tiempo de ejecución” o “tiempo de corrida” del algoritmo. Una forma de medir el tiempo de ejecución de la función sumaDeN es hacer un análisis de pruebas de referencia (benchmark). Esto significa que mediremos el tiempo real requerido para que el programa calcule su resultado. En Python, podemos hacer una prueba de referencia de una función observando el tiempo de inicio y el tiempo de finalización con respecto al sistema que estamos utilizando. En el módulo time hay una función llamada time que devolverá el tiempo actual del reloj del sistema medido en segundos desde algún punto de inicio arbitrario. Al llamar a esta función dos veces, al inicio y al final, y luego calcular la diferencia, podemos obtener un número exacto de segundos (fracciones en la mayoría de los casos) de la ejecución.
Programa 1
import time
def sumaDeN2(n):
inicio = time.time()
laSuma = 0
for i in range(1,n+1):
laSuma = laSuma + i
final = time.time()
return laSuma,final-inicio
El Programa 1 muestra la función sumaDeN con las llamadas de temporización incrustadas antes y después de la suma. La función devuelve una tupla que consiste en el resultado y la cantidad de tiempo (en segundos) requerida para el cálculo. Si realizamos 5 llamados a la función, calculando cada vez la suma de los primeros 10,000 enteros, obtendremos lo siguiente:
>>>for i in range(5):
print("La suma es %d y requirió %10.7f segundos"%sumaDeN(10000))
La suma es 50005000 y requirió 0.0018950 segundos
La suma es 50005000 y requirió 0.0018620 segundos
La suma es 50005000 y requirió 0.0019171 segundos
La suma es 50005000 y requirió 0.0019162 segundos
La suma es 50005000 y requirió 0.0019360 segundos
Descubrimos que el tiempo es bastante consistente y que ejecutar ese código toma en promedio alrededor de 0.0019 segundos. ¿Qué pasará si ejecutamos la función sumando los primeros 100,000 enteros?
>>>for i in range(5):
print("La suma es %d y requirió %10.7f segundos"%sumaDeN(100000))
La suma es 5000050000 y requirió 0.0199420 segundos
La suma es 5000050000 y requirió 0.0180972 segundos
La suma es 5000050000 y requirió 0.0194821 segundos
La suma es 5000050000 y requirió 0.0178988 segundos
La suma es 5000050000 y requirió 0.0188949 segundos
>>>
De nuevo, el tiempo requerido para cada ejecución, aunque más largo, es muy consistente, promediando alrededor de 10 veces más segundos. Para n igual a 1,000,000 obtenemos:
>>>for i in range(5):
print("La suma es %d y requirió %10.7f segundos"%sumaDeN(1000000))
La suma es 500000500000 y requirió 0.1948988 segundos
La suma es 500000500000 y requirió 0.1850290 segundos
La suma es 500000500000 y requirió 0.1809771 segundos
La suma es 500000500000 y requirió 0.1729250 segundos
La suma es 500000500000 y requirió 0.1646299 segundos
>>>
En este caso, el promedio vuelve a ser aproximadamente 10 veces el anterior.
Ahora considere el ActiveCode 3, el cual muestra una manera diferente de resolver el problema de la sumatoria. Esta función, sumaDeN3, hace uso de una ecuación cerrada \(\sum_{i=1}^{n} i = \frac {(n)(n+1)}{2}\) para calcular, sin iterar, la suma de los primeros n números enteros.
Si hacemos la misma prueba de referencia para sumaDeN3, usando cinco valores diferentes para n (10,000, 100,000, 1,000,000, 10,000,000 y 100,000,000), obtendremos los siguientes resultados:
La suma es 50005000 y requirió 0.00000095 segundos
La suma es 5000050000 y requirió 0.00000191 segundos
La suma es 500000500000 y requirió 0.00000095 segundos
La suma es 50000005000000 y requirió 0.00000095 segundos
La suma es 5000000050000000 y requirió 0.00000119 segundos
Hay dos cosas importantes que observar acerca de este resultado. En primer lugar, los tiempos registrados anteriormente son más cortos que cualquiera de los ejemplos anteriores. En segundo lugar, son muy consistentes sin importar el valor de n. Parece que sumaDeN3 apenas se ve afectada por el número de enteros que se suman.
Pero, ¿qué nos dice realmente esta prueba de referencia? Intuitivamente, podemos ver que las soluciones iterativas parecen estar haciendo más trabajo ya que algunos pasos del programa se están repitiendo. Ésta es probablemente la razón por la que está tomando más tiempo. Además, el tiempo requerido para la solución iterativa parece aumentar a medida que aumentamos el valor de n. Sin embargo, hay un problema. Si ejecutamos la misma función en una computadora diferente o usamos un lenguaje de programación diferente, es probable que obtengamos resultados diferentes. Podría tomar aún más tiempo ejecutar sumaDeN3 si la computadora fuera una más antigua.
Necesitamos una mejor manera de caracterizar estos algoritmos con respecto al tiempo de ejecución. La técnica de pruebas de referencia calcula el tiempo de ejecución real. Esa técnica en verdad no nos proporciona una medida útil, ya que depende de una máquina, programa, hora del día, compilador y lenguaje de programación en particular. En su lugar, nos gustaría tener una caracterización que sea independiente del programa o de la computadora que se utilice. Esta medida sería entonces útil para juzgar el algoritmo aisladamente y podría utilizarse para comparar algoritmos en diferentes implementaciones.