Divisão e conquista resolve um problema ao (1) dividir em subproblemas menores, (2) conquistar cada um recursivamente, e (3) combinar os resultados. Muitos algoritmos eficientes seguem este modelo.
Se subproblemas são independentes e diminuem rapidamente, o trabalho total segue uma recorrência que você pode analisar com o Teorema Mestre.
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
Muitas vezes T(n) = a·T(n/b) + f(n); para merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Use quando um problema se divide claramente em subproblemas independentes. Se subproblemas se sobrepõem, prefira programação dinâmica em vez disso (para evitar recálculo). A overhead de recursão e a etapa de combinação podem dominar para entradas pequenas.
Divisão e conquista é um modelo reutilizável por trás de uma grande fração de algoritmos eficientes.
Reconhecer o padrão permite derivar e analisar novos algoritmos rapidamente com recorrências.
Também mapeia naturalmente para paralelismo, pois subproblemas independentes podem ser executados simultaneamente.