⚙️ Catálogo de algoritmos

Un algoritmo se corre una vez y entrega una respuesta: lo que importa es su costo total y, sobre todo, cuándo aplica. (Su contraparte son las estructuras, que se construyen y se consultan: Catálogo de estructuras.)

Esta página está ordenada por lo que te piden, no por nombre: el problema casi nunca dice “usa Dijkstra”, dice “el camino más barato”.

Es un catálogo, no un plan de estudio

Aquí conviven lo que se aprende en el módulo 08 y lo que recién tiene sentido después de la nacional (Li Chao, HLD, Knuth). Si estás empezando, no lo leas de arriba abajo: entra desde la Ruta de Aprendizaje, que ordena por dificultad, y vuelve aquí cuando tengas un enunciado en la mano y no sepas qué usar. Cada ficha dice en qué módulo se aprende.

V y E

En los costos de grafos, V son los vértices (nodos) y E las aristas. Los enunciados casi siempre los llaman N y M: es la misma cosa con otro nombre.

🧭 Elegir por lo que te piden

Caminos y distancias

Lo que te pidenUsaCosto
distancia mínima con aristas de igual pesoBFSO(V+E)
camino mínimo con pesos no negativosDijkstraO((V+E) log V)
camino mínimo con pesos negativosBellman-FordO(n·m)
distancias entre todas las parejas (n chico)Floyd-WarshallO(n³)

Estructura de un grafo

Lo que te pidenUsa
recorrer todo / contar componentes conexasDFS · BFS
contar regiones o islas en una grillaFlood fill
ordenar tareas con prerrequisitos (y detectar ciclos)Orden topológico (Kahn)
grupos que se alcanzan mutuamente en un grafo dirigidoSCC (Tarjan)
aristas o nodos cuya caída desconecta el grafoPuentes y puntos de articulación
conectar todo al mínimo costoKruskal (MST) · Prim (MST)
emparejar dos grupos (personas ↔ tareas)Matching bipartito (Kuhn)
cuánto “cabe” por una red / corte mínimoFlujo máximo (Ford-Fulkerson)

Árboles

Lo que te pidenUsa
el camino más largo del árbolDiámetro de un árbol
la respuesta para cada nodo como raízDP en árboles (rerooting)
consultas sobre el camino entre dos nodosLCA con binary lifting · Heavy-Light Decomposition
contar caminos que pasan por cada nodoCentroid decomposition

Números

Lo que te pidenUsa
todos los primos hasta nCriba de Eratóstenes
los divisores primos de un númeroFactorización
mcd, mcm, ecuaciones con enterosEuclides extendido (gcd)
aᵇ mod m con b giganteExponenciación rápida (modular)
contar combinaciones C(n, k)Coeficientes binomiales
contar los que cumplen alguna de varias condicionesInclusión-exclusión

Geometría

Lo que te pidenUsa
hacia qué lado gira / de qué lado cae un puntoProducto cruz y orientación
el polígono que envuelve a todos los puntosConvex hull
procesar eventos ordenados (intervalos, choques)Barrido (sweep line)

Greedy y juegos

Lo que te pidenUsa
tomar la decisión obvia… y poder demostrar que sirveGreedy y argumento de intercambio
quién gana si los dos juegan perfectoTeoría de juegos (posiciones ganadoras)

Programación dinámica

Lo que te pidenUsa
una recurrencia que se repite a sí mismaRecursión y memoización
el subarreglo contiguo de suma máximaKadane (subarreglo de suma máxima)
juntar/partir por tramos, o un juego por los extremosDP de intervalos
elegir objetos sin pasarse de una capacidadMochila 0-1
la secuencia creciente más larga (o algo que lo sea disfrazado)Subsecuencia creciente más larga (LIS)
asignar/emparejar/recorrer todo, con n ≤ 20DP con bitmask

Optimizar y buscar

Lo que te pidenUsa
probar todas las opciones con n chico (n ≤ 20)Backtracking
revelar estructura ordenando (y ordenar con tu criterio)Ordenamiento y comparadores
buscar un valor en algo ordenado, o contar cuántos hay ≤ xBúsqueda binaria clásica
el subarreglo más corto/largo que cumple una condiciónDos punteros y ventana deslizante
”el mínimo x tal que se pueda…”Búsqueda binaria sobre la respuesta
el mayor/menor anterior más cercano a cada elementoStack monótono
el máximo o mínimo de cada ventana de largo kDeque monótona (ventana deslizante)
minimizar una función que baja y después subeBúsqueda ternaria
una DP O(n²) con transiciones lineales que no cabeConvex hull trick (Li Chao)
una DP de intervalos O(n³) que no cabeOptimización de Knuth
una DP por capas cuyo óptimo es monótonoOptimización divide y vencerás (DP)
una DP que pide exactamente k grupos y es convexa en kAliens trick (optimización lagrangiana)

📚 Todos, por tema

Grafos

AlgoritmoQué resuelveCosto
BFSRecorrido por niveles desde un origen; da la distancia mínima en aristas (grafo no ponderado) a todos los nodosO(V + E).
Bellman-FordCamino mínimo desde un origen admitiendo pesos negativos; detecta ciclos negativos alcanzablesO(V·E).
DFSRecorre un grafo metiéndose hasta el fondo por cada rama antes de retrocederO(V + E): cada nodo y cada arista se tocan una vez.
DijkstraCamino mínimo desde un origen en grafos con pesos NO negativosO((V + E) log V) con priority_queue.
Flood fillPinta toda la región conectada a una celda de una grillaO(filas × columnas): cada celda se visita una vez.
Floyd-WarshallCaminos mínimos entre TODOS los pares de vértices, por DP sobre vértices intermediosO(V³) tiempo, O(V²) memoria.
Flujo máximo (Ford-Fulkerson)Flujo máximo entre fuente y sumidero buscando caminos aumentantes por BFS (Edmonds-Karp) sobre la red residual; da también el corte mínimoO(V·E²) (Edmonds-Karp).
Kruskal (MST)Árbol de expansión mínima: subconjunto de aristas de menor costo que conecta todo el grafo, ordenando aristas y uniendo con DSUO(E log E) por el ordenamiento.
Matching bipartito (Kuhn)Emparejamiento máximo en un grafo bipartito buscando caminos aumentantes con DFSO(V·E) en el peor caso.
Orden topológico (Kahn)Ordena los vértices de un DAG de modo que toda arista u→v aparezca con u antes que vO(V + E).
Prim (MST)Árbol de expansión mínima creciendo desde un vértice y agregando siempre la arista más barata hacia un vértice nuevoO(E log V) con priority_queue.
Puentes y puntos de articulaciónHalla las aristas (puentes) y vértices (puntos de articulación) cuya eliminación desconecta el grafo, con tiempos de llegada y low-linkO(V + E).
SCC (Tarjan)Componentes fuertemente conexas de un grafo dirigido en una sola pasada de DFS; el id de componente queda en orden topológico inversoO(V + E).

Árboles

AlgoritmoQué resuelveCosto
Centroid decompositionConstruye el ‘árbol de centroides’: recursivamente elige el centroide, lo quita y recurreConstrucción O(n log n).
DP en árboles (rerooting)Calcula, para CADA nodo como raíz, una agregación sobre todo el árbol en O(n) total: una pasada hacia arriba y otra propagando hacia abajoO(n).
Diámetro de un árbolLa distancia (en aristas) más larga entre dos nodos, con dos BFS: el nodo más lejano desde cualquiera, y desde él el más lejanoO(n).
Heavy-Light DecompositionDescompone el árbol en cadenas ‘pesadas’ para responder consultas/updates sobre CAMINOS con un segment tree, en O(log² n)Construcción O(n); consulta de camino O(log² n).

Programación Dinámica

AlgoritmoQué resuelveCosto
Aliens trick (optimización lagrangiana)Quita la restricción de ‘exactamente k partes’ cobrando una penalización λ por cada parte, resuelve el problema libre (que es mucho más barato) y busca por búsqueda binaria el λ que hace que el óptimo use k partesO(costo del DP sin restricción × log(rango de λ)). Con el DP interno en O(n) u O(n log n), reemplaza un O(n·k) por algo casi independiente de k.
Convex hull trick (Li Chao)Mantiene un conjunto de rectas y responde el mínimo (o máximo) en un punto, para optimizar DPs de la forma dp[i] = min_j (m_j·x_i + b_j)Agregar recta y consultar: O(log rango).
DP con bitmaskUsa un número entero como conjunto: el bit i dice si el elemento i ya fue usadoO(2^n · n) o O(2^n · n²) según la transición. Cabe hasta n ≈ 20-22.
DP de intervalosLa DP cuyo estado es un segmento: dp[l][r] = la mejor respuesta para el trozo que va de l a rO(n²) estados. O(n³) si la transición prueba un punto de corte, O(n²) si solo mira los extremos.
Kadane (subarreglo de suma máxima)La suma máxima de un subarreglo contiguo no vacío, en una sola pasadaO(n) tiempo y O(1) memoria.
Mochila 0-1Elige un subconjunto de objetos, cada uno con peso y valor, para maximizar el valor sin pasarse de una capacidadO(n · C) tiempo y O(C) memoria con el truco de una sola fila.
Optimización de KnuthAcelera DPs de intervalo dp[l][r] = min_{l<=k<r}(dp[l][k]+dp[k+1][r]) + cost(l,r) usando que el k óptimo está acotado por los óptimos vecinosO(n²) en vez de O(n³).
Optimización divide y vencerás (DP)Acelera DPs dp[i][j] = min_k (dp[i-1][k] + cost(k,j)) cuando el k óptimo es monótono en j, recurriendo sobre rangos de j y de kO(capas · n log n) en vez de O(capas · n²).
Recursión y memoizaciónResolver un problema llamándose a sí mismo sobre casos más chicos, y anotar cada resultado para no recalcularloCon memo: O(estados × trabajo por estado). Sin memo, una recurrencia con dos llamadas es exponencial: fib(30) hace 2.692.537 llamadas, y con memo, 59.
Subsecuencia creciente más larga (LIS)El largo de la subsecuencia estrictamente creciente más larga de un arreglo (los elementos no tienen que ser contiguos)O(n log n) con la versión de abajo. La DP directa es O(n²) y sirve hasta n ≈ 5000.

Estructuras de Datos

AlgoritmoQué resuelveCosto
Deque monótona (ventana deslizante)Mantiene una cola doble con los candidatos de una ventana en orden decreciente (o creciente), de modo que el frente es siempre el máximo (o el mínimo) de la ventana actualO(n) amortizado: cada índice entra y sale de la deque exactamente una vez. La versión 2D sobre una matriz n×m es O(n·m).
Dos punteros y ventana deslizanteRecorre la secuencia con dos índices que solo avanzan, manteniendo un segmento (la ‘ventana’) que cumple una condiciónO(n) amortizado: cada puntero recorre el arreglo a lo más una vez en total, aunque una iteración mueva varios pasos.
Stack monótonoMantiene una pila creciente/decreciente para hallar, para cada elemento, el siguiente/anterior mayor o menor, en O(n) totalO(n) (cada índice entra y sale una vez).

Greedy

AlgoritmoQué resuelveCosto
Greedy y argumento de intercambioToma en cada paso la decisión localmente mejor y no mira atrás; el argumento de intercambio es la herramienta con que se demuestra que esa decisión no cierra la puerta al óptimoO(n log n) casi siempre: el costo es el sort que impone el criterio, y la pasada posterior es O(n).
Ordenamiento y comparadoresOrdenar es la herramienta más barata que existe para revelar estructura: pone juntos los iguales, deja el mínimo y el máximo en los extremos, y habilita la búsqueda binariaO(n log n) con sort. stable_sort mantiene el orden relativo de los empatados (útil cuando ya venías ordenado por otra cosa).

Geometría

AlgoritmoQué resuelveCosto
Barrido (sweep line)Procesa eventos ordenados por una coordenada manteniendo una estructura activa; aquí, la longitud cubierta por una unión de intervalosO(n log n) por el ordenamiento de eventos.
Convex hullLa envolvente convexa de un conjunto de puntos (el polígono convexo mínimo que los contiene), por el método de Andrew (monotone chain)O(n log n) por el ordenamiento.
Producto cruz y orientaciónEl producto cruz indica si tres puntos giran a la izquierda, a la derecha o son colineales — base de casi toda la geometría enteraO(1).

Matemática y Combinatoria

AlgoritmoQué resuelveCosto
Coeficientes binomialesC(n, k) cuenta de cuántas formas puedes elegir k elementos entre n sin importar el ordenO(N²) precálculo; O(1) consulta.
Criba de EratóstenesLista todos los primos hasta n de una pasada, tachando los múltiplos de cada primo que encuentraO(n log log n) tiempo, O(n) memoria.
Euclides extendido (gcd)Calcula gcd(a, b) y además coeficientes x, y tales que a·x + b·y = gcd(a, b)O(log min(a, b)).
Exponenciación rápida (modular)Calcula b^e (mód m) en O(log e) elevando al cuadrado repetidamenteO(log e).
FactorizaciónDescompone un entero en factores primos por división de prueba hasta √nO(√n) por número.
Inclusión-exclusiónCuenta el tamaño de una unión sin contar nada dos veces: suma los conjuntos por separado, resta las intersecciones de a dos, vuelve a sumar las de a tres, y así alternando el signoO(2^k · k) recorriendo los subconjuntos de k conjuntos. Práctico hasta k ≈ 20.
Teoría de juegos (posiciones ganadoras)Decide quién gana un juego por turnos —dos jugadores, información completa, sin azar ni empates— clasificando cada posición en ganadora o perdedora para quien tiene el turnoO(estados × movimientos por estado). En un juego de sustracción con n fichas y |S| movimientos posibles, O(n·|S|).

Constructivos y Ad-hoc

AlgoritmoQué resuelveCosto
BacktrackingRecorre sistemáticamente todas las opciones construyendo la solución paso a paso y deshaciendo al retrocederDepende de lo que genere: 2^n subconjuntos (n ≤ 20-25), n! permutaciones (n ≤ 10-11). Las podas bajan mucho el caso real.

Búsqueda Binaria

AlgoritmoQué resuelveCosto
Búsqueda binaria clásicaEncuentra un elemento —o la primera posición que cumple una condición— en una secuencia ordenada, descartando la mitad de los candidatos en cada pasoO(log n) por consulta. Si hay que ordenar primero, O(n log n) una sola vez y después cada consulta sigue siendo O(log n).
Búsqueda binaria sobre la respuestaConvierte ‘optimizar X’ en ‘decidir si X es factible’ cuando la factibilidad es monótona, y busca binariamente el umbralO(log(rango) · costo del predicado).
Búsqueda ternariaEncuentra el mínimo (o el máximo) de una función unimodal, que baja hasta un punto y después sube, descartando un tercio del rango en cada pasoO(log(rango) · costo de evaluar la función). Sobre enteros, la versión de abajo hace una sola evaluación por paso en vez de dos.

Referencias: Complejidad computacional (qué cabe en el tiempo límite) · Catálogo de estructuras · Ruta de Aprendizaje · por tema: Temas · volver a Referencia.