Análisis de algoritmos

¿Que es un algoritmo?


Es un método para resolver un problema mediante una serie de pasos definidos, precisos y finitos.


¿A que nos referimos con análisis de algoritmos?

El análisis de algoritmos es una parte de suma importancia que pertenece a la teoría de Complejidad computacional, provee estimaciones teóricas para los recursos que necesita cualquier Algoritmo que sea capaz de resolver un problema computacional dado. Caracteriza el algoritmo en términos de cantidad de computación y memoria que requeriremos para llegar a la solución de un problema.

Calidad de los algoritmos


Basándonos en la información proporcionada por la dra. Schaeffer, la calidad de los algoritmos se esta medida en:

• Tiempo total de computación

1. Determinar que operaciones que se emplean y su costo relativo.
2. Determinar numero de transiciones que tomara la Maquina de Turing que ejecuta el algoritmo.

• Cantidad de memoria utilizada

1. Cuantas y que tamaño de variables vamos a utilizar
2. Encontrar la posición extrema a la derecha que se llega a visitar en la cinta de Maquina de Turing durante la ejecución.

En caso de encontrar el algoritmo expresado en pseudocódigo, no tenemos la necesidad de convertirlo a Maquina de Turing, lo que tenemos que hacer es contar la cantidad de las operaciones básicas que puede tener nuestro algoritmo, podemos encontrarnos con algunas de estas:

• Aritmética simple
• Lógica simple
• Comparaciones simples
• Asignaciones simples
• Salto

Instancia


La palabra instancia significa solicitud o insistencia. Una instancia tiene elementos de entrada y de salida.


Para cada problema podemos encontrar varias soluciones, que son los datos que podemos tomar como entrada en nuestro problema.


También existen ciertas dificultades para implementar estas estancias, no todas las instancias son iguales en términos de dificultad de su resolución, el tamaño de la instancia afecta, al igual que su estructura.


Ademas la teoría clásica de la complejidad computacional se plantea en términos del tamaño de las instancias.


La manera más fácil y confiable para calcular el tamaño de una instancia es convertir todo en binario y después contar los bits. 


Complejidad cumpotacional


La complejidad cumpotacional clasifica los algoritmos en buenos o malos, también los problemas en la forma de poder resolverlos.


Complejidad:

• Temporal: Tiempo requerido de un algoritmo para encontrar la solución. 

• Espacial: Almacenamiento requerido por un algoritmo para encontrar una solución. 

Fuente: http://es.wikipedia.org/wiki/An%C3%A1lisis_de_algoritmos