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. El análisis de los algoritmos es importante debido a que, en más de una ocasión tendremos varios algoritmos entre los cuales elegir para realizar exactamente la misma tarea pero con diferente método, y deberemos saber cuál de todos ellos requiere de menor costo computacional (el que se encuentre en menor orden, después hablaremos de esto). 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, supongamos que estamos analizando un algoritmo y encontramos que para resolver un caso de cierto tamaño se requieren a adiciones, b multiplicaciones y c instrucciones de asignación. Supongamos tambien que se sabe que las adiciones no pueden tomar mas de t_a microsegundos, que una multiplicación no requiere más de t_b microsegundos, y una instrucción de asignación no requiere más de t_c microsegundos, donde t_a,t_b y t_c son constantes que dependen de la máquina que estemos usando. Dado que el costo de cada una de estas operaciones está delimitado por una constante, pueden ser consideradas operaciones elementales. Entonces el tiempo total t necesario para ejecutar nuestro algoritmo estará acotado por:

t ≤ at_a + bt_b + ct_{c                         (1)}

t ≤ max (t_a, t_b, t_c) x (a,b,c)            (2)

Esto es: se toma el mayor de los costos de las diferentes operaciones elementales, y se asume que las demás operaciones elementales también tienen ese costo. Dado que el costo exacto de cada operación elemental en realidad no es tan importante, simplificaremos diciendo que cada operación elemental tiene un costo unitario. Sin embargo, existen algunas excepciones, por ejemplo: la suma de aquellos números que no alcanzan a ser representados de manera simple en una computadora (numero muy grandes, con decimales muy largos y pequeños, entre otros), y que requieren de un trato especial al sumarlos, restarlos, dividirlos, multiplicarlos… en estos casos, estas operaciones no son consideradas elementales, sin embargo, dejaremos estos casos fuera del alcance de este blog.

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 =).