Divide et impera risolve un problema (1) dividendolo in sottoproblemi più piccoli, (2) conquistando ricorsivamente ogni sottoproblema, e (3) combinando i risultati. Molti algoritmi efficienti seguono questo schema.
Se i sottoproblemi sono indipendenti e si riducono rapidamente, il lavoro totale segue una ricorrenza che puoi analizzare con il Master Theorem.
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
Spesso T(n) = a·T(n/b) + f(n); per merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Usalo quando un problema si divide in modo netto in sottoproblemi indipendenti. Se i sottoproblemi si sovrappongono, preferisci la programmazione dinamica (per evitare la ricalcolazione). L'overhead della ricorsione e il passo di combinazione possono dominare per input piccoli.
Divide et impera è uno schema riutilizzabile dietro una grande frazione di algoritmi efficienti.
Riconoscere il pattern ti permette di derivare e analizzare rapidamente nuovi algoritmi usando ricorrenze.
Si mappa anche naturalmente al parallelismo, poiché i sottoproblemi indipendenti possono eseguirsi concorrentemente.