Técnicas De Análisis De Algoritmos

Técnicas de análisis de algoritmos

El análisis de algoritmos es una disciplina en el campo de la computación cuya finalidad es la de medir de forma cuantitativa la cantidad de recursos que un algoritmo necesita para su ejecución.

El análisis de algoritmos tiene como objetivo establecer propiedades sobre la eficiencia permitiendo la comparación entre soluciones alternativas y predecir

los recursos que usarán un algoritmo.

Hay varias razones por las que es deseable analizar el comportamiento de un algoritmo.

1. Analizando se pueden descubrir características generales y particulares de un algoritmo y evaluar la facilidad de emplearlo en una aplicación, o compararlo con otras opciones de algoritmo para la misma aplicación.

2. El análisis de un algoritmo sirve para entender mejor sus propiedades y puede sugerir mejoras posteriores.

3. El análisis puede servir para identificar maneras de sacar las mayores ventajas del ambiente de programación (arquitectura de la computadora, sistema operativo, compilador), que puede tener un efecto significativo en el desempeño del algoritmo.

4. Muchos algoritmos poseen una estructura compleja que despierta interés matemático y permite el desarrollo de teoría útil para otras situaciones (como el análisis de otros algoritmos).

Notación asintótica

Llamamos notación asintótica a la familia de relaciones conocidas como notación de Bachmann-Landau, la cual es usada para describir el tiempo de ejecución de los algoritmos.

Si se conoce el tiempo (o espacio) que utiliza un algoritmo para procesar 50 datos (nombres, números, imágenes), 70 datos, 100, 200, 300 y 500 datos, se puede construir una gráfica que de una idea de cómo se comportará el algoritmo cuando la cantidad de datos siga creciendo. De hecho, es en términos de n datos como nos interesa su comportamiento. Estamos hablando aquí de su comportamiento asintótico.

Eficiencia de algoritmos computacionales

Medida del uso de los recursos computacionales requeridos por la ejecución de un algoritmo en función del tamaño de las entradas. La eficiencia de los algoritmos, principio de invariancia, operaciones con órdenes de complejidad, funciones anónimas, análisis de algoritmos, el caso especial de los algoritmos recursivos, análisis de los algoritmos de ordenación. T(n) Tiempo empleado para ejecutar el algoritmo con una entrada de tamaño n.

Tipos de análisis

¿Cómo medimos el tiempo de ejecución de un algoritmo?

- Mejor caso

En condiciones óptimas (no se usa por ser demasiado optimista).

- Peor caso

En el peor escenario posible (nos permite acotar el tiempo de ejecución).

- Caso promedio

Caso difícil de caracterizar en la práctica.

- Análisis probabilístico

Asume

...