Divide and conquer એક સમસ્યાને (1) તેને નાની સબપ્રોબ્લેમ્સમાં વિભાજિત કરીને, (2) દરેકને જીતીને પુનરાવર્તિતપણે, અને (3) પરિણામોને જોડીને ઉકેલે છે. ઘણા કુશળ અલ્ગોરિધમ આ નમૂનાને અનુસરે છે.
જો સબપ્રોબ્લેમ્સ સ્વતંત્ર હોય અને ઝડપથી સંકોચાય, તો કુલ કાર્ય એક પુનરાવર્તી સમીકરણ અનુસરે છે જેને તમે 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
હોય તો T(n) = a·T(n/b) + f(n); merge sort માટે, T(n) = 2T(n/2) + O(n) = O(n log n).
જ્યારે સમસ્યા સ્વતંત્ર સબપ્રોબ્લેમ્સમાં સ્વચ્છતાથી વિભાજિત થાય તેવા સમયે ઉપયોગ કરો. જો સબપ્રોબ્લેમ્સ ઓવરલેપ થાય, તો પુનઃગણનાને ટાળવા માટે ગતિશીલ પ્રોગ્રામિંગ પસંદ કરો. પુનરાવર્તી ઓવરહેડ અને જોડાણ પગલું નાના ઇનપુટ માટે પ્રભાવશાળી બની શકે છે.
Divide and conquer એક પુનઃઉપયોગી બ્લુપ્રિન્ટ છે જે અત્યંત કુશળ અલ્ગોરિધમ્સના વિશાળ અંશ પાછળ છે.
પેટર્ન ઓળખવાથી તમે નવા અલ્ગોરિધમ્સ ઝડપથી પુનરાવર્તી સમીકરણો સાથે લીધવા અને વિશ્લેષણ કરી શકો છો.
તે સ્વાભાવિકપણે સમાંતરતાને મેપ કરે છે, કારણ કે સ્વતંત્ર સબપ્રોબ્લેમ્સ સમવર્તી રીતે ચલાવી શકાય છે.