Divide and Conquer löst ein Problem durch (1) Aufteilen in kleinere Teilprobleme, (2) rekursives Lösen jedes Teilproblems und (3) Kombinieren der Ergebnisse. Viele effiziente Algorithmen folgen diesem Schema.
Wenn Teilprobleme unabhängig sind und schnell schrumpfen, folgt die Gesamtarbeit einer Rekurrenzrelation, die du mit dem Master Theorem analysieren kannst.
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
Often T(n) = a·T(n/b) + f(n); für Merge Sort gilt T(n) = 2T(n/2) + O(n) = O(n log n).
Verwende Divide and Conquer, wenn ein Problem sauber in unabhängige Teilprobleme zerfällt. Wenn Teilprobleme überlappen, bevorzuge Dynamische Programmierung (um Neuberechnung zu vermeiden). Der Rekursions-Overhead und der Kombinationsschritt können bei kleinen Eingaben dominieren.
Divide and Conquer ist ein wiederverwendbares Schema hinter einem großen Teil effizienter Algorithmen.
Das Erkennen des Musters ermöglicht es dir, neue Algorithmen schnell mit Rekurrenzrelationen zu entwickeln und zu analysieren.
Es passt auch natürlich zu Parallelismus, da unabhängige Teilprobleme gleichzeitig laufen können.