Introducción

Un programa no es otra cosa más que un algoritmo escrito en un lenguaje de programación que puede ser compilado y ejecutado por una computadora. Por lo tanto, aprender a programar incluye aprender a desarrollar algoritmos que den solución a un problema concreto para posteriormente traducirlos al lenguaje de programación de tu preferencia.

Los problemas computables suelen tener suelen tener una cantidad diversa de posibles soluciones y es tarea del programador encontrar la más eficiente posible. Por lo tanto, comprender los fundamentos para el análisis y diseño de algoritmos te darán las herramientas para diferenciar entre buenos y malos algoritmos, así como diseñar siempre la mejor opción posible.

Explicación

Un algoritmo es un conjunto de instrucciones no ambiguas que, dado un conjunto inicial de condiciones, puede ser ejecutada en una secuencia predeterminada para alcanzar una meta teniendo un claro conjunto de condiciones que le permiten terminar (Ahmad, 2020).

Un buen algoritmo debe tener tres características: exactitud, mantenibilidad y eficiencia (Stephens, 2019). Es decir, un algoritmo que no produce resultados exactos no es un algoritmo confiable, aunque en este apartado cabe la excepción de problemas probabilísticos donde los algoritmos que ofrecen resultados con un cierto porcentaje de precisión y resultan ser aceptables en este contexto.

En ocasiones se puede ver algoritmos sumamente intrincados y complicados que a final de cuentas ofrecen un resultado exacto. Sin embargo, si piensas a futuro, un algoritmo con esas características será difícil de mantener; cuando un algoritmo es simple, claro y directo es más fácil para otros programadores hacer correcciones, mejoras o cualquier modificación en general. Es, por lo tanto, una característica muy deseable que ayuda a medir la calidad de un algoritmo. Esto último no significa que los algoritmos difíciles o intrincados no sean útiles o no deban existir, solo que la simplicidad siempre aportará valor agregado.

Finalmente, la eficiencia. Esta suele ser la característica más valorada de un algoritmo y por lo que una gran cantidad de desarrolladores invierten bastante tiempo en desarrollar algoritmos lo más eficiente posible, y aunque un algoritmo produzca el resultado más preciso o sea el más limpio, claro y legible, no tiene mucho sentido si este algoritmo tarda horas o días en terminar su ejecución o si, por otro lado, consume tanta memoria que es imposible de correr en una computadora.

La eficiencia es medida por el manejo de los recursos en la computadora y los dos recursos principales en una computadora son el espacio (la memoria) y el tiempo de ejecución.

Al analizar la eficiencia de un algoritmo se suelen hacer preguntas del tipo: ¿qué pasa se duplica el tamaño de los datos a procesar?, ¿esto duplica el tiempo de ejecución?, ¿el tiempo de ejecución se mantiene constante?, ¿el tiempo crece de manera exponencial?, etc. La misma pregunta se puede hacer para la memoria, cualquier otro recurso que maneje el programa.

También es común preguntarse para un algoritmo cuál es el peor escenario posible, cuál es el escenario en el cual muestra su mejor desempeño y cuál es su desempeño promedio.

Complejidad de algoritmos (Big O, Big Omega, Big Theta) 

Para realizar este tipo de estimaciones se ha desarrollado de notación asintótica que permite realizar un análisis de los algoritmos de una manera general y dar una buena idea de su desempeño con grandes cantidades de datos.

Su nombre proviene del hecho de que las estimaciones se realizan de manera general sin contabilizar puntualmente cada una de las instrucciones que ejecutará el algoritmo. Asimismo, no es tan relevante el tiempo real de ejecución, pues esto varía de una computadora a otra; una vez implementado el algoritmo, dependerá de la velocidad de la computadora de la velocidad, de su conexión a Internet y de otros factores externos al algoritmo que podrán alterar su desempeño real, todas ellas cosas que no son medibles de manera anticipada.

La notación asintótica describe mediante una función matemática el desempeño de un algoritmo. Se realiza un conteo de las operaciones que este ejecuta y se mide su desempeño en diferentes escenarios, y se representa frecuentemente mediante una letra O mayúscula seguida de una función matemática entre paréntesis. Por ejemplo, O(N) indica que el tiempo de ejecución o memoria crece de manera directa conforme crece la cantidad de datos en una relación uno a uno.

Hay cinco reglas para el cálculo del desempeño de un algoritmo usando la notación Big O (Stephens, 2019), siendo N el tamaño de los datos a procesar.

Ilustración 1. Reglas para calcular el desempeño de un algoritmo.

En la práctica se vuelve especialmente útil identificar las familias de algoritmos por su estructura general, lo que facilita su clasificación y la toma de decisiones sobre su posible uso en una solución determinada. 

Identificar algoritmos con complejidad lineal 

La función matemática que describe su desempeño es f(N) = N. Son algoritmos cuyo número de operaciones crece de manera directamente proporcional al tamaño de los datos a procesar. Es decir, si hay 10 datos a procesar se ejecutarán 10 operaciones, si los datos a procesar son 1000 se realizarán, 1000 operaciones, si los datos a procesar son 4 millones se realizarán 4 millones de operaciones y así, sucesivamente.

Para identificarlos fácilmente puedes ver que para cada elemento se realiza una operación.

Estos algoritmos tienen generalmente una estructura iterativa que recorre todos y cada uno de los elementos de una colección. Por ejemplo:

Para un conjunto de datos N={1, 2,…100}

Ilustración 2. Algoritmo para leer e imprimir los elementos de un arreglo.

Tabla 1. Ejemplo de algoritmo de complejidad lineal.

Identificar algoritmos con complejidad cuadrática 

La función matemática que describe su desempeño es f(N) = N². Son algoritmos cuyo número de operaciones crece en relación cuadrática, es decir, para 10 elementos de realizan 100 operaciones, para 50 elementos se realizan 250 operaciones, para 100 elementos se realizan 10000 operaciones y así, sucesivamente.

Estos algoritmos se identifican fácilmente porque para cada elemento dentro de una colección N realizan N operaciones y de ahí su complejidad O(N x N) u O(N²).

Estos algoritmos generalmente cuentan con una estructura iterativa dentro de otra en la que ambos índices recorren la totalidad de los elementos. Por ejemplo:

Para un conjunto de datos N={1, 2,…100}

Ilustración 3. Algoritmo de complejidad cuadrática.

Tabla 2. Ejemplo de algoritmo de complejidad cuadrática.

Identificar algoritmos con complejidad logarítmica 

La función matemática que describe su desempeño es f(N) = log(N). Estos algoritmos tienen como característica que el número de elementos a procesar se reduce por mitad en cada iteración. Así, para un número de elementos inicial de 32, quedarán 16 en la segunda, 8 en la tercera, 4 en la cuarta, 2 en la quinta y 1 en la sexta. Es decir, se procesan 32 elementos en solo 6 iteraciones, y es justamente esto lo que representa un logaritmo, 2⁵ = 32 (recordemos que los índices comienzan en 0), y log₂(32) = 5.

Una manera sencilla de identificarlos es cuando se observa una estructura iterativa que no se procesan todos los elementos, sino que en cada iteración el campo de búsqueda se reduce a la mitad. Como ejemplo de esto se tiene la búsqueda binaria (desarrollada más adelante).

Análisis de algoritmos de complejidad lineal 

La práctica hace a maestro y, por ello, te será de gran utilidad estudiar algoritmos ya conocidos para entender su estructura y funcionamiento, así como escenarios típicos en donde se aplican.

El primer grupo corresponde a algoritmos de complejidad lineal.

Encontrar un elemento dentro de un arreglo 

Una de las operaciones básicas que se pueden realizar dentro de una lista de elementos es la de buscar un elemento, y la búsqueda lineal es la más simple de todas, pues se analiza cada elemento de la lista comparando cada uno de ellos hasta descubrir si el elemento buscado está o no en esta. Los elementos se analizan de izquierda derecha uno a la vez, de tal manera que entre más elementos haya en la lista, más comparaciones se tendrán que hacer. Este algoritmo tiene una complejidad lineal debido a que su tiempo de ejecución crece de manera directamente proporcional con el incremento de los datos a comparar (O(N)).

Dada una lista de elementos:

Ilustración 4. Algoritmo para encontrar un elemento dentro de una lista.

Tabla 3. Demostración de corrida de escritorio de algoritmo de búsqueda lineal con caso de éxito.

Tabla 4. Demostración de corrida de escritorio de algoritmo de búsqueda lineal con caso de fracaso.

Encontrar el elemento más pequeño y el más grande en un arreglo 

Otra operación básica dentro de una lista de elementos es la de encontrar el más pequeño o el más grande de ellos.

En el caso de tener una lista de elementos no ordenada se vuelve inevitable el revisar cada uno de ellos para identificar cuál es el más grande o el más pequeño. Esto produce un algoritmo de complejidad lineal (O(N)) pues al igual que en el caso anterior el tiempo de ejecución crece de manera proporcional al número de elementos dentro de la lista.

El principio detrás este algoritmo es el de asignar al primer valor de la lista el título del elemento más grande y comenzar a comparar los siguientes elementos, uno a la vez, en caso de encontrar un elemento más grande. Este se asume como el más grande de todos y se continua con el resto; este proceso continúa de manera sucesiva hasta alcanzar el final de la lista. Una vez recorridos todos los elementos se tendrá identificado al elemento más grande o pequeño de todos.

Dada una lista de elementos:

Ilustración 5. Algoritmo para encontrar el valor máximo dentro de una lista.

Tabla 5. Demostración de corrida de escritorio de algoritmo para encontrar el número más grande en una lista.

Sumar los números de un arreglo 

Para sumar todos los números de un arreglo es necesario recorrer posición en la lista e irlos sumando. Por sus características, este algoritmo es también de complejidad lineal ya que, a mayor número de elementos en la lista, mayor será el número de operaciones a realizar.

Dada una lista de elementos:

Ilustración 6. Algoritmo en pseudo código para sumar todos los números de una lista.

Tabla 6. Demostración de corrida de escritorio de algoritmo para sumar los números de una lista.

Análisis de algoritmos de complejidad cuadrática

Al inicio podrá parecer que los algoritmos de complejidad cuadrática son muy ineficientes, sin embargo, es útil estudiarlos para comprender sus casos de uso, así como su implementación, por otro lado, existen escenarios en los que por su naturaleza no puede reducir la complejidad computacional y los algoritmos de complejidad cuadrática resultan ser la mejor opción.

Algoritmos de ordenamiento 

Los algoritmos de ordenamiento cuentan una gran variedad de alternativas para realizar la misma tarea. Por ello resulta especialmente útil estudiarlos, ya que podemos ver cómo para una misma tarea se puede desarrollar algoritmos con complejidades similares con diferentes operaciones.

• Ordenamiento burbuja (bubble sort) 

El ordenamiento burbuja (bubble sort, por su nombre en inglés) es el más simple y lento de los algoritmos utilizados para ordenamiento. Está diseñado de tal manera que en cada iteración el elemento más grande de la lista es empujado hacia el extremo derecho y su complejidad media es cuadrática (O(N²)).

El principio básico de este algoritmo es el de comparar elementos adyacentes y, en el caso de que el elemento de la izquierda sea más grande que el de la derecha, los intercambia de lugar. De esta manera, los elementos más grandes son empujados una posición a la vez hacia la derecha, haciendo un efecto de “burbujeo”.

Dada una lista de elementos:

Ilustración 7. Algoritmo Burbuja para ordenar una lista de números.

Tabla 7. Demostración de corrida de escritorio de algoritmo burbuja.

• Ordenamiento de selección (selection sort) 

Está algoritmo es una mejora al ordenamiento burbuja, dado que reduce el número de intercambios entre números dentro de la lista.

Este algoritmo realiza únicamente un intercambio en cada iteración, en lugar de ir empujando cada elemento hacia la derecha una posición, a la vez determina cuál es el elemento más grande disponible y lo ubica en la posición de extrema derecha, en la siguiente iteración encuentre siguiente elemento más grande disponible y lo ubica una posición antes del elemento más grande y así, sucesivamente.

Ilustración 8. Algoritmo Selección para ordenar una lista de números.

Tabla 8. Demostración de corrida de escritorio de algoritmo de selección.

• Ordenamiento de inserción (insertion sort) 

La idea detrás del ordenamiento inserción es la de tomar un elemento de la lista, sacarlo, encontrar su posición final y, posteriormente, insertarlo; es de esta acción que toma su nombre. De los algoritmos de ordenamiento estudiados es el más eficiente. Sin embargo, su desempeño promedio sigue siendo cuadrático (O(N2)).

Dada una lista de elementos:

Ilustración 9. Algoritmo Inserción para ordenar una lista de números.

Tabla 9. Demostración de corrida de escritorio de algoritmo de inserción.

Análisis de algoritmos de complejidad logarítmica 

Los algoritmos de complejidad son bastante poderosos, ya que estos reducen significativamente el número de operaciones a realizar con referencia al número de elementos del procesar. Conocer su funcionamiento te dará herramientas para el desarrollo de algoritmos eficientes cuando un escenario compatible se te presente.

Algoritmo de búsqueda binaria 

Este algoritmo permite encontrar un valor dentro de una lista ordenada de números en un tiempo logarítmico (con un logaritmo base 2), debido a que el universo de búsqueda se reduce a la mitad en cada iteración. Para entenderlo, analiza el siguiente pseudocódigo (Heineman, 2021):

Dada una lista de elementos:

Ilustración 10. Algoritmo de búsqueda binaria.

Tabla 10. Demostración de corrida de escritorio de algoritmo de búsqueda binaria, caso de éxito.

Tabla 11. Demostración de corrida de escritorio de algoritmo de búsqueda binaria, caso de fracaso.

Cierre

El análisis y diseño de algoritmos es un tema sumamente basto y en este apartado has aprendido las bases. Esto solo significa que queda un largo camino por recorrer y que tus habilidades deberán ir creciendo, conforme crece tu experiencia.

El conocimiento base de los algoritmos te dará un punto de partida para el diseño de tus propios programas, pero siempre puedes ahondar más conforme tu experiencia te permita comprender temas cada vez más complejos. No sientas agobio ante la gran cantidad de técnicas existentes; recuerda que es un tema que te acompañará en todo momento y que el mejorar tus habilidades te hará mejor profesional.

Checkpoint

Asegúrate de:

• Entender qué es un algoritmo, cuáles son sus características y cómo se mide su desempeño para desarrollar mejores y más eficientes algoritmos propios.
• Identificar la estructura base de los algoritmos de complejidad lineal, cuadrática y logarítmica para poder realizar estimaciones sobre su desempeño y determinar la mejor alternativa disponible.
• Interpretar algoritmos e implementarlos en lenguaje Java para llevarlos a la práctica.

Bibliografía

• Ahmad, I. (2020). 40 Algorithms Every Programmer Should Know. Estados Unidos: Packt Publishing.
• Heineman, G. (2021). Learning Algorithms. Estados Unidos: O'Reilly Media, Inc.
• Stephens, R. (2019). Essential Algorithms. Estados Unidos: Wiley.