Algoritmos

El panorama y el vocabulario

Imagina que debes encontrar un nombre en una guía telefónica. Puedes leer cada línea desde el principio, o puedes abrir el libro por la mitad y decidir qué mitad conservar. Las dos formas son correctas, pero la segunda es mucho más rápida. Comparar recetas así es el corazón del estudio de los algoritmos.

Para cada algoritmo hacemos tres preguntas. ¿Es correcto, es decir, siempre da la respuesta acertada? ¿Cuánto tiempo necesita cuando la entrada crece? ¿Cuánta memoria extra usa? Para responder la segunda, contamos pasos y describimos cómo crece esa cuenta con el tamaño n de la entrada, usando la notación Big O.

Mira lo enorme que es la última barra frente a las demás. Con solo mil elementos, un algoritmo cuadrático ya hace cien veces más trabajo que un buen ordenamiento. Con un millón de elementos, la brecha se vuelve un millón de veces mil. Por eso nos importa la idea, y no solo una máquina rápida.

Las cuatro técnicas de diseño

Palabras que aparecen en todas las secciones

Ordenamientos elementales: burbuja, selección, inserción

Ordenar es poner elementos en orden. Las tres formas más simples son fáciles de explicar y de escribir. Todas toman cerca de n² pasos en el peor caso, así que se usan para entradas pequeñas, o como ayudantes dentro de algoritmos más astutos.

Insertion sort: ordenar cartas de baraja

La regla que siempre se cumple es el invariante: antes de tratar la posición i, las posiciones 0 a i − 1 están ordenadas. Después de tratarla, las posiciones 0 a i están ordenadas y el resto del arreglo no se tocó. Para insertar, el algoritmo desplaza los elementos mayores un lugar a la derecha y deja el elemento nuevo en el hueco.

El costo depende de qué tan desordenada esté la entrada. Si ya está ordenada, el elemento nuevo nunca es menor que su vecino de la izquierda, así que cada paso cuesta una comparación y el total es cerca de n. Si está invertida, cada elemento viaja hasta el principio y el total es cerca de n²/2. Más exactamente, el costo es cerca de n más el número de inversiones. Si cada elemento está a lo sumo a k posiciones de su lugar final, hay como máximo cerca de n·k inversiones, así que el costo es cerca de n·k. Por eso el insertion sort es la mejor opción para datos casi ordenados.

Se puede usar búsqueda binaria para hallar el lugar del elemento nuevo, lo que baja las comparaciones a cerca de log n por elemento. Pero el desplazamiento sigue siendo necesario, y en un arreglo es el costo mayor. Así que este truco solo vale la pena cuando comparar es mucho más caro que mover.

Selection sort: elegir el menor

Mira todos los elementos aún desordenados, halla el menor e intercámbialo con el primero de ellos. Repite para la siguiente posición. Hallar el menor de m elementos siempre exige m − 1 comparaciones, incluso si el arreglo ya está ordenado. Así que el total es siempre (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2 comparaciones. No es adaptativo.

A cambio, mueve muy poco: un intercambio por ronda, o sea a lo sumo n − 1 intercambios en total. Si mover un registro grande es caro y comparar es barato, el selection sort es una buena opción.

Bubble sort: el mayor sube

Recorre el arreglo de izquierda a derecha e intercambia cada par de vecinos fuera de orden. Al final de la primera pasada, el mayor elemento 'burbujeó' hasta la última posición. Después de k pasadas, los k mayores están en sus lugares finales, así que cada pasada puede detenerse una posición antes.

Pasada 1 en [3, 1, 2]:
  [3, 1, 2]  3 > 1, intercambia
  [1, 3, 2]  3 > 2, intercambia
  [1, 2, 3]  el mayor quedó al final
Pasada 2: ningún intercambio -> se detiene

Intercambiar dos vecinos fuera de orden elimina exactamente una inversión y no crea ninguna. Por eso el número de intercambios del bubble sort es exactamente el número de inversiones de la entrada. Si añades una bandera que recuerda si la pasada intercambió algo, el algoritmo se detiene tras una pasada sin intercambios, porque eso prueba que todo está en orden. Con la bandera, una entrada ordenada cuesta solo cerca de n pasos.

Merge sort

Supón que dos amigos tienen, cada uno, una pila de hojas de tarea ya ordenada por nombre. Para juntar las pilas en una sola pila ordenada, solo debes mirar la hoja de arriba de cada pila y tomar la menor. Repite hasta que las dos pilas se acaben. Ese paso de juntar se llama merge (mezcla), y el merge sort se construye sobre él.

El merge sort tiene tres pasos. Dividir el arreglo en dos mitades, ordenar cada mitad llamando de nuevo al merge sort, y mezclar las dos mitades ordenadas. Un arreglo con un elemento ya está ordenado, así que la división se detiene ahí. Esto es divide y vencerás.

          [6 2 8 3]
          /       \
      [6 2]       [8 3]
      /   \       /   \
    [6]   [2]   [8]   [3]
      \   /       \   /
      [2 6]       [3 8]
          \       /
          [2 3 6 8]

El costo se describe con una recurrencia: T(n) = 2·T(n/2) + n. Dos mitades, más una mezcla que toca cada elemento una vez. El árbol de recursión tiene cerca de log₂ n niveles, y cada nivel hace cerca de n de trabajo en total. Así que el merge sort cuesta n·log₂ n.

La división se hace por posición (la mitad), nunca mirando los valores. Así que la forma del árbol es siempre la misma, sea cual sea el orden de los datos. Un arreglo ordenado, uno invertido y uno aleatorio tienen el mismo orden de crecimiento. Solo cambia un poco el número exacto de comparaciones.

¿Cuántas comparaciones necesita una mezcla?

Cada comparación manda exactamente un elemento a la salida. Cuando una pila se acaba, el resto de la otra se copia sin comparar. El peor caso es cuando las pilas están entrelazadas de modo que una quede con un solo elemento al final. Mezclar m y n elementos toma entonces como máximo m + n − 1 comparaciones.

Memoria extra y estabilidad

• Memoria. Mezclar dentro del mismo arreglo sin espacio extra es difícil y lento. La solución clásica copia los elementos a un buffer y los escribe de vuelta en orden. Ese buffer tiene tamaño n, así que el merge sort clásico no es in-place.
• Estabilidad. Cuando el elemento de la mitad izquierda y el de la derecha son iguales, toma el de la izquierda, porque llegó primero en la entrada. Copia el de la izquierda cuando left[i] <= right[j]. Usar < estricto tomaría el de la derecha en los empates y rompería la estabilidad.

// ES: toma de la izquierda en los empates, para que claves iguales mantengan el orden
if (left[i] <= right[j]) {
	out.push(left[i++]);
} else {
	out.push(right[j++]);
}

La prueba del doble

Cuando n se duplica, un algoritmo n·log n tarda un poco más del doble (cerca de 2 × (1 + 1/log₂ n)), mucho menos que las cuatro veces de un algoritmo cuadrático. En un benchmark, una razón cercana a 2 indica crecimiento lineal o n log n, y una razón cercana a 4 indica n².

Extra: contar inversiones

El merge sort puede contar las inversiones de un arreglo en tiempo n log n. Las inversiones dentro de cada mitad las cuenta la recursión. Las que cruzan las mitades se cuentan durante la mezcla: cuando el siguiente elemento a copiar viene de la mitad derecha, es menor que todos los elementos que aún esperan en la mitad izquierda, así que sumamos al contador el número de elementos que quedan en la izquierda.

Quicksort y estrategias de pivote

Imagina una maestra que pide al grupo formarse por estatura. Ella elige a un alumno, el pivote, y dice: 'más bajos que el pivote a la izquierda, más altos a la derecha'. Ahora el pivote está exactamente donde se quedará al final. Los dos grupos se ordenan con el mismo método, y nadie necesita juntarlos después.

antes:    [ 6  2  8  3  5 ]      pivote = 5 (el último)
después:  [ 2  3 |5| 6  8 ]
            <= 5 pivote  > 5
luego se ordena la parte izquierda y la derecha

Este paso se llama partición, y es donde está el trabajo. El quicksort es lo opuesto del merge sort: la división es difícil y el paso de combinar está vacío. Una forma popular de particionar (llamada Lomuto) usa el último elemento como pivote y mantiene un marcador i al final de la región de los elementos pequeños. Cada elemento menor o igual al pivote se intercambia justo después de esa región. Al final, el pivote se intercambia a la posición siguiente a la región.

function partition(a: number[], lo: number, hi: number): number {
	const pivot = a[hi];
	let i = lo - 1; // ES: fin de la región de los 'pequeños'
	for (let j = lo; j < hi; j++) {
		if (a[j] <= pivot) {
			i++;
			[a[i], a[j]] = [a[j], a[i]];
		}
	}
	[a[i + 1], a[hi]] = [a[hi], a[i + 1]];
	return i + 1; // ES: lugar final del pivote
}

Todo depende del pivote

El mejor pivote es la mediana: corta el rango por la mitad, así que hay cerca de log₂ n niveles de trabajo n cada uno, y el total es n·log n. El peor pivote es el elemento menor o el mayor: las partes tienen 0 y n − 1 elementos, hay n niveles, y el costo es (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2, que es n². En ese peor caso, cada par de elementos se compara exactamente una vez.

La mediana de tres mira el primer elemento, el del medio y el último, y usa la mediana de esos tres como pivote. Con pivote aleatorio, el peor caso deja de pertenecer a una entrada concreta (como la ordenada). Pertenece a una secuencia desafortunada de sorteos, así que el promedio es sobre las elecciones del algoritmo, y un adversario no puede armar de antemano una entrada mala.

Memoria: in-place, pero con una pila

El quicksort reorganiza los elementos dentro del arreglo, así que es in-place. Pero cada llamada recursiva usa un poco de memoria en la pila de llamadas. Con partes equilibradas, la profundidad es cerca de log n. Con las peores partes, es n. Un truco común es recursar en la parte menor y hacer un bucle en la mayor, lo que mantiene la profundidad en log n incluso en los casos malos.

Muchas claves iguales

Si la partición tiene solo dos regiones ('menor o igual' y 'mayor') y las n claves son todas iguales, todos los elementos van al mismo lado, las partes tienen 0 y n − 1 elementos, y el costo es n², sea cual sea el pivote. La solución clásica es la partición en tres vías (la bandera holandesa): poner las claves menores, iguales y mayores que el pivote en tres grupos, y recursar solo en el primero y el último. Con pocas claves distintas, el costo se acerca a lineal.

Quicksort híbrido

La mayoría de las llamadas del quicksort tratan rangos diminutos. Para diez elementos, elegir un pivote y hacer dos llamadas cuesta más que el trabajo mismo. Por eso muchas bibliotecas entregan todo rango menor que una constante k (por ejemplo 16) al insertion sort. Esto no cambia el orden de crecimiento, que sigue siendo n log n, pero baja la constante, y el mejor k se encuentra midiendo. En el benchmark de este repositorio, un umbral de algunas decenas de elementos ayudó tanto en C++ como en Rust.

Heapsort

Un heap es un árbol genealógico con una regla estricta. En un max-heap, todo padre es mayor o igual que sus hijos. Así que el mayor elemento de todo el árbol está siempre arriba, en la raíz. El árbol también es completo: todos los niveles están llenos, salvo quizá el último, que se llena de izquierda a derecha.

Un árbol dentro de un arreglo

Como el árbol es completo, cabe en un arreglo simple, nivel por nivel, sin punteros. Las relaciones se vuelven aritmética sobre el índice.

        9            índice: 0  1  2  3  4  5
      /   \          valor:  9  4  5  1  3  2
     4     5
    / \   /
   1   3 2

Sift-down y la construcción del heap

El sift-down (también llamado heapify) arregla un nodo: compáralo con su hijo mayor, intercambia si el hijo es mayor, y repite bajando por ese camino. Para convertir cualquier arreglo en heap, aplica el sift-down a cada nodo interno, del último hasta la raíz. En [2, 8, 5, 1], el último nodo interno (índice 1) está bien, luego la raíz 2 se intercambia con el 8 y el arreglo queda [8, 2, 5, 1].

Construir un heap así cuesta solo n, y no n log n. La razón es que el costo de un nodo es su propia altura, y la mayoría de los nodos son bajos: cerca de n/2 son hojas (altura 0), n/4 tienen altura 1, n/8 tienen altura 2, y la suma n/4·1 + n/8·2 + n/16·3 + ... se queda por debajo de n. Si construyes el heap insertando los elementos uno a uno y subiendo cada uno (sift-up), el costo de un nodo es su profundidad, y la mayoría de los nodos son profundos, así que el total es n log n.

El ordenamiento en sí

1. Construye un max-heap en el arreglo (costo n).
2. Intercambia la raíz (el mayor) con el último elemento del heap. Ya queda en su lugar final.
3. Reduce el heap en un elemento y haz el sift-down de la nueva raíz.
4. Repite los pasos 2 y 3 hasta que el heap tenga un elemento (n − 1 veces, cada una cuesta cerca de log n).

El total es n log n en todos los casos, con memoria extra constante. Es el único ordenamiento clásico con ambas propiedades. El precio es que no es estable, porque los intercambios saltan sobre claves iguales, y que lee la memoria en posiciones dispersas, lo que lo hace más lento en la práctica que un buen quicksort.

Ordenamientos en tiempo lineal: counting, radix, bucket

Todos los ordenamientos de las secciones anteriores son ordenamientos por comparación. Hay un límite duro para ellos: para distinguir los n! órdenes posibles de n elementos usando solo preguntas de sí o no, se necesitan al menos log₂(n!) preguntas, que es cerca de n·log n. Ningún ordenamiento por comparación puede superar eso, por muy ingenioso que sea.

La salida es dejar de comparar. Si las claves son enteros pequeños, podemos usar las propias claves como posiciones. Estos ordenamientos usan la estructura de las claves, así que el límite no se aplica a ellos.

Counting sort

1. Cuenta cuántas veces aparece cada valor en un arreglo C.
2. Haz una suma acumulada en C, de modo que C[v] pase a ser cuántos elementos son menores o iguales a v. Eso dice dónde termina el grupo de v en la salida.
3. Recorre la entrada de atrás hacia adelante, pon cada elemento en la posición C[v] − 1 de la salida y decrementa C[v].

entrada:         [1, 3, 1, 0, 3]      valores 0..3
conteos:         [1, 2, 0, 2]
suma acumulada:  [1, 3, 3, 5]
salida:          [0, 1, 1, 3, 3]

El costo es n + k, donde k es el tamaño del rango de valores (de 0 a k). Es excelente cuando k es cerca de n, y pésimo cuando k es enorme. Ir de atrás hacia adelante en el paso 3 mantiene los elementos iguales en su orden original, así que el ordenamiento es estable. Eso importa para el siguiente.

Radix sort (LSD)

El radix sort ordena números dígito por dígito, empezando por el dígito menos significativo (LSD), el de la derecha. Cada pasada usa un ordenamiento estable (normalmente counting sort) sobre un dígito. La estabilidad es esencial: cuando dos números comparten el dígito de la pasada actual, deben quedar en el orden que dieron las pasadas anteriores.

inicio:         329 457 657 839 436 720 355
pasada unid.:   720 355 436 457 657 329 839
pasada dec.:    720 329 436 839 355 457 657
centenas:       329 355 436 457 657 720 839

Con d dígitos en base k, el costo es d·(n + k). El número de pasadas es el número de dígitos de la clave: un entero de 32 bits tratado como 4 bytes (base 256) necesita 4 pasadas. Una base mayor significa menos pasadas, pero un arreglo de conteo mayor. Un buen truco: para n enteros entre 0 y n³ − 1, elige la base n. Cada número tiene como máximo 3 dígitos, así que 3 pasadas de costo cerca de n cada una ordenan todo en tiempo lineal. Para un rango de n^c, son c pasadas.

Bucket sort

Divide el intervalo de valores en cubetas (buckets) de ancho igual, lanza cada elemento a su cubeta, ordena cada cubeta (normalmente con insertion sort) y júntalas. Es lineal en promedio si los datos están bien repartidos por el intervalo, porque así cada cubeta recibe pocos elementos. Si la mayoría de los datos cae en una sola cubeta, el costo pasa a ser el del ordenamiento interno, que es n² con insertion sort.

Estabilidad, ordenamiento in-place y adaptativo

La velocidad no es lo único que importa al elegir un ordenamiento. Tres propiedades dicen cómo se comporta un algoritmo con registros reales, con límites de memoria y con datos que ya están casi en orden.

Estable

Un ordenamiento es estable si los elementos con claves iguales salen en el mismo orden relativo en que llegaron. Importa cuando los registros llevan más que la clave. Supón una lista de alumnos ordenada por nombre. Si ahora la ordenas por grupo con un algoritmo estable, cada grupo conserva a sus alumnos en orden alfabético. Esto da un ordenamiento por dos criterios: ordena primero por la clave menos importante y al final por la más importante. Es también la razón por la que el radix sort LSD funciona.

¿Cómo puede un ordenamiento romper la estabilidad? Moviendo un elemento lejos en un solo salto. Imagina el selection sort en las cartas 7♥, 7♠, 3♣. Intercambia la primera carta con la menor, el 3♣. El resultado es 3♣, 7♠, 7♥. Los dos sietes cambiaron de lugar. Los algoritmos que solo mueven un elemento más allá de vecinos estrictamente mayores, o que copian los elementos en orden de llegada, son estables.

In-place

Un ordenamiento es in-place si trabaja dentro del arreglo de entrada, con a lo sumo cerca de log n de memoria extra (por ejemplo, una pila de recursión). El merge sort necesita un buffer de tamaño n, así que no es in-place. El quicksort sí lo es, porque su pila es pequeña. El heapsort lo es, con memoria extra constante.

Adaptativo

Un ordenamiento es adaptativo si se vuelve más rápido cuando la entrada está más cerca de estar ordenada. El insertion sort cuesta cerca de n más las inversiones, y el bubble sort con la bandera también se detiene antes. Selección, merge y heapsort hacen casi el mismo trabajo para cualquier orden. Los ordenamientos de bibliotecas como Timsort usan la misma idea a mayor escala: encuentran tramos que ya están ordenados y mezclan solo esos tramos.

Búsqueda: secuencial, binaria, interpolación

Buscar es hallar un elemento, llamado clave, en una colección. El método correcto depende de una pregunta: ¿está ordenada la colección?

Búsqueda secuencial

Mira los elementos uno por uno hasta hallar la clave o llegar al final. Funciona en cualquier colección. El mejor caso es 1 comparación, el peor es n, y si cada posición es igualmente probable para la clave, una búsqueda exitosa hace en promedio (n + 1)/2 comparaciones. Todo esto es lineal en n.

Una pequeña mejora es el centinela. Normalmente cada ronda prueba dos cosas: '¿llegué al final?' y '¿este es la clave?'. Si primero copias la clave a una posición extra al final del arreglo, el bucle tiene la seguridad de detenerse en la clave, y la primera prueba ya no hace falta. El costo sigue siendo lineal, pero la constante es menor, un detalle que la notación Big O no muestra.

Búsqueda binaria

La búsqueda binaria exige que los datos estén ordenados. Mira el elemento del medio. Si es la clave, detente. Si la clave es mayor, no puede estar en la mitad izquierda, así que haz low = mid + 1. Si es menor, haz high = mid − 1. Repite hasta que el intervalo quede vacío. En datos desordenados, la comparación con el medio no dice nada de los otros elementos, y el método falla.

function binarySearch(a: number[], key: number): number {
	let low = 0;
	let high = a.length - 1;
	while (low <= high) {
		// ES: low + (high - low) / 2 no desborda un int de 32 bits
		const mid = low + Math.floor((high - low) / 2);
		if (a[mid] === key) return mid;
		if (a[mid] < key) low = mid + 1;
		else high = mid - 1;
	}
	return -1;
}

Cada paso divide el intervalo a la mitad, así que el número máximo de miradas es ⌊log₂ n⌋ + 1. En una búsqueda fallida el número es el mismo: un intervalo de 7 pasa a 3, luego a 1, luego a 0, o sea 3 miradas. Los arreglos de tamaño 2ᵏ − 1 forman árboles perfectos con k niveles.

Duplicar el arreglo añade solo un paso: 1 millón de elementos necesita 20 miradas y 1.000 millones necesitan 30.

Dos detalles famosos

• El bug del desbordamiento. Escribir mid = (low + high) / 2 con enteros de 32 bits falla cuando low + high pasa de 2³¹ − 1, lo que ocurre en arreglos ordenados con más de unos mil millones de elementos. La suma se vuelve negativa. Un programa correcto en el papel puede fallar en una máquina real porque los enteros tienen tamaño fijo. Escribe mid = low + (high − low) / 2.
• Claves repetidas. Para hallar la primera aparición de una clave en O(log n), no te detengas al encontrarla. Busca el primer índice cuyo valor sea mayor o igual que la clave (un lower bound): cuando a[mid] >= key, conserva la mitad izquierda incluyendo mid. Nunca se detiene antes, y siempre toma cerca de log₂ n pasos.

Búsqueda por interpolación

Cuando buscas 'Zebra' en un diccionario, no lo abres por la mitad: lo abres cerca del final. La búsqueda por interpolación hace eso. Si los valores crecen más o menos en línea recta entre v[lo] y v[hi], estima la posición de la clave en esa recta.

// ES: la clave está a una fracción del camino entre los dos extremos
pos = lo + (hi - lo) * (key - v[lo]) / (v[hi] - v[lo]);

Si los valores están bien repartidos, el intervalo se encoge muy rápido (cerca de log log n pasos en promedio). Si no lo están, por ejemplo cuando crecen exponencialmente, la estimación se pega a un extremo y el intervalo se encoge un elemento por vez, así que el costo puede llegar a n. La velocidad de la búsqueda por interpolación depende de la distribución de las claves.

Divide y vencerás

¿Cómo se come una pizza gigante? Una porción a la vez. Divide y vencerás resuelve un problema grande cortándolo en copias menores del mismo problema. Siempre tiene tres pasos: dividir el problema, vencer cada parte resolviéndola de forma recursiva, y combinar las respuestas. La recursión se detiene en el caso base, un problema tan pequeño que la respuesta es inmediata.

Merge sort, quicksort y búsqueda binaria son divide y vencerás. En estos algoritmos las partes son fracciones del problema (la mitad, un tercio), así que la profundidad de la recursión es logarítmica. Insertion y selection sort son distintos: son incrementales, porque reducen el problema en un elemento por paso. Eso lleva a n etapas y, normalmente, a un costo cuadrático.

El costo como recurrencia

Si un algoritmo hace a subproblemas de tamaño n/b y gasta f(n) en dividir y combinar, entonces T(n) = a·T(n/b) + f(n). Para resolverla, compara f(n) con n^(log_b a), que es el número de hojas del árbol de recursión. Este es el teorema maestro.

Para la búsqueda binaria también puedes expandir a mano: T(n) = T(n/2) + c = T(n/4) + 2c = ... = c·log₂ n, porque log₂ n cuenta cuántas veces se puede dividir n entre 2 hasta llegar a 1. En la recurrencia T(n) = 4T(n/2) + n con n = 8, los niveles cuestan 8, 16, 32 y 64: la base domina, como dice el teorema.

Dos trucos clásicos

• Exponenciación por cuadrados sucesivos. Para calcular xⁿ, usa xⁿ = (xⁿ/²)² cuando n es par y xⁿ = x · xⁿ⁻¹ cuando n es impar. El exponente se reduce a la mitad cada vez, así que el número de multiplicaciones es cerca de log n en vez de n − 1. Para x¹⁰: x², x⁴, x⁵, x¹⁰ son solo 4 multiplicaciones.
• Karatsuba. Multiplicar dos números de n dígitos como en la escuela divide cada uno en dos mitades y necesita 4 productos de n/2 dígitos, lo que cuesta Θ(n²). Karatsuba encuentra una forma con solo 3 productos y algunas sumas de más. Como el número de subproblemas a aparece en el exponente log_b a, pasar de 4 a 3 baja el costo de n² a cerca de n^1,585. Strassen hace lo mismo para matrices, con 7 productos en vez de 8.

Cuándo no funciona bien

Divide y vencerás es excelente cuando los subproblemas son independientes, como las dos mitades de un arreglo. La función Fibonacci ingenua, fib(n) = fib(n − 1) + fib(n − 2), también se divide en problemas menores, pero estos se superponen: fib(n − 2) se calcula de nuevo dentro de fib(n − 1). Las llamadas se multiplican y el tiempo es exponencial. La cura es recordar las respuestas, que es la programación dinámica.

Algoritmos voraces

Un niño que se come primero lo más rico del plato, luego lo segundo más rico, está siendo voraz. Un algoritmo voraz arma la respuesta un paso a la vez y, en cada paso, toma la opción que parece mejor ahora. Nunca mira hacia el futuro y nunca cambia de opinión.

Eso hace que los algoritmos voraces sean rápidos y simples. Pero solo es correcto si el problema tiene la propiedad de elección voraz: siempre existe una solución óptima que contiene la elección localmente mejor. Sin una prueba de eso, un algoritmo voraz es solo una heurística.

Dar cambio

Un cajero con monedas de 1, 5, 10, 25 y 50 centavos da el cambio usando siempre la moneda mayor que todavía cabe. Para 68 centavos: 50, 10, 5, 1, 1, 1, o sea 6 monedas. Con estas monedas la regla siempre da el menor número de monedas. Pero con otras monedas puede fallar.

Selección de actividades

Muchas actividades quieren la misma sala. Cada una tiene hora de inicio y de fin. ¿Qué elección da el mayor número de actividades sin traslape? Toma la actividad que termina más temprano, descarta las que se traslapan con ella y repite. La prueba usa un argumento de intercambio: toma cualquier solución óptima y cambia su primera actividad por la que termina más temprano. La solución sigue siendo válida y del mismo tamaño. Entonces alguna solución óptima empieza con la elección voraz, y el mismo razonamiento vale para el tiempo que queda.

Mochila fraccionaria y mochila 0-1

Tienes una mochila con límite de peso y objetos con valor y peso. En la mochila fraccionaria puedes llevar parte de un objeto (como arena o harina). Ordena los objetos por valor por kilo y lleva primero la mejor razón. Cada kilo se usa con el material más valioso aún disponible, así que esto es óptimo.

Ejemplo con capacidad 10: el objeto X vale 20 y pesa 5 (razón 4), y el objeto Y vale 18 y pesa 6 (razón 3). El voraz lleva todo el X y 5/6 del Y, o sea 20 + 15 = 35. En la mochila 0-1 debes llevar el objeto completo o dejarlo, y la misma regla puede fallar. Con capacidad 10 y los objetos A (valor 36, peso 6, razón 6), B (valor 25, peso 5, razón 5) y C (valor 25, peso 5, razón 5), la regla de la razón lleva el A y ya nada más cabe, o sea 36. Pero B y C juntos pesan 10 y valen 50. La prueba del caso fraccionario necesita la opción de llenar el espacio restante con una fracción. La versión 0-1 necesita una tabla que compare 'llevar' y 'dejar' para cada objeto y capacidad, y eso es programación dinámica.

Dónde el voraz está probado como correcto

• Árbol generador mínimo (Prim y Kruskal, en la sección de grafos).
• Caminos mínimos con pesos no negativos (Dijkstra).
• Selección de actividades y mochila fraccionaria.
• Códigos de Huffman, que comprimen texto dando códigos cortos a las letras comunes.
• Cambio con sistemas de monedas 'bien portados'.

El voraz como heurística

El problema del viajante de comercio es NP-difícil: no se conoce un algoritmo que halle el mejor recorrido en tiempo polinomial. La heurística del vecino más cercano empieza en una ciudad y va siempre a la ciudad más cercana aún no visitada. Es rápida, pero no garantiza nada sobre el largo del recorrido: tramos baratos al principio pueden forzar tramos larguísimos al final. Normalmente se mejora con el 2-opt, una búsqueda local que elimina cruces del recorrido. En los experimentos de este repositorio con 5 a 12 ciudades, el vecino más cercano quedó en promedio un 8% por encima del mejor recorrido, y el 2-opt solo un 0,6%. Pero esos números describen aquellas instancias, no son una promesa.

Programación dinámica

Si alguien te pregunta '1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 ¿es cuánto?' y dices 8, y luego añade un '+ 1' más y vuelve a preguntar, no cuentas desde cero. Recuerdas el 8 y dices 9. La programación dinámica (PD) es eso: resolver cada problema pequeño una sola vez, anotar la respuesta y reutilizarla cada vez que vuelva el mismo problema pequeño.

La PD funciona cuando el problema tiene dos propiedades.

• Subestructura óptima. La mejor respuesta se arma con las mejores respuestas de subproblemas menores. Esto hace que la PD sea correcta.
• Subproblemas superpuestos. El mismo subproblema aparece muchas veces. Esto hace que la PD valga la pena. Sin superposición, la PD no está mal, solo no gana nada frente a la recursión simple.

Dos formas de escribirla

El costo de la PD es siempre: el número de subproblemas distintos por el trabajo de cada uno, suponiendo que los menores ya están hechos. Para Fibonacci con memoización, hay n + 1 subproblemas de costo constante, así que el tiempo es lineal. La recursión ingenua hace 2·fib(n + 1) − 1 llamadas, que crece cerca de 1,618 veces por cada +1 en n.

Problema 1: cambio con monedas cualesquiera

Sea dp[v] el menor número de monedas que forman el monto v. Entonces dp[0] = 0 y dp[v] = 1 + min(dp[v − c]) sobre las monedas c que caben en v. La tabla prueba cada moneda para cada monto, así que no cae en la trampa del voraz. Con monedas 1, 5 y 6:

Problema 2: la mochila 0-1

La celda (i, w) guarda el mejor valor usando los primeros i objetos con capacidad w. Es la mayor de dos opciones: dejar el objeto i, que es la celda (i − 1, w), o llevarlo, que es su valor más la celda (i − 1, w − peso), si cabe. Con capacidad 4 y los objetos P (valor 5, peso 2), Q (valor 4, peso 3) y R (valor 3, peso 1), las filas son:

La mochila es NP-difícil, pero O(n·W) parece polinomial. El truco: esto es pseudopolinomial. El tiempo es polinomial en el valor numérico de W, y no en el número de bits necesarios para escribirlo. Si W = 2⁶⁴, la entrada tiene solo 64 bits para la capacidad, pero la tabla tendría 2⁶⁴ columnas. Para capacidades pequeñas es excelente en la práctica.

Problema 3: subsecuencia común más larga (LCS)

Una subsecuencia mantiene el orden de las letras, pero no necesitan estar pegadas. La celda (i, j) guarda el largo de la LCS de las primeras i letras de una palabra y las primeras j de la otra. Si las últimas letras coinciden, la celda es 1 más la celda de la diagonal. Si no, es la mayor entre la celda de arriba y la de la izquierda. El costo es m·n. Para CAT y ACT:

Cada celda de la LCS depende solo de la fila actual y la anterior, así que puedes guardar solo dos filas. Ganas memoria, pero pierdes las decisiones que llevan a la respuesta: aún sabes el largo, pero no puedes reconstruir la subsecuencia. Este intercambio entre memoria y reconstruir la solución aparece en casi todo problema de PD.

Backtracking y fuerza bruta

Estás en un laberinto. En cada cruce eliges un camino. Si llegas a un callejón sin salida, regresas al último cruce y pruebas otro camino. Eso es backtracking: una búsqueda en profundidad sobre respuestas parciales que arma la solución una decisión a la vez y retrocede cuando un camino no puede funcionar.

Su poder está en la poda. Cuando una solución parcial ya es imposible, el algoritmo la descarta, y con ella todas las soluciones completas que crecerían a partir de ella. Los resolutores de sudoku, los laberintos y el problema de las n reinas funcionan así.

Fuerza bruta: probar todo

El método más simple es la fuerza bruta: generar cada candidato y probar cada uno. Es fácil de hacer bien y funciona para entradas pequeñas. Pero los candidatos se multiplican muy rápido. En el problema del viajante de comercio, un recorrido es un orden de las ciudades. Fijar la ciudad de partida elimina las rotaciones equivalentes y deja (n − 1)! órdenes por probar. Con 5 ciudades son 24.

El factorial crece más rápido que cualquier exponencial: cada ciudad extra multiplica el trabajo por el número de ciudades, un multiplicador que no deja de crecer. Pasar de 13 a 14 ciudades lo vuelve 13 veces más lento, y de 13 a 16 ciudades lo vuelve 13 × 14 × 15 = 2.730 veces más lento. En el benchmark de este repositorio, la fuerza bruta tomó cerca de 0,2 segundos con 11 ciudades y 1,7 segundos con 12 en TypeScript, y pasó de 10 segundos con 13 ciudades. Un lenguaje 2 o 3 veces más rápido compra cerca de una ciudad más.

Elegir una buena representación

La forma de describir un candidato puede eliminar candidatos antes de cualquier búsqueda. Toma el problema de las 8 reinas (colocar 8 reinas en un tablero de ajedrez sin que una ataque a otra). Elegir 8 casillas libremente entre 64 da más de 4.000 millones de posibilidades. Permitir solo una reina por fila da 8⁸ = 16 millones. Permitir una reina por fila y por columna, que son permutaciones, da 8! = 40.320. El backtracking recorta aún más, porque descarta una colocación parcial apenas dos reinas comparten una diagonal.

La poda debe ser segura

Toda regla de poda se apoya en una propiedad monótona: algo que, una vez roto, sigue roto en toda extensión. Ejemplo: hallar un subconjunto de números cuya suma sea exactamente T, descartando una rama cuando la suma parcial pasa de T. Esto solo es correcto si todos los números son no negativos, porque entonces la suma solo puede crecer. Si se permiten números negativos, un número posterior podría devolver la suma hacia abajo, y la poda tiraría respuestas válidas. Antes de podar, pregunta qué suposición sobre la entrada sostiene la poda.

Branch and bound

En el viajante de comercio puedes guardar el mejor recorrido completo hallado hasta ahora, como cota. Si un camino parcial ya es tan largo como esa cota o más, ninguna forma de completarlo vence al mejor recorrido, así que descartas la rama. Esto se llama branch and bound (ramificar y acotar). El recorte es seguro porque las distancias no son negativas, así que un camino nunca se acorta al extenderlo. Una buena primera cota, por ejemplo de la heurística del vecino más cercano, hace que la poda empiece antes.

• Held-Karp es una respuesta de programación dinámica que recuerda, para cada conjunto de ciudades visitadas y última ciudad, el mejor camino. Cuesta n²·2ⁿ, que sigue siendo exponencial pero mucho menor que n!.
• Las heurísticas como el vecino más cercano y el 2-opt cambian la garantía del mejor recorrido por velocidad.

Algoritmos en grafos: camino mínimo, árbol generador, ordenamiento topológico

Un grafo es un conjunto de puntos, llamados vértices, unidos por líneas, llamadas aristas. Ciudades y carreteras, amigos y amistades, tareas y sus dependencias son grafos. Las aristas pueden tener un peso, como una distancia o un costo, y pueden tener dirección. Sea V el número de vértices y E el número de aristas.

Árbol generador mínimo

Un árbol generador de un grafo conexo y no dirigido es un conjunto de aristas que conecta todos los vértices sin ciclos. Empezando con V vértices separados, cada arista que no forma un ciclo une dos grupos, y se necesitan V − 1 uniones para quedar con un solo grupo. Así que todo árbol generador tiene exactamente V − 1 aristas. El árbol generador mínimo (AGM) es el de menor peso total. Piensa en el conjunto más barato de cables para conectar todas las casas de un pueblo.

• Kruskal. Ordena las aristas por peso. Recórrelas y acepta cada arista que une dos grupos distintos (comprobado con una estructura llamada conjuntos disjuntos, o union-find). Detente cuando se acepten V − 1 aristas.
• Prim. Empieza desde un vértice y haz crecer un solo árbol. En cada paso agrega la arista más barata que conecta el árbol con un vértice de fuera. Ambos son voraces, y ambos dan el mismo peso total.

aristas: R-S 1, P-Q 2, Q-R 3, P-R 4, Q-S 6

Kruskal, en orden de peso:
  R-S 1  acepta
  P-Q 2  acepta
  Q-R 3  acepta (une {P,Q} y {R,S})
  P-R 4  rechaza (cerraría un ciclo)
  Q-S 6  rechaza
4 vértices -> 3 aristas, peso total 1 + 2 + 3 = 6

Camino mínimo: Dijkstra

Dijkstra halla el camino más corto desde un origen hasta todos los demás vértices. Guarda la mejor distancia conocida de cada vértice. En cada paso elige el vértice aún no finalizado de menor distancia, lo finaliza y relaja sus aristas: si dist[u] + peso(u, v) < dist[v], entonces se actualiza dist[v]. La idea es voraz y correcta porque extender un camino nunca lo abarata.

aristas: S-A 7, S-B 2, B-A 3, A-T 1, B-T 8

inicio:       S=0
finaliza S:   A=7, B=2
finaliza B:   A=min(7, 2+3)=5, T=2+8=10
finaliza A:   T=min(10, 5+1)=6
camino mínimo de S a T: S-B-A-T = 6

Con un heap, Dijkstra corre en cerca de (V + E)·log V. Exige pesos no negativos. Una arista negativa rompe la prueba. Ejemplo: aristas S → A con peso 3, S → B con peso 4 y B → A con peso −2. Dijkstra finaliza A con distancia 3 (es la menor) y nunca lo reabre, pero el camino mínimo real hasta A es S → B → A, con costo 2. Bellman-Ford resuelve el problema: relaja todas las aristas V − 1 veces, en O(V·E), y también detecta ciclos negativos.

Ordenamiento topológico

Un grafo dirigido puede modelar dependencias: 'calcetines antes que zapatos'. Un ordenamiento topológico lista los vértices de modo que, para toda arista u → v, u venga antes que v. Solo existe si el grafo no tiene ciclos. Un ciclo es una dependencia circular (A necesita B, B necesita A), que ningún orden puede satisfacer. Puede haber varios ordenamientos válidos.

El algoritmo de Kahn repite esto: quitar un vértice de grado de entrada cero (sin dependencia pendiente), ponerlo en la salida y bajar en uno el grado de entrada de sus sucesores. Toma Calcetines → Zapatos, Pantalón → Zapatos y Pantalón → Cinturón. Calcetines y Pantalón empiezan en 0, así que quita Calcetines (Zapatos pasa a 1), quita Pantalón (Zapatos y Cinturón pasan a 0), y luego Zapatos y Cinturón. El resultado: Calcetines, Pantalón, Zapatos, Cinturón.

Si el algoritmo termina habiendo quitado menos de V vértices, el resto del grafo tiene un ciclo: esos vértices siempre esperan a otro del mismo ciclo. Así avisan los gestores de paquetes y las herramientas de build de una dependencia circular. El algoritmo de Kahn cuesta V + E. Para comprobar un orden dado, recorre las aristas y confirma que el origen de cada una aparece antes que el destino.

Elegir la herramienta correcta

Ahora tienes una caja de herramientas. La habilidad es mirar un problema y elegir la herramienta correcta. Estas preguntas ayudan.

Elegir un ordenamiento

Errores comunes

• Usar búsqueda binaria en datos que no están ordenados.
• Confiar en una regla voraz sin prueba. Busca primero un contraejemplo.
• Usar Dijkstra con aristas negativas.
• Olvidar la memoria de un algoritmo: el merge sort necesita un buffer, el quicksort necesita una pila.
• Culpar al lenguaje cuando el problema es el algoritmo. En la carrera de ordenamiento de este repositorio, el merge sort en Python con 10.000 valores (32,7 ms) venció al bubble sort en C++ (69,0 ms).