Divide y vencerás y teorema maestro

Mergesort, la búsqueda binaria y la multiplicación rápida de enteros comparten una forma: el problema se parte, cada parte se resuelve igual y los resultados se combinan. Lo que cambia entre uno y otro es dónde está el trabajo real, y de eso depende el costo final.

Dividir, resolver y combinar

El esquema tiene tres pasos: dividir la entrada en subproblemas del mismo tipo, resolverlos recursivamente y combinar las soluciones. La recursión corta en un caso base lo bastante chico como para resolver directo.

La condición para que sirva es que los subproblemas sean independientes. Si se pisan entre sí y se recalculan, hace falta memorizar resultados, y eso ya es programación dinámica.

El costo se escribe como recurrencia

El costo se escribe como una recurrencia. Si el problema de tamaño $n$ se parte en $a$ subproblemas de tamaño $n/b$ y dividir más combinar cuesta $f(n)$:

Mergesort es $a=2$, $b=2$, $f(n)=\Theta(n)$: dos mitades y una fusión lineal. La búsqueda binaria es $a=1$, $b=2$, $f(n)=\Theta(1)$: una sola mitad y nada que combinar.

El árbol de llamadas lo explica sin cuentas

La forma de entender la recurrencia es dibujar el árbol de llamadas. Tiene profundidad $\log_b n$, y en el nivel $i$ hay $a^i$ subproblemas de tamaño $n/b^i$.

La cantidad de hojas es $n^{\log_b a}$, y ese número es la clave: representa el trabajo que cuesta la recursión pura, sin contar lo que se hace al dividir y combinar. Todo el análisis se reduce a comparar ese trabajo de las hojas contra $f(n)$.

El teorema maestro y sus tres casos

Eso es el teorema maestro. Comparando $f(n)$ con $n^{\log_b a}$ hay tres casos:

• Si $f(n)$ crece más lento, mandan las hojas: $T(n)=\Theta\!\left(n^{\log_b a}\right)$.
• Si crecen igual, cada nivel aporta lo mismo y se multiplica por la cantidad de niveles: $T(n)=\Theta\!\left(n^{\log_b a}\log n\right)$.
• Si $f(n)$ crece más rápido, manda la raíz: $T(n)=\Theta(f(n))$.

Mergesort cae en el segundo caso —$n^{\log_2 2}=n$ contra $f(n)=n$— y por eso da $n\log n$.

Los extremos: búsqueda binaria y mergesort

Los casos extremos se ven mejor con ejemplos. La búsqueda binaria tiene una sola hoja por nivel: $n^{\log_2 1}=1$, y el costo termina siendo $\Theta(\log n)$, puro camino.

La multiplicación de Karatsuba parte dos números en mitades y, con un truco algebraico, usa tres multiplicaciones en vez de cuatro: $a=3$, $b=2$, y el costo baja de $n^2$ a $n^{\log_2 3}\approx n^{1.58}$. Bajar $a$ de 4 a 3 cambia el exponente: en el primer caso, lo único que importa es cuántos subproblemas hay.

Lo que el teorema no cubre

El teorema no cubre todo. Pide subproblemas del mismo tamaño y un $f(n)$ razonable; con particiones desparejas —quicksort en su peor caso— hay que analizar a mano o acotar con el árbol de recursión.

Y hay un costo que la recurrencia no muestra: cada llamada usa pila. Con profundidad logarítmica no importa, pero una recursión mal balanceada puede desbordarla mucho antes de que el tiempo sea un problema.

El teorema maestro, y cuándo no alcanza

La forma corta de usarlo es comparar $n^{\log_b a}$ —el trabajo total de las hojas— con $f(n)$ —el de combinar—. Si las hojas dominan, el resultado es el de las hojas; si domina la combinación, el resultado es $f(n)$; si empatan, se multiplica por $\log n$.

Cierre

Divide y vencerás sirve cuando los subproblemas son independientes. Su costo se escribe como $a\,T(n/b)+f(n)$, y el teorema maestro lo resuelve comparando $f(n)$ con el trabajo de las hojas $n^{\log_b a}$: gana el más grande, y si empatan aparece el factor $\log n$.