فرّق واحكم يحل مشكلة ما بـ (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).
استخدمه عندما تنقسم المشكلة بشكل نظيف إلى مشاكل فرعية مستقلة. إذا كانت المشاكل الفرعية متداخلة، فاختر البرمجة الديناميكية بدلاً من ذلك (لتجنب إعادة الحساب). يمكن أن تهيمن تكاليف الاستدعاء العودي وخطوة الدمج على المدخلات الصغيرة.
فرّق واحكم هو نموذج قابل لإعادة الاستخدام يقف وراء جزء ضخم من الخوارزميات الفعالة.
التعرف على هذا النموذج يتيح لك اشتقاق وتحليل خوارزميات جديدة بسرعة من خلال العلاقات التكرارية.
كما أنه يتماشى بشكل طبيعي مع التوازي، حيث يمكن للمشاكل الفرعية المستقلة أن تعمل بشكل متزامن.