⚙️ 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 piden | Usa | Costo |
|---|---|---|
| distancia mínima con aristas de igual peso | BFS | O(V+E) |
| camino mínimo con pesos no negativos | Dijkstra | O((V+E) log V) |
| camino mínimo con pesos negativos | Bellman-Ford | O(n·m) |
| distancias entre todas las parejas (n chico) | Floyd-Warshall | O(n³) |
Estructura de un grafo
| Lo que te piden | Usa |
|---|---|
| recorrer todo / contar componentes conexas | DFS · BFS |
| contar regiones o islas en una grilla | Flood fill |
| ordenar tareas con prerrequisitos (y detectar ciclos) | Orden topológico (Kahn) |
| grupos que se alcanzan mutuamente en un grafo dirigido | SCC (Tarjan) |
| aristas o nodos cuya caída desconecta el grafo | Puentes y puntos de articulación |
| conectar todo al mínimo costo | Kruskal (MST) · Prim (MST) |
| emparejar dos grupos (personas ↔ tareas) | Matching bipartito (Kuhn) |
| cuánto “cabe” por una red / corte mínimo | Flujo máximo (Ford-Fulkerson) |
Árboles
| Lo que te piden | Usa |
|---|---|
| el camino más largo del árbol | Diámetro de un árbol |
| la respuesta para cada nodo como raíz | DP en árboles (rerooting) |
| consultas sobre el camino entre dos nodos | LCA con binary lifting · Heavy-Light Decomposition |
| contar caminos que pasan por cada nodo | Centroid decomposition |
Números
| Lo que te piden | Usa |
|---|---|
| todos los primos hasta n | Criba de Eratóstenes |
| los divisores primos de un número | Factorización |
| mcd, mcm, ecuaciones con enteros | Euclides extendido (gcd) |
| aᵇ mod m con b gigante | Exponenciación rápida (modular) |
| contar combinaciones C(n, k) | Coeficientes binomiales |
| contar los que cumplen alguna de varias condiciones | Inclusión-exclusión |
Geometría
| Lo que te piden | Usa |
|---|---|
| hacia qué lado gira / de qué lado cae un punto | Producto cruz y orientación |
| el polígono que envuelve a todos los puntos | Convex hull |
| procesar eventos ordenados (intervalos, choques) | Barrido (sweep line) |
Greedy y juegos
| Lo que te piden | Usa |
|---|---|
| tomar la decisión obvia… y poder demostrar que sirve | Greedy y argumento de intercambio |
| quién gana si los dos juegan perfecto | Teoría de juegos (posiciones ganadoras) |
Programación dinámica
| Lo que te piden | Usa |
|---|---|
| una recurrencia que se repite a sí misma | Recursión y memoización |
| el subarreglo contiguo de suma máxima | Kadane (subarreglo de suma máxima) |
| juntar/partir por tramos, o un juego por los extremos | DP de intervalos |
| elegir objetos sin pasarse de una capacidad | Mochila 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 ≤ 20 | DP con bitmask |
Optimizar y buscar
| Lo que te piden | Usa |
|---|---|
| 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 ≤ x | Búsqueda binaria clásica |
| el subarreglo más corto/largo que cumple una condición | Dos 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 elemento | Stack monótono |
| el máximo o mínimo de cada ventana de largo k | Deque monótona (ventana deslizante) |
| minimizar una función que baja y después sube | Búsqueda ternaria |
| una DP O(n²) con transiciones lineales que no cabe | Convex hull trick (Li Chao) |
| una DP de intervalos O(n³) que no cabe | Optimización de Knuth |
| una DP por capas cuyo óptimo es monótono | Optimización divide y vencerás (DP) |
| una DP que pide exactamente k grupos y es convexa en k | Aliens trick (optimización lagrangiana) |
📚 Todos, por tema
Grafos
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| BFS | Recorrido por niveles desde un origen; da la distancia mínima en aristas (grafo no ponderado) a todos los nodos | O(V + E). |
| Bellman-Ford | Camino mínimo desde un origen admitiendo pesos negativos; detecta ciclos negativos alcanzables | O(V·E). |
| DFS | Recorre un grafo metiéndose hasta el fondo por cada rama antes de retroceder | O(V + E): cada nodo y cada arista se tocan una vez. |
| Dijkstra | Camino mínimo desde un origen en grafos con pesos NO negativos | O((V + E) log V) con priority_queue. |
| Flood fill | Pinta toda la región conectada a una celda de una grilla | O(filas × columnas): cada celda se visita una vez. |
| Floyd-Warshall | Caminos mínimos entre TODOS los pares de vértices, por DP sobre vértices intermedios | O(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ínimo | O(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 DSU | O(E log E) por el ordenamiento. |
| Matching bipartito (Kuhn) | Emparejamiento máximo en un grafo bipartito buscando caminos aumentantes con DFS | O(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 v | O(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 nuevo | O(E log V) con priority_queue. |
| Puentes y puntos de articulación | Halla las aristas (puentes) y vértices (puntos de articulación) cuya eliminación desconecta el grafo, con tiempos de llegada y low-link | O(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 inverso | O(V + E). |
Árboles
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| Centroid decomposition | Construye el ‘árbol de centroides’: recursivamente elige el centroide, lo quita y recurre | Construcció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 abajo | O(n). |
| Diámetro de un árbol | La 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 lejano | O(n). |
| Heavy-Light Decomposition | Descompone 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
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| 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 partes | O(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 bitmask | Usa un número entero como conjunto: el bit i dice si el elemento i ya fue usado | O(2^n · n) o O(2^n · n²) según la transición. Cabe hasta n ≈ 20-22. |
| DP de intervalos | La DP cuyo estado es un segmento: dp[l][r] = la mejor respuesta para el trozo que va de l a r | O(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 pasada | O(n) tiempo y O(1) memoria. |
| Mochila 0-1 | Elige un subconjunto de objetos, cada uno con peso y valor, para maximizar el valor sin pasarse de una capacidad | O(n · C) tiempo y O(C) memoria con el truco de una sola fila. |
| Optimización de Knuth | Acelera 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 vecinos | O(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 k | O(capas · n log n) en vez de O(capas · n²). |
| Recursión y memoización | Resolver un problema llamándose a sí mismo sobre casos más chicos, y anotar cada resultado para no recalcularlo | Con 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
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| 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 actual | O(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 deslizante | Recorre la secuencia con dos índices que solo avanzan, manteniendo un segmento (la ‘ventana’) que cumple una condición | O(n) amortizado: cada puntero recorre el arreglo a lo más una vez en total, aunque una iteración mueva varios pasos. |
| Stack monótono | Mantiene una pila creciente/decreciente para hallar, para cada elemento, el siguiente/anterior mayor o menor, en O(n) total | O(n) (cada índice entra y sale una vez). |
Greedy
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| Greedy y argumento de intercambio | Toma 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 óptimo | O(n log n) casi siempre: el costo es el sort que impone el criterio, y la pasada posterior es O(n). |
| Ordenamiento y comparadores | Ordenar 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 binaria | O(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
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| Barrido (sweep line) | Procesa eventos ordenados por una coordenada manteniendo una estructura activa; aquí, la longitud cubierta por una unión de intervalos | O(n log n) por el ordenamiento de eventos. |
| Convex hull | La 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ón | El producto cruz indica si tres puntos giran a la izquierda, a la derecha o son colineales — base de casi toda la geometría entera | O(1). |
Matemática y Combinatoria
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| Coeficientes binomiales | C(n, k) cuenta de cuántas formas puedes elegir k elementos entre n sin importar el orden | O(N²) precálculo; O(1) consulta. |
| Criba de Eratóstenes | Lista todos los primos hasta n de una pasada, tachando los múltiplos de cada primo que encuentra | O(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 repetidamente | O(log e). |
| Factorización | Descompone un entero en factores primos por división de prueba hasta √n | O(√n) por número. |
| Inclusión-exclusión | Cuenta 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 signo | O(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 turno | O(estados × movimientos por estado). En un juego de sustracción con n fichas y |S| movimientos posibles, O(n·|S|). |
Constructivos y Ad-hoc
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| Backtracking | Recorre sistemáticamente todas las opciones construyendo la solución paso a paso y deshaciendo al retroceder | Depende 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
| Algoritmo | Qué resuelve | Costo |
|---|---|---|
| Búsqueda binaria clásica | Encuentra un elemento —o la primera posición que cumple una condición— en una secuencia ordenada, descartando la mitad de los candidatos en cada paso | O(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 respuesta | Convierte ‘optimizar X’ en ‘decidir si X es factible’ cuando la factibilidad es monótona, y busca binariamente el umbral | O(log(rango) · costo del predicado). |
| Búsqueda ternaria | Encuentra 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 paso | O(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.