Introducción: análisis de algoritmos

Bien, a continuación hablaremos del análisis de algoritmos que es una técnica utilizada para calcular el costo computacional de diversos algoritmos, mismos que muchas veces realizan la misma tarea, y donde el objetivo es encontrar aquel que requiera de menor labor computacional. Para ello abordaremos en varios post las diferentes técnicas utilizadas, asi que sean pacientes, es necesario que conozcan varios conceptos básicos que trataré de explicar sencillamente a lo largo de varios post.

Primero es necesario entender los siguientes conceptos:

Operador elemental: operación cuyo tiempo de ejecución está delimitado por una constante, donde esta constante depende de la implementación que hayamos hecho del algoritmo (en qué lenguaje, en que máquina…). Por ejemplo, digamos que estamos construyendo un algoritmo cuya función es sumar varios números que están contenidos en un arreglo. Lo que deseamos medir en este caso, es la cantidad de sumas necesarias para obtener el resultado deseado (la suma de todos los números).  Las operaciones de comparación necesarias para llegar al resultado, dado que no son el objetivo de este algoritmo, son consideradas operadores elementales.

Análisis del algoritmo, mejor, medio y peor caso: En el análisis de un algoritmo, no necesariamente hay una respuesta absoluta con respecto a su análisis. Habrá que considerar que podemos analizar el mismo algoritmo utilizando enfoques diferentes. Podemos hacer el análisis basándonos en el mejor de los casos, esto es, cuando el algoritmo ejecuta el menor número de operaciones. Para el mismo algoritmo, podemos basarnos en el peor de los casos, que es cuando el algoritmo realiza el mayor número de operaciones, por lo que el análisis para el mismo algoritmo en el mejor y peor de los casos, será diferente. Y bueno finalmente, está el análisis del caso medio, que creo que ya se entiende.

Para entender lo anterior, pongamos el primer ejemplo:

El código de arriba corresponde a un algoritmo de ordenamiento, donde t es un arreglo que contiene los elementos a ordenar. Supongamos que t={1,2,3,4,5}, si analizamos el comportamiento del algoritmo podemos observar que dado que los números ya están ordenados, el algoritmo no tendrá que hacer ningún intercambio y por tanto nos ahorramos muchas operaciones.

Por el contrario, si t={5,4,3,2,1}, entonces habría que recorrer todo el arreglo, e intercambiar cada uno de los números para lograr que queden ordenados. Por lo tanto no nos ahorramos ninguna operación, ya que se ejecutan todas las posibles en el algoritmo.

En estos dos ejemplos, el primero se considera el mejor de los casos, debido a que se ejecuta el menor número de operaciones posibles en el algoritmo, por otro lado, el segundo ejemplo es considerado el peor de los casos debido a que ejecuta el mayor número de operaciones posibles.

Ahora bien, en caso de que t={5,2,3,1,4}, no se ejecuta el menor número de operaciones posibles pero tampoco el mayor número, así que por ello es considerado el caso medio.

En el próximo post, estudiaremos la notación asintótica y como establecer el orden de un algoritmo en términos de ella.

cualquier duda, favor de dejar en comentarios =).