En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas determinados. Las personas empleamos los algoritmos frecuentemente en nuestra vida cotidiana para resolver problemas o tareas sin ser conscientes de ello. En términos de programación, un algoritmo es una secuencia de pasos lógicos que permiten solucionar un problema. En informática se define un algoritmo de programación como una secuencia de pasos ordenados que pueden ser traducidos a un lenguaje informático y que se implementan con el objetivo de que los equipos electrónicos o informáticos realicen determinadas tareas.
Partiendo de un estado inicial y una entrada determinada, la aplicación de los pasos sucesivos de un algoritmo conduce a un estado final que proporciona una solución al problema planteado. Todo algoritmo tiene una entrada, conocida como input y una salida, conocida como output, y entre medias, están las instrucciones o secuencia de pasos a seguir. En el mundo de la programación, todo programa o sistema operativo funciona a través de algoritmos, escritos en un lenguaje de programación que el ordenador pueda entender para ejecutar los pasos o instrucciones de una forma automatizada.
Un algoritmo se puede concebir como una función que transforma los datos de un problema (entrada) en los datos de una solución (salida). Los datos se pueden representar a su vez como secuencias de bits, y en general, de símbolos cualesquiera. Como cada secuencia de bits representa a un número natural, entonces los algoritmos son en esencia funciones de los números naturales en los números naturales que sí se pueden calcular.
En los últimos tiempos, debido al auge y desarrollo de la inteligencia artificial y a que los algoritmos son capitales para su funcionamiento, se vienen utilizando con cierta sinonimia la expresión «inteligencia artificial» y el término «algoritmo» en el lenguaje común o atécnico. En este sentido, por ejemplo, la Estrategia de Inteligencia Artificial de la Unión Europea parece identificarlos cuando indica que: «En lo que atañe a la utilización de la IA, los entornos ricos en datos también brindan más oportunidades. Ello se debe a que los datos son los que permiten al algoritmo aprender acerca de su entorno e interactuar con él». Así, es frecuente encontrar expresiones como "ética de los algoritmos" o "gobernanza de los algoritmos" para hacer referencia a determinados requisitos de cumplimiento ético y jurídico que normas como el Reglamento (UE) 2024/1689 de Inteligencia Artificial imponen a los sistemas y modelos de inteligencia artificial.
¿Qué es el Orden de un Algoritmo?
El orden de un algoritmo no mide su rapidez, aunque nos permite ordenar los algoritmos del más eficiente al menos eficiente. El orden mide cuan rápidamente aumenta el tiempo de ejecución de un algoritmo cuando aumenten los datos de entrada. Se puede argumentar que el orden de un algoritmo nos define cuan rápido es. Pero esa visión no es cierta. Por norma general, siempre que sea posible debemos usar un algoritmo del menor orden posible.
Lea también: IVA 21% Excel
Si un algoritmo tiene O(n) significa que el tiempo aumenta linealmente al aumentar los datos de entrada. Es decir, que si para una lista de 100 elementos el algoritmo tarda x segundos, para una lista de 1000 elementos (10 veces más grande) tardará 10 veces más. Por otro lado, si el algoritmo tiene O(n^2) significa que el tiempo aumenta cuadráticamente. En este caso, si para ordenar una lista de 100 elementos el algoritmo tarda x segundos, para una lista de 1000 elementos ¡tardará 100 veces más! Hemos aumentado los datos de entrada en un ratio de 10 y el algoritmo no tarda 10 veces más si no 100 (10^2).
Existen unos algoritmos que desafían al sentido común y son una maravilla: en estos el tiempo aumenta logarítmicamente. Es decir, si para ordenar una lista de 100 elementos el algoritmo tarda x segundos, para ordenar una lista 10 veces más larga tardará… ¡tan solo el doble! Mediante el análisis de algoritmos se puede determinar la complejidad de cada uno de ellos, es decir, el tiempo de ejecución que tendrá ese programa en función de la cantidad de datos de entrada.
Tipos de Complejidad: Temporal y Espacial
Cuando se habla de complejidad se hace referencia, casi todas las veces, a la complejidad temporal. La primera de ellas, determina de una forma exacta el tiempo (donde una posible unidad de medida son los segundos) de ejecución de un algoritmo. No obstante, también existe otro tipo de complejidad: la espacial.
La respuesta a por qué se prioriza la complejidad temporal sobre la espacial la encontramos en la diferencia de costes que existe entre mejorar la capacidad de computación y la de almacenamiento. A día de hoy, es mucho más económico y rentable obtener más espacio en memoria que no mejorar la capacidad de cálculo de un computador. Por otro lado, la complejidad espacial también puede ser medida con exactitud, más no resultará tan interesante y determinante como la temporal.
Factores que Influyen en la Complejidad de un Algoritmo
Para determinar la complejidad de un algoritmo, es importante considerar varios factores:
Lea también: Guía IVA reducido
Cantidad de datos de entrada: No es lo mismo tener que tratar una cantidad de datos pequeña como una cantidad muy grande. Por ejemplo, si hay que buscar un elemento entre un vector de 10 posiciones, en el peor de los casos solo habrá que recorrer 10 posiciones. Sin embargo, si el vector contiene 1000 posiciones, serán 1000.
Estructuras internas del algoritmo: Un algoritmo tendrá mayor complejidad según las estructuras que tenga dentro. Por ejemplo, no es lo mismo ejecutar 10 líneas de código sin ninguna estructura iterativa dentro que hacerlo con un bucle donde esa cantidad de líneas se tendrá que ejecutar múltiples veces.
El computador que lo ejecuta: Un mismo algoritmo con la misma cantidad de datos de entrada puede tardar más en un computador o en otro según los componentes que tenga. Además, también puede darse el caso que un algoritmo tarde un tiempo diferente en un mismo computador según el estado de este, ya que puede darse el caso en que ese computador esté usando gran parte del procesador en otra tarea y destine menos recursos a ejecutar el algoritmo.
El Escenario del Peor Caso
Una vez definidos los elementos que determinan la complejidad, hay que tener en cuenta que un mismo algoritmo puede ejecutar diferente parte del código con estructuras condicionales o, incluso, no iterar siempre las mismas veces una estructura iterativa. Entonces, es necesario hablar de lo que se conoce como el peor caso.
La realidad es que, como ya se ha dicho, no siempre se ejecutarán la misma cantidad de líneas de un mismo algoritmo, como tampoco se van a tener que recorrer la misma cantidad de elementos de un vector en una búsqueda. Por lo tanto, es necesario generalizar este raciocinio para poder determinar la complejidad que tendrá un algoritmo en la mayoría de los casos. Es necesario valorar siempre la eficiencia de un algoritmo en función del peor caso, ya que no tiene sentido valorarla en función de si el elemento está en la primera posición o en el medio, ya que no serán las situaciones más comunes y nada garantiza que el elemento a buscar esté realmente en la lista.
Lea también: ¿Cómo localizar tus XML del SAT?
Por ejemplo, si se parte del vector {1, 2, 3, 4, 5} y se busca el elemento con valor 1, parece claro que lo encontrará en la primera posición y no tendrá que seguir buscando. Siguiendo con el ejemplo propuesto, esta situación se dará cuando el elemento buscado no se encuentre dentro del vector, puesto que, en una situación real, será un caso bastante recurrente.
En el caso de la búsqueda, el elemento a buscar puede que se encuentre en la primera posición, pero también puede ser que esté en medio, al final o que directamente no esté. Entonces, ¿cuál será la complejidad de ese algoritmo? Parece evidente que la cantidad de tiempo de ejecución no va a ser el mismo si se encuentra en la primera posición o en la última. Por ello, hay que determinar un escenario que sea igual para todos los métodos de búsqueda en este caso y que permita dictaminar la cantidad de tiempo máximo que estará en ejecución. Justamente eso es lo que se conoce como el peor caso.
Medición de la Complejidad Temporal
Habiendo citado todas las consideraciones previas, ya se puede empezar a determinar la complejidad temporal de forma exacta. Para ello, se establece un criterio donde se asigna una cantidad de tiempo a cada operación elemental que se realiza. En este caso, para facilitar el cálculo de la complejidad siempre se determina que todas las operaciones llamadas elementales tardan la misma cantidad de tiempo en ser ejecutadas. Normalmente, se suelen determinar con una constante, por ejemplo, kx (donde x es un número natural).
Una vez determinado el coste temporal, habrá que agrupar las operaciones en las constantes que se han citado según la estructura en la cual estén. Para ello, si hay un bucle en el algoritmo, se intentará agrupar todas las operaciones elementales en una única constante que se ejecutará tantas veces como el bucle se itere. Es decir, si el bucle se ejecuta n veces, el valor de la constante k se tendrá que multiplicar por n.
Ejemplo de Complejidad: Algoritmos de Búsqueda
En caso de tener un vector ordenado de elementos donde se quiera buscar en qué posición se encuentra cierto valor, existen múltiples formas de obtenerlo.
Búsqueda Secuencial
Por un lado, la búsqueda secuencial empezará por el inicio o por el final de la lista e irá incrementando o decrementando el índice en el cual va a comprobar si es el valor que está buscando. En el primer caso, el de la búsqueda secuencial, accedería a todos los elementos de la lista. Suponiendo que la cantidad de elementos sea n, tendría n iteraciones.
Búsqueda Binaria o Dicotómica
Por otro lado, la búsqueda binaria o dicotómica empezará su búsqueda por el valor central de la lista e irá descartando mitades. Realizará tal operación de forma iterativa hasta encontrar el valor o determinar que el valor a buscar no se encuentra en la lista. Con lo cual, este método de búsqueda no tendrá que buscar entre todos los elementos de la lista, sino que irá descartando mitades de forma recursiva hasta finalizar. En consecuencia, tardará menos tiempo en ejecutarse y su complejidad es logarítmica: O (log n).
Algoritmos de Ordenación
Los algoritmos de ordenación son un conjunto de instrucciones que toman un arreglo o lista como entrada y organizan los elementos en un orden particular. Las ordenaciones suelen ser numéricas o una forma de orden alfabético (o lexicográfico), y pueden ser en orden ascendente (AZ, 0-9) o descendente (ZA, 9-0). Dado que a menudo pueden reducir la complejidad de un problema, los algoritmos de ordenación son muy importantes en informática. Estos algoritmos tienen aplicaciones directas en algoritmos de búsqueda, algoritmos de bases de datos, métodos divide y vencerás, algoritmos de estructura de datos y muchos más.
Consideraciones al Elegir un Algoritmo de Ordenación
Al elegir un algoritmo de ordenación, se deben hacer algunas preguntas: ¿Cuán grande es la colección que se ordena? ¿Cuánta memoria hay disponible? ¿La colección necesita crecer? Las respuestas a estas preguntas pueden determinar qué algoritmo funcionará mejor para cada situación. Debes determinar cuáles son tus requisitos y considerar las limitaciones de tu sistema antes de decidir qué algoritmo de ordenación usar.
Clasificación de un Algoritmo de Ordenación
Los algoritmos de ordenación se pueden clasificar en función de los siguientes parámetros:
La cantidad de intercambios o inversiones requeridas: Esta es la cantidad de veces que el algoritmo intercambia elementos para ordenar la entrada. La ordenación por selección requiere el número mínimo de intercambios.
El número de comparaciones: Este es el número de veces que el algoritmo compara elementos para ordenar la entrada. Usando la notación Big-O, los ejemplos de algoritmos de ordenación enumerados anteriormente requieren al menos O(nlogn) comparaciones en el mejor de los casos y O(n^2) comparaciones en el peor de los casos para la mayoría de los resultados.
Recursividad: Algunos algoritmos de ordenación, como la ordenación rápida, usan técnicas recursivas para ordenar la entrada. Otros algoritmos de ordenación, como la ordenación por selección o la ordenación por inserción, utilizan técnicas no recursivas. Por último, algunos algoritmos de ordenación, como la ordenación por fusión, utilizan técnicas tanto recursivas como no recursivas para ordenar la entrada.
Estabilidad: Los algoritmos de ordenación estables mantienen el orden relativo de los elementos con valores iguales o claves. Los algoritmos de ordenación inestables no mantienen el orden relativo de los elementos con valores/claves iguales.
Por ejemplo, imagina que tienes el arreglo de entrada [1, 2, 3, 2, 4]. Y para ayudar a diferenciar entre los dos valores iguales, 2 actualicemoslos a 2a y 2b, creando el arreglo de entrada [1, 2a, 3, 2b, 4]. Los algoritmos de ordenación estables mantendrán el orden de 2a y 2b, lo que significa que el arreglo de salida será [1, 2a, 2b, 3, 4]. Los algoritmos de ordenación inestables no mantienen el orden de los valores iguales y el arreglo de salida puede ser [1, 2b, 2a, 3, 4]. La ordenación por inserción, la ordenación por fusión y la ordenación por burbuja son estables. La ordenación en montón y la ordenación rápida son inestables.
Cantidad de espacio adicional requerido: Algunos algoritmos de ordenación pueden ordenar una lista sin crear una lista completamente nueva. Estos se conocen como algoritmos de ordenación en el lugar y requieren un O(1) espacio adicional constante para la ordenación. Mientras tanto, los algoritmos de ordenación fuera de lugar crean una nueva lista durante la ordenación. La ordenación por inserción y la ordenación rápida son algoritmos de ordenación en el lugar, ya que los elementos se mueven alrededor de un punto de pivote y no usan un arreglo separado. Merge sort es un ejemplo de un algoritmo de ordenación fuera del lugar, ya que el tamaño de la entrada debe asignarse de antemano para almacenar la salida durante el proceso de ordenación, lo que requiere memoria adicional.
Algoritmos de Ordenación Comunes
Algunos de los algoritmos de ordenación más comunes y sus características son:
| Algoritmo | Complejidad Temporal (Mejor/Promedio/Peor Caso) | Complejidad Espacial | Estable | En el lugar (In-place) |
|---|---|---|---|---|
| Ordenación de Cubo (Bucket Sort) | No especificado en el texto | No especificado en el texto | No especificado en el texto | No especificado en el texto |
| Ordenación de Conteo (Counting Sort) | O(n+k) / O(n+k) / O(n+k) | No especificado en el texto | No especificado en el texto | No especificado en el texto |
| Ordenación de Inserción (Insertion Sort) | O(n) / O(n*n) / O(n*n) | O(1) | Sí | Sí |
| Ordenación por Montones (Heapsort) | O(nlogn) / O(nlogn) / O(nlogn) | O(1) | No | Sí |
| Ordenación Radix (Radix Sort) | No especificado en el texto | No especificado en el texto | Sí (usa ordenación por conteo estable) | No especificado en el texto |
| Ordenación de Selección (Selection Sort) | O(n^2) / O(n^2) / O(n^2) | O(n) | No | Sí |
| Ordenación de Burbuja (Bubble Sort) | O(n) / O(n^2) / O(n^2) | No especificado en el texto | Sí | No especificado en el texto |
| Ordenación Rápida (Quick Sort) | O(nlog(n)) / O(nlog(n)) / O(n^2) | O(n) (peor caso, para la recursión) | No | Sí |
Ordenación de Cubo (Bucket Sort)
La ordenación de cubos es un algoritmo de ordenación por comparación que opera en elementos dividiéndolos en diferentes cubos y luego ordenando estos cubos individualmente. Cada depósito se ordena individualmente utilizando un algoritmo de ordenación independiente, como la ordenación por inserción, o aplicando el algoritmo de ordenación de cubos de forma recursiva. La ordenación de cubos es principalmente útil cuando la entrada se distribuye uniformemente en un rango.
Ordenación de Conteo (Counting Sort)
El algoritmo de ordenación por conteo funciona creando primero una lista de los conteos u ocurrencias de cada valor único en la lista. Tiene la complejidad de O(n+k), donde k es el elemento máximo del arreglo de entrada. Así, si k es O(n), CountSort se convierte en una ordenación lineal, que es mejor que los algoritmos de ordenación basados en comparación que tienen una complejidad de tiempo O(nlogn).
Ordenación de Inserción (Insertion Sort)
La ordenación por inserción es un algoritmo de ordenación simple para una pequeña cantidad de elementos. En la ordenación por inserción, se compara el elemento clave con los elementos anteriores. Por ejemplo, key se compara con 8. El elemento clave se intercambiará al final de la iteración. Sus propiedades incluyen una complejidad de espacio de O(1), y una complejidad de tiempo de O(n) para el mejor caso (arreglo ya ordenado), O(n*n) para el caso promedio (arreglo ordenado aleatoriamente) y O(n*n) para el peor caso (arreglo ordenado de forma inversa). Es un algoritmo en el lugar y estable.
Ordenación por Montones (Heapsort)
Heapsort es un algoritmo de ordenación eficiente basado en el uso de montones máximos/mínimos. Un montón es una estructura de datos basada en un árbol que satisface la propiedad del montón. Esta propiedad se puede aprovechar para acceder al elemento máximo en el montón en tiempo O (logn) usando el método maxHeapify. Realizamos esta operación n veces, cada vez que movemos el elemento máximo en el montón a la parte superior del montón y lo extraemos del montón y lo colocamos en un arreglo ordenado. Por lo tanto, después de n iteraciones, tendremos una versión ordenada del arreglo de entrada.
El algoritmo se ejecuta en tiempo O(nlogn) y espacio adicional O(1) ya que todas las operaciones se realizan completamente en el lugar. La complejidad de tiempo del caso mejor, peor y promedio de Heapsort es O (nlogn). El algoritmo no es un algoritmo en el lugar en el sentido estricto que requiere la construcción de la estructura del montón, y también es inestable.
Ordenación Radix (Radix Sort)
La idea de Radix Sort es extender el algoritmo CountSort para obtener una mejor complejidad de tiempo. Para cada dígito i donde i varía del dígito menos significativo al dígito más significativo de un número, ordena el arreglo de entrada utilizando el algoritmo de ordenación de acuerdo con el i-ésimo dígito. Se usa la ordenación por conteo porque es una ordenación estable. El ejemplo proporcionado muestra la ordenación de un arreglo de números enteros aplicando este proceso dígito por dígito, desde las unidades hasta las centenas, para lograr la ordenación final.
Ordenación de Selección (Selection Sort)
Selection Sort es uno de los algoritmos de ordenación más simples. Este algoritmo recibe su nombre de la forma en que itera a través del arreglo: Selecciona el elemento más pequeño actual y lo cambia de lugar. Así es como funciona: encuentra el elemento más pequeño en el arreglo y lo intercambia con el primer elemento; luego encuentra el segundo elemento más pequeño y lo intercambia con el segundo elemento del arreglo, y así sucesivamente. La ordenación por selección siempre toma el mismo número de comparaciones clave - N(N − 1)/2. Sus propiedades son: complejidad espacial O(n), complejidad del tiempo O(n^2), es en el lugar, y no es estable.
Ordenación de Burbuja (Bubble Sort)
Al igual que las burbujas se elevan desde el fondo de un vaso, la ordenación de burbujas es un algoritmo simple que ordena una lista, lo que permite que los valores más bajos o más altos aparezcan en la parte superior. El algoritmo atraviesa una lista y compara valores adyacentes, intercambiándolos si no están en el orden correcto. Con una complejidad en el peor de los casos de O(n^2), la ordenación de burbujas es muy lenta en comparación con otros algoritmos de ordenación. La ventaja es que es uno de los algoritmos de ordenación más fáciles de entender y codificar desde cero. Desde una perspectiva técnica, la ordenación por burbuja es razonable para ordenar arreglos de tamaño pequeño o cuando se ejecutan en ordenadores con recursos de memoria notablemente limitados. Es un algoritmo estable.
Ordenación Rápida (Quick Sort)
Quick sort es un eficiente algoritmo de ordenación divide y vencerás. La complejidad de tiempo del caso promedio de Quick Sort es O (nlog (n)) y la complejidad de tiempo del peor caso es O (n ^ 2) dependiendo de la selección del elemento pivote, que divide el arreglo actual en dos sub arreglos. Los pasos involucrados en Quick Sort son: elegir un elemento para que sirva como pivote, particionar el arreglo de tal manera que todos los elementos menores que el pivote estén a la izquierda y todos los elementos mayores estén a la derecha, y llamar a Quicksort de forma recursiva.
La complejidad espacial de ordenación rápida es O(n). Esto es una mejora con respecto a otros algoritmos de ordenación de divide y vencerás, que ocupan espacio O(nlog(n)). La ordenación rápida logra esto cambiando el orden de los elementos dentro del arreglo dado. La complejidad de tiempo de Quick Sort es aproximadamente O(nlog(n)) cuando la selección del pivote divide el arreglo original en dos subarreglos de tamaño casi igual. Por otro lado, si el algoritmo genera consistentemente 2 subarreglos con una gran diferencia en términos de tamaños de arreglo, puede lograr la complejidad de tiempo del peor caso de O(n^2). No es un algoritmo estable, y es en el lugar.