Fund

Capítulo 7


Análisis de Algoritmos


7.1 Objetivo Educacional

– Comprender la complejidad de los algoritmos e identificar la eficiencia de los mismos

7.2 Competencia específica a desarrollar

– Que el alumno comprenda la complejidad de los algoritmos e identificar la eficiencia de los mismos

7.3 Actividades de aprendizaje

– Generar cuadro comparativo con los tiemposobtenidos en cada método de ordenamiento y búsqueda
– Comentario. Emitir su propia conclusión al observar la complejidad de los algoritmos estudiados y contrastarla con lo que dicen al respecto, los autores citados en las fuentes bibliográficas

7.4 Análisis de Algoritmos

Para procesar una gran cantidad de datos se utiliza una computadora y a través de un lenguaje de programación se establece unalgoritmo de solución, que es un conjunto de instrucciones mediante las cuales se indica la forma de resolver un determinado problema.

Una vez que se ha determinado que el algoritmo es correcto, es necesario determinar la cantidad de recursos computacionales requeridos para tal efecto, como el tiempo de proceso y el espacio de memoria, además de que éste sea sencillo y claro, y por supuesto,que sea el óptimo, es decir, se necesita realizar un análisis del algoritmo.

Se analizan los algoritmos con la intención de mejorarlos, si es posible y de escoger uno de entre varios con los que se podría resolver un problema, utilizando los criterios mencionados de:
1. Corrección
2. Cantidad de trabajo realizado
3. Cantidad de espacio usado
4. Sencillez, claridad
5.Optimidad

los cuales se revisarán enseguida.

Corrección – primeramente para poder determinar que un algoritmo es correcto se deben precisar las entradas con las que se espera que trabaje y el resultado o salida que se espera que produzca con cada entrada, y tratar de demostrar enunciados acerca de las relaciones entre las entradas y las salidas.

Estas demostraciones pueden ser formales a travésde leyes, teoremas, etc. o informales como lo es la aplicación de unos cuantos ejemplos pequeños al algoritmo.

El algoritmo tiene dos aspectos: el método de solución y las instrucciones para ponerlo en práctica, o sea, su implementación, y una vez establecido un método, se implementa en un programa. Se tiene que tener especial cuidado en la verificación de algunos detalles como los valoresiniciales y finales de contadores de ciclos y simulación a mano del algoritmo con unos cuantos ejemplos.

Esto se puede realizar para programas pequeños, pero cuando los programas son grandes y complejos se puede dividir éste en módulos más pequeños e independientes y verificar cada uno de ellos para determinar si es correcto, una vez hecho esto, se puede establecer que el programa es correcto.Cantidad de trabajo realizado – una vez determinado que un algoritmo es correcto, para determinar qué tan buena es la solución que se ha dado a un problema o si hay una mejor forma de resolverlo se debe escoger una medida para comparar dos algoritmos, por ejemplo, se pueden utilizar los tiempos de ejecución reales de dos algoritmos, los cuales varían dependiendo de la computadora; o se pueden contartodas las instrucciones ejecutadas por el programa, que dependen del lenguaje de programación y del estilo del programador. Sin embargo, la medida que se seleccione debe ser independiente de estas problemáticas, además de otros detalles de la implementación como el incremento del índice de un ciclo, el cálculo de los índices de un arreglo y el establecimiento de apuntadores en estructuras dedatos.

A final de cuentas, se requiere medir la eficiencia del método empleado por el algoritmo, entendiendo por eficiencia, los recursos de un algoritmo usados para encontrar una respuesta. Se dice que un algoritmo es eficiente cuando utiliza menos recursos en tiempo y en espacio (memoria), y puede medirse en términos de cálculos teóricos tales como comparaciones o movimiento de datos, el número...