Tema
Divide y vencerás
- Algoritmos
- Nivel intermedio
La estrategia de divide y vencerás parte el problema en subproblemas independientes del mismo tipo, los resuelve por recursión y combina sus soluciones.
Nombre en inglés
Divide and conquer
Intuición
El ahorro no está en dividir, sino en que combinar cueste poco. La ordenación por mezcla gana porque fundir dos listas ordenadas es lineal, y el método de Karatsuba gana porque cambia cuatro productos por tres a cambio de unas sumas. Cuando los subproblemas se solapan y se repiten, la estrategia que corresponde ya no es esta sino la programación dinámica.
Fórmula
T(n) = a T(n/b) + coste de combinar ; Karatsuba: T(n) = 3 T(n/2) + O(n) = O(n^{1.585})
Ejemplo resuelto
Para multiplicar 12 por 34 con el método de Karatsuba se separan las cifras en 1 y 2 y en 3 y 4. Se calculan tres productos: 1 por 3 da 3, 2 por 4 da 8 y la suma 1 más 2 por la suma 3 más 4 da 21. El término medio es 21 menos 3 menos 8, es decir 10. El resultado es 3 por 100 más 10 por 10 más 8, es decir 408, que coincide con el producto directo.
Errores frecuentes
- Recursionar sin un caso base eficiente: Por debajo de cierto umbral el coste de las llamadas supera al del método directo, motivo por el cual las implementaciones reales cambian al método de inserción en las hojas.
- Aplicar divide y vencerás a subproblemas que se repiten: El árbol de llamadas recalcula lo mismo una y otra vez, como ocurre con la sucesión de Fibonacci ingenua, que cuesta tiempo exponencial.
- Contar mal el coste de combinar: Si la fusión se programa con concatenaciones que copian, la etapa deja de ser lineal y la recurrencia cambia de caso.
Ejercicio
Un algoritmo divide el problema en tres partes de tamaño n dividido entre 3 y combina en tiempo lineal. ¿Cuál es su coste?
Ver la solución
Se tiene T(n) = 3 T(n/3) más n, con log_3(3) igual a 1, de modo que el coste de combinar empata con el de las hojas y aparece el factor logarítmico.
Respuesta: Theta(n log n)