Divide and conquer کسی مسئلے کو (1) اسے چھوٹے subproblems میں تقسیم کرتے ہوئے، (2) ہر ایک کو recursively حل کرتے ہوئے، اور (3) نتائج کو ملاتے ہوئے حل کرتا ہے۔ بہت سے موثر algorithms اس template کی پیروی کرتے ہیں۔
اگر subproblems آزاد ہوں اور تیزی سے سکڑتے ہوں، تو کل کام ایک recurrence کی پیروی کرتا ہے جسے آپ 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)۔
جب کوئی مسئلہ صاف طریقے سے آزاد subproblems میں تقسیم ہو تو استعمال کریں۔ اگر subproblems overlap کریں، تو dynamic programming کو ترجیح دیں (دوبارہ حساب سے بچنے کے لیے)۔ Recursion کے overhead اور combine step چھوٹے inputs کے لیے حاوی ہو سکتے ہیں۔
Divide and conquer موثر algorithms کے بہت بڑے حصے کے پیچھے ایک دوبارہ استعمال ہونے والا blueprint ہے۔
اس pattern کو پہچاننا آپ کو recurrences کے ساتھ نئے algorithms تیزی سے اخذ اور تجزیہ کرنے دیتا ہے۔
یہ parallelism پر بھی قدرتی طریقے سے نقشہ بناتا ہے، کیونکہ آزاد subproblems بیک وقت چل سکتے ہیں۔