La complejidad de los algoritmos

He trabajado con mis alumnos de programación un tema tan interesante como la complejidad de los algoritmos. Algo realmente importante en los tiempos que corren y donde la optimización por parte de algoritmos complejos, implica reducciones de tiempo y costes para procesos como búsquedas, recomendaciones o predicciones. Pero empecemos desde el principio. ¿Qué es un…


He trabajado con mis alumnos de programación un tema tan interesante como la complejidad de los algoritmos. Algo realmente importante en los tiempos que corren y donde la optimización por parte de algoritmos complejos, implica reducciones de tiempo y costes para procesos como búsquedas, recomendaciones o predicciones.

Pero empecemos desde el principio. ¿Qué es un algoritmo?

Un algoritmo es un conjunto de pasos o procedimientos utilizados para resolver un problema. Es un proceso bien definido que toma alguna entrada, realiza ciertas operaciones en la entrada y produce alguna salida. Los algoritmos son una parte importante de la informática y se utilizan para realizar una amplia variedad de tareas, desde cálculos simples hasta análisis de datos complejos e inteligencia artificial.

Y su complejidad

La complejidad de un algoritmo es una medida de cuán eficiente es el algoritmo para resolver el problema. En otras palabras, es una medida de cuánto tiempo y espacio (memoria) requiere el algoritmo para producir una solución.

En matemáticas, la complejidad se estudia a menudo en el contexto de los algoritmos. Esto se debe a que muchos problemas matemáticos se pueden resolver mediante algoritmos, y la eficiencia de estos algoritmos es un factor importante en su utilidad en la práctica.

Hay varias formas de medir la complejidad de un algoritmo. Uno de los más comunes es contar el número de operaciones básicas (como sumas o multiplicaciones) que realiza el algoritmo. Esto se conoce como la complejidad temporal del algoritmo.

Otra forma de medir la complejidad es contar la cantidad de memoria (en bytes o bits) que requiere el algoritmo. Esto se conoce como la complejidad espacial del algoritmo.

Las complejidades de tiempo y espacio de un algoritmo se pueden expresar utilizando la notación O grande. Esta notación proporciona una forma de comparar la complejidad de diferentes algoritmos. Por ejemplo, un algoritmo con una complejidad temporal de O(n) se considera más eficiente que un algoritmo con una complejidad temporal de O(n^2), porque crece a un ritmo más lento a medida que aumenta el tamaño de entrada.

En general, el objetivo del diseño de algoritmos es encontrar algoritmos que sean eficientes y fáciles de implementar. Esto implica un compromiso entre la complejidad del tiempo y el espacio, así como otros factores como la simplicidad y la mantenibilidad.

En general, el estudio de la complejidad de los algoritmos es una parte importante tanto de las matemáticas como de la informática. Nos ayuda a comprender las limitaciones de los algoritmos y las compensaciones involucradas en la resolución de problemas complejos.

El valor ya no está en hacer un programa que realice cierta tarea, porque probablemente haya una IA que pueda diseñarte un código para esa cierta tarea en un tiempo extremadamente bajo, pero si tiene un valor añadido que nosotros podamos optimizar ese algoritmo para mejorar sus tiempos de ejecución y costes computacionales.

Para explicar esto en el aula me he basado en los algoritmos de búsqueda en listas ordenadas, algo relativamente sencillo, pero que cuando el número de datos es exponencialmente alto los costes de tiempo empiezan a ser importantes para tener en cuenta.
Para demostrarlo creamos un script (os adjunto abajo) que generaba una lista de 9 millones de números entre 1 y 15 millones, el cual posteriormente elegía un número aleatorio para buscarlo en esa lista, podía estar o no, y demostramos como un algoritmo tradicional, el cual va mirando elemento por elemento hasta que lo encuentra, es mucho más lento e irregular que un algoritmo de búsqueda binaria (adjunto gráfica), el cual va dividiendo la lista en dos y preguntando al número del medio cual es mayor y se queda solo con la parte de la lista donde pertenece nuestro numero buscado.

Esto técnicamente se conoce como comparar un algoritmo de complejidad O(n) (tradicional) con otro de O(log(n)) (binario) donde n es el número de elementos en la lista.

Me parece muy interesante acercar este tipo de prácticas al aula porque de manera visual podemos entender donde realmente podemos sacar un valor añadido a la programación, más allá de «picar» un código y ejecutarlo, en este mundo actual de #inteligenciaartificial

Mi siguiente reto compararlo con el Algoritmo de Grover en computación cuántica, donde se complejidad baja de O(n) a O(Raiz cuadrada(n))…pero ojo en una lista desordenada 😉

Os comparto un video tutorial donde os explico la elaboración de la práctica