Análisis de complejidad del algoritmo: ¿cuál es la importancia?

Actualmente, se ha hecho más visible la necesidad de contar con algoritmos más eficientes para nuestras aplicaciones, ya sea por la cantidad de datos procesados o por la necesidad de respuestas rápidas. Esto nos lleva a uno de los principales fundamentos del desarrollo de software: analizar la complejidad de los algoritmos.

Es increíble cómo los lenguajes de programación y las plataformas más modernas se encargan del funcionamiento de los algoritmos por nosotros. Aún así, es muy importante saber por qué y cómo funciona nuestro código, ¿no crees?

Entonces, tomemos un ejemplo práctico: imagine que estamos desarrollando una guía telefónica y somos responsables de crear la función de búsqueda de contactos.

Asumiendo que todos los contactos ya están en orden alfabético, ¡manos a la obra!

Búsqueda lineal

Para hacerlo más fácil y evitar errores, desplacémonos por la lista en busca de un contacto. Supongamos que se solicitó el contacto de Wanessa:

Nos encontramos con que hemos repasado toda la lista hasta encontrarlo. Hasta ahora ningún problema, ¿verdad? La solución actual funciona perfectamente y con un rendimiento aceptable. Ahora imagine que nuestra solución se vendió a una empresa multinacional que tiene miles o incluso millones de contactos.

¡Para encontrar a Rodrigo en esta oportunidad, tuvimos que pasar por millones de contactos! ¿Ahora no parece tener tan buen desempeño, verdad?

Búsqueda binaria

Pensemos en una solución mejor. Sabemos que la lista ya está en orden alfabético, entonces, ¿qué tal si la desglosamos? Podemos comparar el contacto que buscamos con el contacto del medio, comprobar la dirección que debemos tomar y eliminar el resto de la lista. Por tanto, seguiremos los pasos descritos para encontrar el contacto de Paula:

Seleccionamos el contacto del medio, Nico, para comparar con el contacto que buscamos, Paula, y descartamos la mitad de la lista en la que estamos seguros de que no estará la persona buscada.

En esta iteración, elegimos nuevamente al contacto en el medio de la lista, Rodrigo, y verificamos en qué dirección debemos ir, descartando la otra mitad. Entonces encontramos a Paula.

¿Y cuál sería la diferencia entre las dos soluciones?

Tenga en cuenta que en la primera solución, independientemente del tamaño de la lista, debemos recorrer todos los contactos hasta encontrar el que queremos. Si tenemos suerte, el contacto que buscamos podría ser el primero de todos. Sin embargo, si no tenemos tanta suerte y buscamos el último contacto, tendremos que recorrer toda la lista, lo que sería el peor de los casos para el algoritmo. Con eso en mente, podemos determinar que nuestra primera solución ejecuta una función que crece linealmente con el tamaño de la lista de contactos.

En la segunda solución, notamos que en cada iteración eliminamos la mitad de la lista, por lo que no es necesario revisarla por completo. De esta forma optimizamos la búsqueda. Esta solución realiza una función que crece a una tasa logarítmica considerando el tamaño de la lista de contactos.

¿Visualizamos la diferencia entre las tasas de crecimiento del algoritmo?

Ahora está claro que la solución logarítmica tiene un desempeño extremadamente más eficiente que la solución lineal, y podemos confirmarlo a través del gráfico anterior, donde el eje de la cantidad de operaciones realizadas por las dos funciones es bastante desigual.

Profundizando un poco más, en una lista con 1 millón de contactos solo es necesario realizar 20 operaciones de comparación hasta dar con el contacto deseado. Con esto podemos empezar a entender cuán importante es el análisis de la complejidad de los algoritmos.

Usamos un ejemplo muy simple, pero imagine tener que desarrollar una función de búsqueda de estudiantes de Alura Latam para que sea posible autenticarse en el sitio web o la aplicación. ¿Qué solución usarías?

¿Te gustó el tema? Tenemos una serie de nuevos artículos que explican más sobre el análisis de la complejidad de los algoritmos. En el siguiente, discutiremos la implementación de los algoritmos de búsqueda explicados anteriormente.

Brendo Rodrigo Souza de Matos

Ingeniero de Software apasionado por lo que hace, amante de los nuevos retos y sediento de conocimiento. Actualmente soy Ingeniero de Software de Plataformas en Méliuz (B3: CASH3) y estoy realizando una Maestría en Ciencias de la Computación en la Universidad Federal de Amazonas.

Este articulo fue adecuado para Alura Latam por: Wilfredo Rojas