Algoritmos

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ón de 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 este tema 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 la eficiencia 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 criterios para 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 en cada 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 se harí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 de que 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

...