Las recurrencias describen el costo de un algoritmo recursivo en función del tamaño de entrada. Al resolverlas podemos predecir cómo crece su tiempo de ejecución antes de probarlo con datos enormes.
Cuando un algoritmo se llama a sí mismo con problemas más pequeños, su costo depende del costo de esas llamadas y del trabajo adicional realizado en cada nivel. Una recurrencia permite expresar esa relación con precisión.
Si T(n) representa el tiempo para una entrada de tamaño n, una forma típica es T(n) = costo de los subproblemas + trabajo local. El objetivo no es medir milisegundos exactos, sino clasificar el crecimiento cuando n aumenta.
Para construir T(n) debemos identificar tres elementos: el caso base, el tamaño y cantidad de subproblemas, y el trabajo que no pertenece a las llamadas recursivas.
Las constantes c representan costos acotados. En análisis asintótico suelen omitirse al final, pero mantenerlas al plantear la relación ayuda a comprender qué parte del algoritmo se está contando.
El caso base indica cuándo la recursión termina. Para entradas de tamaño 0 o 1, muchos algoritmos realizan una cantidad constante de operaciones; por eso escribimos T(1) = Θ(1).
Una recurrencia sin caso base está incompleta: no especifica dónde detener la expansión ni determina una solución única.
Si cada llamada resuelve un subproblema cuyo tamaño disminuye en una unidad y realiza trabajo constante, tenemos:
Este patrón aparece en factorial recursivo, recorridos lineales recursivos y funciones que eliminan un elemento por llamada.
function sumarRecursivo(numeros, indice = 0) {
if (indice === numeros.length) return 0;
return numeros[indice] + sumarRecursivo(numeros, indice + 1);
}
console.log(sumarRecursivo([4, 7, 2, 9])); // 22La llamada sobre un arreglo de n elementos realiza una suma y llama a un problema de n - 1 elementos. Su costo cumple T(n) = T(n - 1) + c, por lo que es lineal.
Si una llamada reduce el problema aproximadamente a la mitad y el trabajo local es constante, el número de niveles es logarítmico.
Reducir a la mitad es mucho más efectivo que reducir de a uno: para un millón de elementos, log2(1 000 000) es cercano a 20.
function busquedaBinaria(numeros, buscado, inicio = 0, fin = numeros.length - 1) {
if (inicio > fin) return -1;
const centro = Math.floor((inicio + fin) / 2);
if (numeros[centro] === buscado) return centro;
if (buscado < numeros[centro]) {
return busquedaBinaria(numeros, buscado, inicio, centro - 1);
}
return busquedaBinaria(numeros, buscado, centro + 1, fin);
}
const ordenados = [2, 5, 8, 11, 16, 21, 29, 34, 40];
console.log(busquedaBinaria(ordenados, 21)); // 5
console.log(busquedaBinaria(ordenados, 22)); // -1En cada llamada se hace un número constante de comparaciones y se conserva solo una mitad. La precondición de ordenamiento es indispensable para que este descarte sea correcto.
Merge sort divide el arreglo en dos mitades, ordena cada mitad y después las combina recorriendo todos los elementos. Su recurrencia es:
La dificultad está en que hay dos llamadas por nivel. Un árbol de recurrencia hace visible cómo se distribuye el trabajo.
Para T(n) = 2T(n/2) + cn, en el nivel 0 hay un problema de tamaño n y trabajo cn. En el nivel 1 hay dos problemas de tamaño n/2: el trabajo total es 2 · c(n/2) = cn. Esto se repite en cada nivel.
El árbol no necesita dibujarse físicamente para cada problema. Lo importante es identificar cuántos nodos y cuánto trabajo aparecen en cada nivel.
El siguiente ejemplo cuenta comparaciones durante la combinación. El valor exacto depende del orden de los datos, pero el patrón general es proporcional a n log n.
let comparaciones = 0;
function merge(izquierda, derecha) {
const resultado = [];
let i = 0;
let j = 0;
while (i < izquierda.length && j < derecha.length) {
comparaciones++;
if (izquierda[i] <= derecha[j]) resultado.push(izquierda[i++]);
else resultado.push(derecha[j++]);
}
return resultado.concat(izquierda.slice(i), derecha.slice(j));
}
function mergeSort(numeros) {
if (numeros.length <= 1) return numeros;
const centro = Math.floor(numeros.length / 2);
return merge(mergeSort(numeros.slice(0, centro)), mergeSort(numeros.slice(centro)));
}
console.log(mergeSort([8, 3, 6, 1, 7, 2])); // [1, 2, 3, 6, 7, 8]
console.log(`Comparaciones: ${comparaciones}`); // Comparaciones: 10Consideremos T(n) = 4T(n/2) + c. En cada nivel el número de problemas se multiplica por 4 mientras el tamaño se divide por 2. El trabajo de las hojas termina dominando la suma.
Este patrón surge, por ejemplo, en algoritmos que generan cuatro subproblemas de la mitad del tamaño.
El teorema maestro resuelve muchas recurrencias de divide y vencerás con la forma:
La expresión nlogb(a) representa el trabajo asociado al crecimiento del árbol de subproblemas. La comparación indica si domina el trabajo de las hojas, el trabajo de todos los niveles o el trabajo local.
| Comparación | Resultado | Interpretación |
|---|---|---|
| f(n) es polinómicamente menor que nlogba | Θ(nlogba) | Dominan las hojas. |
| f(n) = Θ(nlogba) | Θ(nlogba log n) | Todos los niveles aportan igual orden. |
| f(n) es polinómicamente mayor y cumple regularidad | Θ(f(n)) | Domina el trabajo local. |
El teorema tiene condiciones técnicas y no se aplica a toda recurrencia. Es una herramienta rápida, no un reemplazo universal del análisis por expansión o árbol.
| Recurrencia | nlogba | Resultado |
|---|---|---|
| T(n) = 2T(n/2) + n | nlog₂2 = n | Θ(n log n) |
| T(n) = 4T(n/2) + 1 | nlog₂4 = n² | Θ(n²) |
| T(n) = T(n/2) + 1 | nlog₂1 = 1 | Θ(log n) |
| T(n) = 2T(n/2) + n² | n | Θ(n²) |
En el último caso, el trabajo local n² es mayor que el trabajo generado por las hojas, por lo que domina la complejidad total.
El método de sustitución propone una cota para T(n) y la prueba por inducción. Por ejemplo, para demostrar T(n) = O(n log n) en merge sort, suponemos T(n/2) ≤ c(n/2)log(n/2) y lo reemplazamos en la recurrencia.
Este método ofrece una justificación formal de una cota propuesta, aunque exige elegir correctamente la hipótesis y tratar los casos base.
No podemos aplicar directamente el teorema maestro si los subproblemas no tienen el mismo tamaño, si se reduce n - 1 en lugar de n/b, si el número de subproblemas cambia o si la forma de f(n) no satisface sus condiciones.
| Recurrencia | Por qué no aplica directamente |
|---|---|
| T(n) = T(n - 1) + 1 | No reduce por un factor constante. |
| T(n) = T(n/3) + T(2n/3) + n | Los subproblemas tienen tamaños distintos. |
| T(n) = T(n/2) + T(n/4) + n | Subproblemas de tamaños distintos. |
| T(n) = T(n/2) + n sin base | La recurrencia está incompleta. |
En esos casos podemos usar expansión, árboles de recurrencia más generales, sustitución u otras técnicas avanzadas.
La recurrencia de tiempo no describe por sí sola la memoria usada. Una función recursiva mantiene una pila de llamadas activa. Para búsqueda binaria, la profundidad es Θ(log n); para una recursión que reduce n en uno, puede ser Θ(n).
Analizar ambos recursos permite elegir implementaciones que funcionen con los límites reales del sistema.
Las recurrencias convierten la estructura de un algoritmo recursivo en una estimación de crecimiento. En el próximo tema estudiaremos el conteo de operaciones, una técnica complementaria para analizar algoritmos iterativos y recursivos.