ALGORITMO

Un algoritmo es el conjunto de operaciones y procedimientos que deben seguirse para resolver un problema. La palabra "algoritmo" deriva del nombre latinizado del gran matemático árabe Mohamed Ibn Moussa Al Kow Rizmi.

En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos se encuentran en los instructivos (manuales de usuario), los cuales muestran algoritmos para usar el aparato en cuestión o incluso en las instrucciones que recibe un trabajador por parte de su patrón.

• Precisión. “Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso”.

• Entrada. “Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinamicamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos específicos de objetos”.

• Salida. “Un algoritmo tiene una o más salidas: cantidades las cuales tienen una relación específica con las entradas”.

• Eficacia. “También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel”.

Entendiendo esto ya estamos un paso mas cerca de ser parte de este proceso.

Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas.

Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán cuando las implementemos, especialmente al atacar problemas "grandes".

La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo se considera farragoso.

Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto difícil de entender.

Por hacer una similitud acerca de lo complicado que es este concepto, la dificultad de la complejidad es -salvando las distancias- como la de la predicción meteorológica: todos intuimos lo complicado que es hacer una predicción meteorológica, miles de datos, fórmulas, modelos y cálculos... sin embargo, cuando un meteorólogo nos explica con algo de gracia la predicción del tiempo, la podemos entender bastante bien. Ya estamos muy acostumbrados a cosas como borrasca, anticiclón, marejadilla, cota de nieve... Lo mismo pasa en cierto modo con la complejidad: enfrentarnos a un algoritmo para hacer un estudio de su complejidad requiere de un gran esfuerzo. Sin embargo, cuando alguien estudia un algoritmo y nos habla de su complejidad, entender el concepto no es tan complicado.

Entender la complejidad es importante porque a la hora de resolver muchos problemas, utilizamos algoritmos ya diseñados. Saber valorar su valor de complejidad puede ayudarnos mucho a conocer cómo se va a comportar el algoritmo e incluso a escoger uno u otro.

Así que en este artículo, nos vamos a dedicar a intentar exponer qué es la complejidad de un algoritmo desde un punto de vista sencillo y sin pretensiones, intentado distinguir qué impacto tiene el que un algoritmo tenga una u otra complejidad. Y, como de costumbre, adoptamos grandes simplificaciones, con el único ánimo de obtener una visión general de los conceptos. En cuanto a cómo obtener la complejidad de un algoritmo, no nos vamos a meter mucho: los formalismos necesarios quedan totalmente fuera del alcance de éste breve artículo divulgativo.