Eficiencia

Tiempo de ejecución y eficiencia de algoritmos

En esta sección vamos a estudiar algunas formas de medir la eficiencia de nuestros programas en Sage, y a estudiar la complejidad de las operaciones usuales en Sage.

Medir de forma precisa este tiempo no es una tarea trivial, y los resultados pueden variar sensiblemente de un ordenador a otro. La cantidad de factores que pueden influir en el tiempo de ejecución es muy larga:

• algoritmo usado
• sistema operativo
• velocidad del procesador, número de procesadores y conjunto de instrucciones que entiende
• cantidad de memoria RAM, y caché, y velocidad de cada una
• coprocesador matemático, GPU
• ...

Incluso en la misma máquina, el mismo algoritmo tarda algunas veces mucho más tiempo en dar el resultado que otras, debido a factores como el tiempo que consumen las otras aplicaciones que se están ejecutando, o si hay suficiente memoria RAM en el momento de ejecutar el programa.

Nuestro objetivo es comparar sólo los algoritmos , intentando sacar conclusiones independientes de la máquina.

Un mismo algoritmo se puede llamar con distintos datos de entrada. Nuestro objetivo es estudiar el tiempo de ejecución como función del “tamaño” de los datos de entrada . Para ello usamos dos técnicas:

• Medir tiempos de ejecución de los programas con datos de entrada de distintos tamaños
• Contar el número de operaciones que realiza el programa

Usar el siguiente código para medir la velocidad con la que procede el algoritmo