resumen

Capítulo 7

Análisis de Algoritmos

7.1 Competencia específica a desarrollar

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

7.2 Actividades de aprendizaje

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

7.3 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 un algoritmo de solución, que es un conjunto de instrucciones mediante las cuales se indica la forma de resolver un determinado problema.

Unavez 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, sies 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 conlas 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és de 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étodode 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 valores iniciales 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 problemao 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 contar todas las instrucciones ejecutadas por el programa, que dependen del lenguaje de programación y del estilo del programador. Sin embargo, la medida quese 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 de datos.

A final de cuentas, se requiere medir la eficiencia del método empleado por el algoritmo, entendiendo por eficiencia, los recursos de unalgoritmo 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 de mensajes pasados, el número de accesos de disco, etc. (para el tiempo); así como la cantidad de memoria usada, en otras palabras, en qué forma son...