Data Structure & Algorithms
Divide and conquer, relaciones de recurrencia, recursion trees, Master theorem y análisis del trabajo de dividir, resolver y combinar.
Divide and conquer separa un problema en subproblemas de la misma forma, los resuelve y combina sus resultados.
divide → conquer → combineLa técnica es útil cuando los subproblemas son suficientemente independientes y la combinación es más barata que resolver el problema original directamente.
function solve(problem: Problem): Result {
if (isSmall(problem)) {
return solveDirectly(problem);
}
const parts = divide(problem);
const partialResults = parts.map(solve);
return combine(partialResults);
}No toda recursión es divide and conquer. Una función que reduce n a n - 1 tiene una estructura recursiva, pero no necesariamente divide en subproblemas independientes.
Cada algoritmo tiene una recurrencia diferente.
Una recurrencia describe el costo de una llamada en función de llamadas menores.
T(n) = T(n/2) + O(1)Solo continúa una mitad y hace trabajo constante para comparar y actualizar límites.
Resultado: O(log n).
T(n) = 2T(n/2) + O(n)Resuelve dos mitades y combina n elementos.
Resultado: O(n log n).
T(n) = T(n - 1) + O(1)Resultado: O(n).
T(n) = T(n - 1) + T(n - 2) + O(1)Los subproblemas se repiten. El tiempo crece exponencialmente; no es un divide and conquer eficiente. Memoization cambia el grafo de ejecución al calcular cada estado una vez.
Expande la recurrencia por niveles.
Para merge sort:
nivel 0: n costo n
/ \
nivel 1: n/2 n/2 costo n
/ \ / \
nivel 2: n/4 ... n/4 costo n
...
altura: log nCada nivel suma O(n) y hay O(log n) niveles:
O(n) × O(log n) = O(n log n)Este método ayuda a ver cuánto trabajo existe por nivel y cuántos niveles se crean.
Propón una cota y demuéstrala por inducción.
Para:
T(n) = 2T(n/2) + nSupón T(n/2) ≤ c(n/2) log(n/2) y sustituye:
T(n) ≤ cn log(n/2) + n
= cn(log n - 1) + n
= cn log n - cn + nPara un c adecuado, esto es O(n log n).
La sustitución aporta rigor cuando el árbol es menos evidente.
Para recurrencias de la forma:
T(n) = aT(n/b) + f(n)a: cantidad de subproblemas;n/b: tamaño de cada uno;f(n): trabajo fuera de las llamadas.Compara f(n) con:
n^(log_b a)Si f(n) crece polinómicamente más lento:
T(n) = Θ(n^(log_b a))Ejemplo:
T(n) = 4T(n/2) + n
n^(log₂4) = n²
resultado Θ(n²)Si:
f(n) = Θ(n^(log_b a) log^k n)entonces se añade un factor logarítmico:
T(n) = Θ(n^(log_b a) log^(k+1) n)Merge sort es el caso k = 0: Θ(n log n).
Si f(n) crece polinómicamente más rápido y cumple una condición de regularidad:
T(n) = Θ(f(n))El teorema no aplica a recurrencias como T(n - 1), subproblemas de tamaños desiguales generales o relaciones no ajustadas a esa forma.
Las categorías ayudan a ver la estructura, pero no sustituyen el análisis concreto.
Calcular base^exponent multiplicando exponent veces cuesta O(exponent).
Usa:
x^n = (x^(n/2))² si n es par
x^n = x · (x^floor(n/2))² si n es imparfunction power(base: number, exponent: number): number {
if (!Number.isInteger(exponent) || exponent < 0) {
throw new RangeError("Exponent must be a non-negative integer");
}
if (exponent === 0) return 1;
const half = power(base, Math.floor(exponent / 2));
const squared = half * half;
return exponent % 2 === 0 ? squared : base * squared;
}La llamada a half se hace una sola vez. Escribirla dos veces:
power(base, n / 2) * power(base, n / 2)crearía dos subárboles y perdería la mejora.
Tiempo: O(log exponent). Call stack: O(log exponent).
Merge sort crea mitades independientes. Fibonacci crea subproblemas superpuestos. Esa diferencia decide si divide and conquer puro evita trabajo o si necesitas DP.
fib(5)
├─ fib(4)
│ └─ fib(3)
└─ fib(3) ← repetidoSi diferentes ramas vuelven al mismo estado, considera memoization.
Dividir puede ser barato y combinar costoso, o al revés.
O(1) conceptual y combina en O(n).O(n) y combina en O(1) después de recursión.Identificar dónde se hace el trabajo evita recurrencias incorrectas.
Una implementación puede cambiar la complejidad espacial:
const left = values.slice(0, middle);slice copia elementos. Si el algoritmo se describe por índices, pero el código crea arrays en cada nivel, debes contar esas asignaciones.
En merge sort, el pico de memoria suele seguir siendo O(n), pero las constantes y presión de garbage collection aumentan.
Subproblemas independientes pueden ejecutarse en paralelo. Sin embargo:
La estructura permite paralelismo; no lo hace gratis.
combine.O(log n) solo porque el tamaño se divide, aunque existan dos ramas.slice, buffers y call stack.T(n/2) y 2T(n/2) producen comportamientos muy distintos.¿Por qué T(n) = 2T(n/2) + O(1) no es O(log n)?
Porque se ejecutan dos ramas en cada nivel. El árbol tiene 2^log n = n hojas y una cantidad total lineal de nodos, por lo que la recurrencia es Θ(n).