Divide și stăpânește rezolvă o problemă prin (1) împărțirea acesteia în subprobleme mai mici, (2) stăpânirea fiecăreia recursiv, și (3) combinarea rezultatelor. Mulți algoritmi eficienți urmează acest șablon.
Dacă subproblemele sunt independente și se micșorează rapid, volumul total de lucru urmează o recurență pe care o puteți analiza cu Teorema Stăpânului.
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
Adesea T(n) = a·T(n/b) + f(n); pentru merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Utilizați atunci când o problemă se împarte curat în subprobleme independente. Dacă subproblemele se suprapun, preferați programarea dinamică în schimb (pentru a evita recalcularea). Supraîncărcarea recursivității și pasul de combinare pot fi dominante pentru intrări mici.
Divide și stăpânește este un șablon reutilizabil în spatele unei fracțiuni mari de algoritmi eficienți.
Recunoașterea modelului vă permite să derivați și analizați noi algoritmi rapid cu recurențe.
De asemenea, se mapează în mod natural la paralelism, deoarece subproblemele independente pot rula concurent.