Divide and Conquer
Divide y vencerás divide un problema en subproblemas independientes, los resuelve de forma recursiva y combina los resultados; el teorema maestro suele analizar su complejidad.
Propósito
Ofrecer un paradigma general para diseñar algoritmos eficientes, como mergesort o la transformada rápida de Fourier.
Mecanismo
Tres pasos: dividir (partir en subproblemas), vencer (resolverlos recursivamente), combinar (fusionar las subsoluciones). Teorema maestro: cota asintótica de T(n)=aT(n/b)+f(n). Clásicos: mergesort O(n log n), FFT O(n log n).
Casos de uso
- Diseño de algoritmos
- Ordenación y búsqueda
- Multiplicación de polinomios