Divide and conquer réitíonn fadhb trí (1) an fhadhb a roinnt ina bhfadhbanna níos lú, (2) gach ceann a bhualadh go athchúrsach, agus (3) na torthaí a chomhcheangal. Leanann go leor halgartam éifeachtúil an teimpléad seo.
Má bhíonn na bhfadhbanna neamhspleácha ann agus má bhíonn siad ag laghdú go tapa, leanann an obair iomlán athfhillteachán ar féidir a anailísiú le .
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
Go minic T(n) = a·T(n/b) + f(n); i gcomhair merge sort, T(n) = 2T(n/2) + O(n) = O(n log n).
Úsáid nuair a scoilteann fhadhb go geal ina bhfadhbanna neamhspleácha. Má fhorleacann na fadhbanna, is fearr claonadh go clár dinimic ina ionad (chun athrialú a sheachaint). Is féidir le brú athchúrsach agus an chéim chomhcheangail glacadh ar bharr do bhreiseanna beaga.
Is teimpléad athúsáidte é divide-and-conquer taobh thiar de chodanna ollmhór de halgartam éifeachtúil.
Leigeann an patrún a aithint do thorthaí agus anailís a dhéanamh ar algartam nua go tapa le athfhillteachán.
Mapáiltear sé go nádúrtha freisin ar chomhthreomharthacht, ó is féidir le fadhbanna neamhspleácha a rith ag an am céanna.