Introducción al Análisis de Algoritmos

El análisis de algoritmos puede ser un tema difícil de entender. En la mayoría de ocasiones nos mandan de frente a una serie de símbolos y notaciones que no necesariamente son de lo más amigables y sin una buena explicación previa, inclusive pueden generar repulsión al tema.

En este BlogPost comenzamos un paso antes, definiendo los conceptos básicos de tiempo de ejecución y hablamos sobre cómo comparar algoritmos. Una vez que tengas esto claro, en otro seguiremos con la notación utilizada, también, estamos a punto de lanzar el Curso de Algoritmos con C al que puedes acceder haciendo click aquí.

Resuelve el cubo de rubik: utiliza algoritmos.

¿Sabes qué es el análisis en tiempo de ejecución y de qué depende?

Es el proceso de determinar o calcular cómo se incrementa el tiempo de procesamiento conforme incrementa el tamaño de los datos de entrada, es decir conforme el problema se hace más complejo, aquí vale la pena destacar que el problema podría tener diversos tipos de entradas de datos y te comparto los más comunes para que logremos entender más este punto:

Tenemos la herramienta que es el análisis del tiempo de ejecución, ahora veamos los parámetros con los que mediremos nuestros algoritmos hablemos de 3 ideas:

¿Tiempo que tarda en ejecutarse?

R: No es la métrica ideal, pues los tiempos de ejecución son específicos para una computadora y van a variar según el hardware que tengamos a disposición por poner sólo un ejemplo, un programa se ejecutaría mucho más rápido en un i7 7700hq que en un i7 7600u y eso que son dos CPUs de los más recientes y de modelos “parecidos” imagínate lo complejo que sería tener una medición para tu algoritmos en todos los hardwares, difícil, ¿cierto?

¿Número de instrucciones a ejecutar?

R: Tampoco es una buena medida, pues el número de instrucciones varía según el lenguaje de programación que se esté utilizando y el estilo del programador mismo, por eso no podemos guiarnos únicamente por esta métrica.

¿Entonces cuál es la solución ideal?

R: Las matemáticas tienen una forma de describir diversos fenómenos del día a día como la transferencia de calor entre dos cuerpos (física AKA, matemáticas aplicadas) por poner un ejemplo, y en el estudio de algoritmos también nos ayudan, en este caso al medir el tiempo de ejecución como una función del tamaño de la entrada.

Si quieres aprender más, no dudes en entrar al Curso de Algoritmos con C dónde aprenderás a hacer el análisis y la implementación de los algoritmos más utilizados, en vivo, junto a la increíble comunidad de estudiantes de Platzi.