Un algoritmo es una secuencia finita y no ambigua de pasos que transforma unos datos iniciales en un resultado verificable. Los diez métodos de este artículo son muy conocidos porque expresan ideas reutilizables: reducir el espacio de búsqueda, dividir un problema, recorrer una red, conservar resultados parciales o aprovechar las frecuencias.
No existe un algoritmo que sea el mejor en todos los casos. Un método es eficaz cuando es correcto para los datos disponibles, respeta las restricciones de tiempo y memoria y garantiza el resultado pedido. El pseudocódigo sirve para comprender la idea; en aplicaciones reales conviene utilizar bibliotecas consolidadas y bien probadas.
Cómo interpretar las complejidades
La notación O(...) describe cómo crece el coste al aumentar la entrada; no es un tiempo en segundos. En este artículo, n indica el número de elementos, V los vértices de un grafo, E sus aristas, m la longitud del patrón, W la capacidad de la mochila, k el número de símbolos distintos y L la longitud del mensaje.
| Orden | Interpretación práctica |
|---|---|
O(1) | El coste no aumenta con el tamaño de la entrada. |
O(log n) | Cada paso reduce mucho el problema, a menudo a la mitad. |
O(n) | El trabajo crece en proporción al número de elementos. |
O(n log n) | Coste típico de los algoritmos generales de ordenación eficientes. |
O(n²) | El coste puede crecer rápidamente con entradas grandes. |
1. Algoritmo de Euclides
Objetivo. Calcular el máximo común divisor de dos enteros sin enumerar todos sus divisores.
Idea fundamental. Si a = qb + r, los divisores comunes de a y b son los mismos que los de b y el resto r. Por tanto, se sustituye la pareja por (b, a mod b) hasta que el resto sea cero.
Pseudocódigo
MCD(a, b)
a ← valor_absoluto(a)
b ← valor_absoluto(b)
MIENTRAS b ≠ 0
(a, b) ← (b, a mod b)
DEVOLVER aEjemplo resuelto. Para MCD(252, 105): 252 mod 105 = 42, 105 mod 42 = 21 y 42 mod 21 = 0. El último resto distinto de cero es 21.
Complejidad. Tiempo O(log min(a,b)) y memoria O(1) en la versión iterativa.
Cuándo usarlo. Para simplificar fracciones, comprobar si dos números son coprimos, calcular periodos y preparar operaciones de aritmética modular. La versión extendida también obtiene coeficientes de Bézout e inversos modulares.
Limitación importante. El caso MCD(0,0) debe definirse aparte porque es indeterminado; el algoritmo no constituye por sí mismo un sistema criptográfico.
2. Búsqueda binaria
Objetivo. Encontrar un valor en una secuencia ordenada sin revisar todos sus elementos.
Idea fundamental. Se compara el valor buscado con el elemento central. La comparación descarta la mitad que no puede contener la respuesta y el proceso continúa únicamente en el intervalo restante.
Pseudocódigo
BUSQUEDA_BINARIA(A, x)
izquierda ← 0
derecha ← longitud(A) − 1
MIENTRAS izquierda ≤ derecha
centro ← izquierda + parte_entera((derecha − izquierda) / 2)
SI A[centro] = x DEVOLVER centro
SI A[centro] < x
izquierda ← centro + 1
EN_OTRO_CASO
derecha ← centro − 1
DEVOLVER no_encontradoEjemplo resuelto. Se busca 23 en [3, 8, 12, 17, 23, 31]. El primer valor central es 12, de modo que se descarta la parte izquierda; el nuevo valor central es 23 y la búsqueda termina.
Complejidad. Tiempo O(log n) y memoria O(1) en la forma iterativa.
Cuándo usarlo. En vectores ordenados con acceso rápido por índice; también para localizar el primer o el último punto en el que una propiedad monótona pasa a ser verdadera.
Limitación importante. Que los datos estén ordenados es una precondición. Si cambian continuamente, mantener el orden puede costar más de lo que se ahorra en las búsquedas.
3. Ordenación por mezcla (merge sort)
Objetivo. Ordenar una secuencia con un tiempo previsible y conservando el orden relativo de los elementos equivalentes.
Idea fundamental. Se divide la secuencia en dos mitades, se ordena recursivamente cada mitad y se mezclan comparando cada vez los primeros elementos que aún no se han copiado.
Pseudocódigo
ORDENAR_POR_MEZCLA(A)
SI longitud(A) ≤ 1 DEVOLVER A
centro ← parte_entera(longitud(A) / 2)
izquierda ← ORDENAR_POR_MEZCLA(A[0 ... centro−1])
derecha ← ORDENAR_POR_MEZCLA(A[centro ... fin])
DEVOLVER MEZCLAR(izquierda, derecha)
MEZCLAR(I, D)
resultado ← secuencia vacía
MIENTRAS I y D no estén vacías
mover a resultado el menor primer elemento
añadir todos los elementos restantes
DEVOLVER resultadoEjemplo resuelto. [8, 3, 5, 1] se divide en [8,3] y [5,1]. Las mitades se convierten en [3,8] y [1,5]; al mezclarlas se obtiene [1,3,5,8].
Complejidad. Tiempo O(n log n) en los casos mejor, medio y peor; memoria auxiliar habitual O(n). Es estable si, en caso de igualdad, se toma primero el elemento de la mitad izquierda.
Cuándo usarlo. Cuando se necesitan rendimiento previsible y estabilidad, en listas enlazadas o para la ordenación externa de datos que no caben en memoria.
Limitación importante. En vectores requiere memoria adicional; para bloques muy pequeños, un método de ordenación sencillo puede tener constantes menores.
4. Ordenación rápida (quicksort)
Objetivo. Ordenar rápidamente en memoria mediante una partición realizada en el propio vector.
Idea fundamental. Se elige un pivote, se colocan antes los elementos no mayores que él y después los mayores, y se ordenan recursivamente las dos partes. Un pivote aleatorio reduce la probabilidad de particiones muy desequilibradas.
Pseudocódigo
ORDENACION_RAPIDA(A, bajo, alto)
SI bajo ≥ alto DEVOLVER
p ← PARTICION_ALEATORIA(A, bajo, alto)
ORDENACION_RAPIDA(A, bajo, p − 1)
ORDENACION_RAPIDA(A, p + 1, alto)
PARTICION_ALEATORIA mueve un pivote aleatorio a su
posición definitiva y devuelve su índiceEjemplo resuelto. Con pivote 5, [8,3,5,1,7] se divide conceptualmente en [3,1] + [5] + [8,7]. Al ordenar las dos partes se obtiene [1,3,5,7,8].
Complejidad. Tiempo esperado O(n log n), peor caso O(n²). La partición puede hacerse en el propio vector; la pila ocupa en promedio O(log n), pero puede llegar a O(n).
Cuándo usarlo. Para vectores en memoria cuando importan la velocidad media, la localidad de caché y la poca memoria auxiliar. Las bibliotecas suelen emplear variantes híbridas.
Limitación importante. Normalmente no es estable y una elección repetidamente mala del pivote provoca el caso cuadrático. En aplicaciones conviene utilizar la función de ordenación de la biblioteca.
5. Búsqueda en anchura (BFS)
Objetivo. Recorrer un grafo por niveles y hallar desde un origen un camino con el menor número de aristas.
Idea fundamental. Una cola conserva los vértices descubiertos pero todavía no explorados. Todos los vértices situados a distancia d se procesan antes que los situados a distancia d + 1.
Pseudocódigo
BFS(G, origen)
para cada vértice v: visitado[v] ← falso
visitado[origen] ← verdadero
distancia[origen] ← 0
COLA.insertar(origen)
MIENTRAS COLA no esté vacía
u ← COLA.extraer_primero()
PARA cada v adyacente a u
SI no visitado[v]
visitado[v] ← verdadero
distancia[v] ← distancia[u] + 1
padre[v] ← u
COLA.insertar(v)Ejemplo resuelto. Si A está unido a B y C, B a D y C a E, la búsqueda desde A visita primero A, después B y C y finalmente D y E. El vector de padres permite reconstruir uno de los caminos mínimos.
Complejidad. Con listas de adyacencia, tiempo O(V+E) y memoria de trabajo O(V), además de la memoria del grafo.
Cuándo usarlo. Para distancias en grafos no ponderados, grados de separación, propagación por niveles, laberintos cuyas acciones tienen el mismo coste y comprobación de bipartición.
Limitación importante. No minimiza el coste si las aristas tienen pesos diferentes; el orden entre vértices del mismo nivel depende del orden de las adyacencias.
6. Búsqueda en profundidad (DFS)
Objetivo. Explorar por completo una rama antes de retroceder y probar las alternativas.
Idea fundamental. Una pila, explícita o proporcionada por la recursión, guarda el camino actual. Cuando un vértice no ofrece vecinos nuevos, la exploración vuelve al vértice anterior.
Pseudocódigo
DFS(G, origen)
visitado[origen] ← verdadero
PILA ← [origen]
MIENTRAS PILA no esté vacía
u ← PILA.extraer_ultimo()
PROCESAR(u)
PARA cada v adyacente a u
SI no visitado[v]
visitado[v] ← verdadero
padre[v] ← u
PILA.insertar(v)Ejemplo resuelto. En el grafo A–B, A–C, B–D y C–E, una posible búsqueda visita A, B, D, vuelve a A y continúa con C, E. Otro orden de vecinos produce otro recorrido válido.
Complejidad. Con listas de adyacencia, tiempo O(V+E) y memoria O(V). Una recursión muy profunda puede agotar la pila de llamadas del lenguaje.
Cuándo usarlo. Para componentes conexas, detección de ciclos, ordenación topológica de grafos acíclicos, exploración de laberintos y problemas de vuelta atrás.
Limitación importante. No garantiza el camino más corto. En los grafos hay que marcar los vértices visitados para evitar ciclos infinitos.
7. Algoritmo de Dijkstra
Objetivo. Calcular las distancias mínimas desde un origen en un grafo con pesos no negativos.
Idea fundamental. Se conserva una distancia provisional para cada vértice. Una cola de prioridad extrae el vértice no fijado más cercano; relajar una arista consiste en comprobar si llegar al vecino a través de ese vértice cuesta menos.
Pseudocódigo
DIJKSTRA(G, origen)
para cada v: distancia[v] ← infinito
distancia[origen] ← 0
COLA_PRIORIDAD.insertar(0, origen)
MIENTRAS la cola no esté vacía
(du, u) ← extraer_minimo()
SI du ≠ distancia[u] CONTINUAR
PARA cada arista (u, v, peso)
candidato ← du + peso
SI candidato < distancia[v]
distancia[v] ← candidato
padre[v] ← u
insertar(candidato, v)Ejemplo resuelto. Con aristas A–B:4, A–C:1, C–B:2, B–D:1 y C–D:5, el camino mínimo de A a D es A–C–B–D y cuesta 4.
Complejidad. Con lista de adyacencia y montículo binario, el tiempo es O((V+E) log V). Distancias y padres ocupan O(V); en la variante sencilla mostrada, las entradas antiguas del montículo pueden requerir hasta O(E), además del grafo O(V+E).
Cuándo usarlo. Para redes de carreteras sin costes negativos, encaminamiento, dependencias ponderadas y cualquier problema reducible a caminos mínimos ponderados no negativos.
Limitación importante. Una sola arista negativa invalida la garantía. En ese caso se necesita un algoritmo como Bellman–Ford; si todos los pesos son iguales, basta con BFS.
8. Mochila 0/1 con programación dinámica
Objetivo. Elegir objetos indivisibles maximizando el valor sin superar una capacidad entera.
Idea fundamental. Distintas elecciones reutilizan los mismos subproblemas. dp[c] conserva el mejor valor posible con capacidad c. Para cada objeto, las capacidades se recorren hacia atrás para impedir que el mismo objeto se elija dos veces.
Pseudocódigo
MOCHILA_01(objetos, W)
dp[0 ... W] ← 0
PARA cada (peso, valor) en objetos
PARA c DESDE W HASTA peso, EN ORDEN DESCENDENTE
dp[c] ← maximo(dp[c], dp[c − peso] + valor)
DEVOLVER dp[W]Ejemplo resuelto. Con capacidad 5 y objetos (peso 2, valor 3), (3,4) y (4,5), los dos primeros llenan la mochila y alcanzan el valor 7, mayor que el de cualquier objeto individual.
Complejidad. Tiempo O(nW) y memoria O(W). Es pseudopolinómica: depende del valor numérico de W, no solo del número de cifras con las que se escribe.
Cuándo usarlo. Para presupuestos o capacidades enteros moderados, selección de proyectos y asignación de recursos cuando cada elección puede tomarse como máximo una vez.
Limitación importante. Con una capacidad enorme, la tabla resulta impracticable; además, el modelo sencillo no representa dependencias entre objetos ni valores no aditivos.
9. Knuth–Morris–Pratt (KMP)
Objetivo. Encontrar todas las apariciones exactas de un patrón en un texto sin retroceder en el texto.
Idea fundamental. Una tabla de prefijos registra, para cada posición del patrón, la longitud del prefijo más largo que también es sufijo. Después de una discordancia se reutiliza esa información en vez de empezar desde cero.
Pseudocódigo
CONSTRUIR_PREFIJOS(P)
prefijo[0] ← 0; j ← 0
PARA i DESDE 1 HASTA longitud(P) − 1
MIENTRAS j > 0 Y P[i] ≠ P[j]
j ← prefijo[j − 1]
SI P[i] = P[j] ENTONCES j ← j + 1
prefijo[i] ← j
DEVOLVER prefijo
KMP(texto T, patrón P)
prefijo ← CONSTRUIR_PREFIJOS(P); j ← 0
PARA i DESDE 0 HASTA longitud(T) − 1
MIENTRAS j > 0 Y T[i] ≠ P[j]
j ← prefijo[j − 1]
SI T[i] = P[j] ENTONCES j ← j + 1
SI j = longitud(P)
INFORMAR i − longitud(P) + 1
j ← prefijo[j − 1]Ejemplo resuelto. Al buscar ABABAC en ABABABAC, tras una discordancia KMP sabe que el sufijo ABAB también es un prefijo útil. Encuentra la aparición que comienza en el índice 2, contando desde cero.
Complejidad. Construir la tabla y realizar la búsqueda requieren en conjunto O(n+m); la tabla utiliza O(m) de memoria.
Cuándo usarlo. Para búsqueda exacta en textos largos o flujos, especialmente con patrones muy repetitivos y cuando resulta útil una garantía lineal.
Limitación importante. Busca coincidencias exactas, no aproximadas. El pseudocódigo supone un patrón no vacío; para una sola búsqueda corta suele ser preferible la función optimizada del lenguaje.
10. Codificación de Huffman
Objetivo. Asignar códigos binarios más cortos a los símbolos frecuentes y más largos a los raros, manteniendo una decodificación única.
Idea fundamental. Se introducen las frecuencias en una cola de prioridad y se combinan repetidamente los dos nodos menos frecuentes. Los recorridos izquierdo y derecho del árbol resultante forman un código prefijo: ningún código es prefijo de otro.
Pseudocódigo
HUFFMAN(frecuencias)
Q ← monticulo_minimo con una hoja por símbolo
MIENTRAS tamaño(Q) > 1
x ← Q.extraer_minimo()
y ← Q.extraer_minimo()
z ← nodo(frecuencia(x) + frecuencia(y), x, y)
Q.insertar(z)
DEVOLVER Q.extraer_minimo()Ejemplo resuelto. Con frecuencias A:5, B:2, C:1, D:1, un código posible es A=0, B=10, C=110, D=111. Los 9 símbolos necesitan 15 bits, frente a 18 bits con un código fijo de dos bits.
Complejidad. Con k símbolos distintos, construir el árbol cuesta O(k log k); codificar o decodificar un mensaje cuesta O(L). El árbol y la tabla ocupan O(k).
Cuándo usarlo. Como componente de formatos de compresión y cuando se conocen frecuencias fiables. Es óptimo entre los códigos prefijo que asignan un número entero de bits a cada símbolo.
Limitación importante. Por sí solo no aprovecha repeticiones largas ni contexto; en archivos pequeños, almacenar el árbol puede anular el ahorro. Para datos reales deben usarse formatos y bibliotecas estándar.
¿Qué algoritmo conviene elegir?
Esta tabla no sustituye el análisis de las restricciones, pero ofrece una primera orientación.
| Problema | Elección inicial | Motivo |
|---|---|---|
| Máximo común divisor y coprimalidad | Algoritmo de Euclides | Reduce rápidamente la pareja mediante los restos. |
| Valor en una secuencia ordenada | Búsqueda binaria | Descarta la mitad del intervalo en cada comparación. |
| Ordenación estable y previsible | Ordenación por mezcla (merge sort) | Garantiza siempre un tiempo proporcional a n log n. |
| Ordenación rápida de un vector en memoria | Ordenación rápida (quicksort) | Ofrece un rendimiento medio excelente y partición en el propio vector. |
| Camino mínimo en un grafo no ponderado | Búsqueda en anchura (BFS) | El recorrido por niveles garantiza el menor número de aristas. |
| Exploración completa, ciclos o vuelta atrás | Búsqueda en profundidad (DFS) | Sigue una rama hasta el final y después vuelve a las alternativas. |
| Camino mínimo con pesos no negativos | Algoritmo de Dijkstra | Fija siempre la menor distancia provisional. |
| Selección óptima con capacidad entera moderada | Mochila 0/1 con programación dinámica | Reutiliza los resultados de subproblemas que se solapan. |
| Búsqueda exacta de un patrón en un texto | Knuth–Morris–Pratt (KMP) | No vuelve a comprobar caracteres cuya información ya conoce. |
| Código prefijo basado en frecuencias | Codificación de Huffman | Asigna menos bits a los símbolos más frecuentes. |
Comparar estos algoritmos muestra una lección general: primero hay que definir con precisión la entrada, el resultado requerido y las restricciones; después se elige la idea que mejor aprovecha la estructura del problema. La corrección y las precondiciones están antes que la velocidad.