Divide y conquistar resuelve un problema (1) dividiéndolo en subproblemas más pequeños, (2) conquistando cada uno recursivamente, y (3) combinando los resultados. Muchos algoritmos eficientes siguen esta plantilla.
Si los subproblemas son independientes y se reducen rápidamente, el trabajo total sigue una recurrencia que puedes analizar con el Teorema Maestro.
def max_dc(arr, lo, hi):
if lo == hi: # base case: one element
return arr[lo]
mid = (lo + hi) // 2
left = max_dc(arr, lo, mid) # conquer left
right = max_dc(arr, mid + 1, hi) # conquer right
return max(left, right) # combine
max_dc([3, 9, 2, 7], 0, 3) # -> 9
A menudo T(n) = a·T(n/b) + f(n); para merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Úsalo cuando un problema se divide claramente en subproblemas independientes. Si los subproblemas se solapan, prefiere programación dinámica en su lugar (para evitar recalcular). La sobrecarga de recursión y el paso de combinación pueden dominar para entradas pequeñas.
Dividir y conquistar es una plantilla reutilizable detrás de una gran fracción de algoritmos eficientes.
Reconocer el patrón te permite derivar y analizar nuevos algoritmos rápidamente con recurrencias.
También se mapea naturalmente en paralelismo, ya que los subproblemas independientes pueden ejecutarse concurrentemente.