Diseño y Análisis de Algoritmos, Código y más: Cotas Inferiores de un Algoritmo

¿Qué es un algoritmo?

La definición más general, es que un algoritmo es simplemente una secuencia de pasos, que seguidos de forma precisa producen un resultado predecible, y que son aplicables a problemas similares.

Una manera de explicarlo es con la metáfora de las recetas de cocina. Cada receta es un algoritmo, que contiene los pasos para preparar un plato. Si una persona conoce y ha seguido muchas recetas, tendrá a sus disposición un arsenal de “conocimiento” y “experiencia” que le permitirán atacar problemas nuevos, como por ejemplo tener que cocinar con las limitaciones de una cocina/despensa en particular y un número de comensales. De la misma forma, un programador que haya estudiado algoritmos comunes y cómo analizarlos, tendrá a su disposición una mayor caja de herramientas a la hora de enfrentar problemas lógicos, llevarlos a código y analizar su eficiencia.

¿Notación Asintótica?

Hemos quedado en que los algoritmos son secuencias de pasos que podemos seguir para solucionar problemas concretos. Pero no sólo eso, sino que también hemos dicho que son como “recetas”, y esto quiere decir que no son “cualquier” secuencia de pasos, sino una que has sido “probada” (funciona correctamente) y “perfeccionada” (es eficiente).

Este último punto, la eficiencia, nos lleva a la temible “notación asintótica”. Siendo un concepto teórico, no voy a entrar en los detalles matemáticos, eso lo pueden encontrar en los links al final, si no ver algunos ejemplos que puedan servir para ilustrar los conceptos en líneas generales.

En computación, la notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).

Desde este punto de vista, el algoritmo más eficiente posible sería aquel en el que el número de operaciones llevadas a cabo no varíe según crezca la entrada.

Notaciones comunes en orden de eficiencia: