Análisis de algoritmos para niños

Figura 1: En la figura se muestra la comparación de pasos realizados por los algoritmos de búsqueda lineal y la búsqueda binaria, representados en magenta y cian, respectivamente. En el ejemplo, ambos algoritmos se utilizan para buscar la entrada "Morin, Arthur" en una lista ordenada de 33 nombres. Como la búsqueda lineal ignora el orden de la lista toma 28 pasos para encontrar la entrada, mientras que, la búsqueda binaria lo hace en 5 pasos dado que aprovecha el orden de las entradas.

El término análisis de algoritmos fue acuñado por Donald Knuth y se refiere al proceso de encontrar la complejidad computacional de un algoritmo que resuelva un problema computacional dado, con el objetivo de proveer estimaciones teóricas de los recursos que necesita. Usualmente, los recursos a los cuales se hace referencia son el tiempo (complejidad temporal) y el almacenamiento (complejidad espacial). Mientras que la complejidad temporal involucra determinar una función que relaciona la longitud o el tamaño de la entrada del algoritmo con el número de pasos que realiza, la complejidad espacial busca la cantidad de ubicaciones de almacenamiento que utiliza. Distintos algoritmos pueden utilizarse para resolver un mismo problema y a su vez los algoritmos pueden estudiarse de forma independiente del lenguaje de programación a utilizar y de la máquina donde se ejecutará. Esto significa que se necesitan técnicas que permitan comparar la eficiencia de los algoritmos antes de su implementación.

Relevancia

En la práctica el análisis de algoritmos es importante porque el uso accidental o no intencional de un algoritmo ineficiente puede afectar significativamente el rendimiento de un sistema. En aplicaciones de tiempo real, un algoritmo que tarda demasiado en ejecutarse puede hacer que sus resultados sean obsoletos o inútiles. Un algoritmo ineficiente también puede terminar requiriendo una cantidad antieconómica de potencia de cálculo o almacenamiento para funcionar, volviéndolo prácticamente inútil.

Véase también

En inglés: Analysis of algorithms Facts for Kids

• Donald Knuth
• Algoritmos
• Teoría de la complejidad computacional
• Teorema maestro
• Optimización de software
• Complejidad temporal