Divide and conquer löser ett problem genom att (1) dela upp det i mindre delproblem, (2) lösa var och en rekursivt, och (3) kombinera resultaten. Många effektiva algoritmer följer denna mall.
Om delproblemen är oberoende och krymper snabbt, följer det totala arbetet en rekurrens som du kan analysera med 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
Ofta T(n) = a·T(n/b) + f(n); för merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Använd när ett problem delas upp rent i oberoende delproblem. Om delproblemen överlappar, föredra dynamisk programmering istället (för att undvika omberäkning). Rekursionskostnaden och kombinationssteget kan dominera för små inmatningar.
Divide and conquer är en återanvändbar mall bakom en stor del av effektiva algoritmer.
Att känna igen mönstret låter dig härleda och analysera nya algoritmer snabbt med rekurrenser.
Det mappar också naturligt till parallellism, eftersom oberoende delproblem kan köras samtidigt.