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).
ஒரு சிக்கல் சுயாதீன துணைச் சிக்கல்களாக சுத்தமாக பிரியும் போது பயன்படுத்தவும். துணைச் சிக்கல்கள் ஒன்றுடன் ஒன்று சேர்ந்திருந்தால், மீண்டும் கணக்கிடுவதை தவிர்க்க dynamic programming ஐ விரும்பவும். சுழல்நிலை மேல்நிலையும் இணைக்கும் படியும் சிறிய உள்ளீடுகளுக்கு மேல் வந்துவிடக் கூடும்.
Divide and conquer என்பது பெரிய பகுதியான திறமையான வழிமுறைகளின் பின்னணியில் உள்ள மீண்டும் பயன்படுத்தக்கூடிய வார்ப்பு.
இந்த வடிவத்தை அறிந்துகொள்வது சுழல்நிலைகளுடன் விரைவாக புதிய வழிமுறைகளைப் பெற்று பகுப்பாய்வு செய்ய உங்களை அனுமதிக்கிறது.
சுயாதீன துணைச் சிக்கல்கள் ஒரே நேரத்தில் இயங்கக் கூடிய தன்மையாக இது இயற்கையாக மேப் செய்கிறது.