Divide en conquer lost een probleem op door (1) het te verdelen in kleinere deelproblemen, (2) elk overwonnen recursief, en (3) de resultaten te combineren. Veel efficiënte algoritmen volgen dit sjabloon.
Als deelproblemen onafhankelijk zijn en snel krimpen, volgt het totale werk een recurrence die je kunt analyseren met de 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
Vaak T(n) = a·T(n/b) + f(n); voor merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Gebruik wanneer een probleem schoon splitst in onafhankelijke deelproblemen. Als deelproblemen overlappen, verkies dan dynamic programming (om herberekening te voorkomen). Recursieoverhead en de combinatiestap kunnen overheersend zijn voor kleine invoeren.
Divide en conquer is een herbruikbare blauwdruk achter een groot deel van efficiënte algoritmen.
Het patroon herkennen stelt je in staat om snel nieuwe algoritmen af te leiden en te analyseren met recurrences.
Het wordt ook natuurlijk toegepast op parallelisme, omdat onafhankelijke deelproblemen gelijktijdig kunnen worden uitgevoerd.