Eficiencia de los algoritmos

EFICIENCIA

1. La eficiencia de los algoritmos

Cuando vamos a construir una casa, o un puente o a reparar el coche pedimos presupuesto, tenemos en cuenta el tipo de materiales que se van a utilizar, el tiempo que se requerirá, el coste de los materiales, el de las horas de trabajo, y en general que cubra todos los requisitos que necesitamos a un coste razonable.
En funciónde todos estos aspectos, decidiremos si el proyecto que nos presentan nos parece bien. Puede ser muy barato pero no cubrir todas las necesidades que tenemos, o ser muy completo pero precisar demasiado tiempo en estar terminado.
En el campo de la computación cuando tenemos que resolver un problema, es posible que estén disponibles varios algoritmos, y deseemos seleccionar el mejor. En estetema trataremos de determinar matemáticamente la cantidad de recursos necesarios para cada algoritmo en función del tamaño de los casos considerados.
El análisis de los algoritmos tiene sentido tanto como paso previo a la realización de un programa o a posteriori, después de haber realizado la implementación.
Antes de decidirse a empezar a programar el estudio previo del cálculo de laeficiencia permite determinar si un algoritmo es suficientemente “bueno”. También nos ofrecerá la posibilidad de decidir ante dos algoritmos que resuelven el mismo problema, cuál de ellos programamos. El estudio a posteriori tiene sentido para comprobar si el comportamiento empírico coincide con el teórico o para encontrar la causa del mal funcionamiento de un programa.
Hay dos criteriospara medir la eficiencia de un algoritmo: espacio de memoria y tiempo que necesita para ejecutarse, a estas dos medidas las llamamos medidas de complejidad. La primera se mide teniendo en cuenta el número de variables, tamaño y número de estructuras de datos y, en general, las necesidades de memoria. El segundo se mide a partir del número de acciones elementales realizadas por el procesador encada una de las ejecuciones.

Estas medidas cambian de una ejecución a otra dependiendo de la entrada, no es lo mismo calcular la media de 5 enteros que la de 1000. Por tanto, el tiempo de ejecución de un algoritmo depende de, o es función del tamaño de la entrada. Con los requerimientos de memoria ocurre lo mismo, vamos a centrarnos en la medida del tiempo, la del espacio de memoria seharía de una manera similar.

Podemos creer que los computadores son increíblemente rápidos y que en realidad el tiempo no es un problema. Esta creencia es falsa, pues existen problemas para los que los algoritmos conocidos tardarían millones de años en solucionarlos, incluso problemas para los que no existe una solución computable, como se vio en el tema 1 de este curso.

El hecho deque las computadoras sean cada vez más y más rápidas, no debe llevar a la conclusión de que no merece la pena invertir tiempo en buscar algoritmos mas eficientes, y pesar (de forma equivocada) que problemas que hoy necesitan muchas horas dentro de unos años se podrán resolver en pocos minutos. Por muy rápidas que puedan llegar a ser las máquinas del futuro, un algoritmo ineficiente seguirá siendoineficiente.

Supongamos que para un problema concreto tenemos un algoritmo cuyo tiempo de ejecución crece exponencialmente con la entrada y tenemos una computadora que es capaz de resolver ese problema con ese algoritmo para una entrada de tamaño n en 10-4 * 2n. Para una entrada de tamaño 10 el algoritmo tardaría 10-4 * 210 segundos, aproximadamente una décima de segundo, una de tamaño20 requeriría 10-4 * 220segundos, unos 2 minutos, y una de tamaño 38, 10-4 * 238 segundos, tendríamos que esperar un año para ver el resultado.
Si conseguimos una máquina 100 veces más rápida, será capaz de resolver el ejemplar de tamaño 10, en 10-6 * 210 segundos, pero en un año sólo lograría resolver el problema para una entrada de tamaño 45. En cambio si conseguimos un algoritmo...