فرّق تَسُد (Divide and Conquer): شرح مبسّط لأهم استراتيجية في الخوارزميات مع أمثلة عملية

فرّق تَسُد (Divide and Conquer) هو أسلوب لتصميم الخوارزميات يقوم على فكرة واحدة بسيطة: بدل مواجهة مشكلة كبيرة دفعة واحدة، تقسّمها إلى نسخ أصغر من المشكلة نفسها، تحلّ كل نسخة على حدة، ثم تدمج الحلول الصغيرة لتحصل على حل المشكلة الأصلية. هذا هو جوهر خوارزميات شهيرة مثل الفرز بالدمج (Merge Sort) والبحث الثنائي (Binary Search)، وهو ما يجعلها أسرع بكثير من الحلول المباشرة.

الفكرة الجوهرية التي يغفلها كثيرون: النسخ الأصغر يجب أن تكون من النوع نفسه للمشكلة الأصلية. لذلك يُنفَّذ هذا الأسلوب عادةً عبر الاستدعاء الذاتي (Recursion)، حيث تستدعي الدالة نفسها على أجزاء أصغر حتى تصل إلى حالة بسيطة يسهل حلها مباشرة.

الخطوات الثلاث

كل خوارزمية من هذا النوع تمرّ بثلاث مراحل:

1. التقسيم (Divide): قسّم المشكلة إلى مشكلتين فرعيتين أو أكثر، كل منها أصغر حجماً.
2. الحل (Conquer): حُلّ كل مشكلة فرعية عبر استدعاء الخوارزمية نفسها. وعندما يصبح الجزء صغيراً جداً (عنصر واحد مثلاً) تحلّه مباشرة؛ هذه تُسمّى الحالة الأساسية (Base Case)، وهي شرط ضروري لكي يتوقف الاستدعاء الذاتي.
3. الدمج (Combine): اجمع حلول الأجزاء لتكوّن حل المشكلة الكاملة. أحياناً تكون هذه الخطوة هي الأثقل حسابياً، وأحياناً تكاد تكون مجانية.

نصيحة عملية: أول ما ينبغي أن تسأل نفسك عند كتابة خوارزمية من هذا النوع هو: «ما الحالة الأساسية التي تُوقف التقسيم؟». نسيان هذه الحالة هو السبب الأول في وقوع الخوارزمية في استدعاء لا نهائي وانهيار المكدس (Stack Overflow).

مثال يوضّح كل شيء: الفرز بالدمج

لنفرز القائمة [5, 2, 8, 1] تصاعدياً:

• تقسيم: نشطر القائمة إلى نصفين: [5, 2] و[8, 1].
• حل: نطبّق الخوارزمية نفسها على كل نصف. [5, 2] تصبح [2, 5]، و[8, 1] تصبح [1, 8]. (كل نصف يُقسَّم بدوره حتى نصل إلى عناصر مفردة، والعنصر المفرد مرتَّب بطبيعته — هذه هي الحالة الأساسية.)
• دمج: ندمج القائمتين المرتّبتين [2, 5] و[1, 8] بمقارنة أوّل عنصر من كل منهما وأخذ الأصغر في كل مرة، فنحصل على [1, 2, 5, 8].

الجمال هنا أن خطوة الدمج تعمل على قائمتين مرتّبتين مسبقاً، وهو ما يجعلها سريعة ومباشرة.

لماذا يكون أسرع؟ فكرة عن التعقيد

الميزة الحقيقية للأسلوب ليست «سهولة الفهم» فحسب، بل تحسين زمن التنفيذ. الفرز بالتبديل الساذج قد يحتاج عدداً من العمليات يتناسب مع مربّع عدد العناصر (n²)، بينما الفرز بالدمج يحتاج ما يتناسب مع n log n فقط. عند فرز مليون عنصر، الفرق بين الأسلوبين قد يكون بين ثوانٍ وساعات.

السبب أن كل مستوى من التقسيم يقلّل حجم المشكلة إلى النصف، فيكون عدد مستويات التقسيم صغيراً (يتناسب مع log n)، وفي كل مستوى ننجز قدراً من العمل يتناسب مع n. علماء الحاسوب يحسبون هذا التعقيد عبر ما يُعرف بـ«نظرية الرئيس» (Master Theorem)، لكن الفكرة الحدسية تكفي للبداية: تقسيم متكرّر إلى النصف يعني عدد خطوات لوغاريتمياً صغيراً.

أشهر الخوارزميات التي تستخدم هذا الأسلوب

الخوارزمية	أين تظهر الخطوات الثلاث؟	الميزة الأساسية
الفرز بالدمج (Merge Sort)	تقسيم للنصف، فرز كل نصف، ثم دمج مرتّب	أداء ثابت n log n في كل الحالات
الفرز السريع (Quick Sort)	اختيار محور، تقسيم حوله، ثم فرز الجزأين	سريع عملياً وقليل استهلاك الذاكرة
البحث الثنائي (Binary Search)	مقارنة بالعنصر الأوسط، ثم البحث في نصف واحد فقط	إيجاد عنصر في قائمة مرتّبة بخطوات قليلة جداً
ضرب المصفوفات (Strassen)	تقسيم المصفوفة إلى كتل أصغر	ضرب أسرع من الطريقة التقليدية

لاحظ أن البحث الثنائي حالة خاصة لطيفة: بعد التقسيم نتجاهل نصف القائمة كاملاً، فلا حاجة لخطوة دمج على الإطلاق.

متى لا تستخدم فرّق تَسُد؟

هذا الأسلوب ليس حلاً سحرياً لكل مشكلة. تجنّبه أو أعِد التفكير فيه عندما:

• تكون المشكلة صغيرة؛ فتكلفة الاستدعاءات الذاتية المتكرّرة قد تفوق فائدتها. كثير من التطبيقات الواقعية تتحوّل إلى فرز بسيط عندما يصبح الجزء أقل من عدد معيّن من العناصر.
• تتكرّر المشكلات الفرعية نفسها كثيراً؛ فحينها تكون البرمجة الديناميكية (Dynamic Programming) أنسب لأنها تخزّن الحلول بدل إعادة حسابها. مثال شهير: حساب متتالية فيبوناتشي بالتقسيم يعيد الحساب نفسه ملايين المرات دون داعٍ.
• تكون خطوة الدمج مكلفة جداً إلى حدّ يلتهم أي مكسب من التقسيم.

خطأ شائع يقع فيه المبتدئون

كثيرون يظنون أن مجرد تقسيم المشكلة يكفي. الحقيقة أن صحّة خطوة الدمج هي التي تحدّد صحّة الخوارزمية كلها. في الفرز بالدمج مثلاً، إن دمجت النصفين دون مقارنة سليمة، ستحصل على قائمة مقسّمة لكنها غير مرتّبة. القاعدة: اختبر خطوة الدمج على مثال صغير جداً بيدك قبل الوثوق بالكود.

الأسئلة الشائعة

هل فرّق تَسُد هو نفسه الاستدعاء الذاتي (Recursion)؟ ليس تماماً. الاستدعاء الذاتي هو الأداة التي نُنفّذ بها الأسلوب غالباً، لكن فرّق تَسُد استراتيجية تصميم أوسع تشترط تقسيم المشكلة إلى أجزاء مستقلّة ثم دمجها. كل خوارزميات فرّق تَسُد استدعائية تقريباً، لكن ليس كل استدعاء ذاتي يتبع هذا الأسلوب.

ما الفرق بينه وبين البرمجة الديناميكية؟ كلاهما يقسّم المشكلة، لكن البرمجة الديناميكية تُستخدم حين تتداخل المشكلات الفرعية وتتكرّر، فتُخزَّن نتائجها لتجنّب إعادة الحساب. أما فرّق تَسُد فيفترض أن الأجزاء مستقلّة ولا تتكرّر.

هل الفرز السريع (Quick Sort) دائماً أسرع من الفرز بالدمج؟ غالباً أسرع عملياً ويستهلك ذاكرة أقل، لكن في أسوأ الحالات (اختيار محور سيّئ) قد يتدهور أداؤه. الفرز بالدمج أبطأ قليلاً لكنه ثابت الأداء ومناسب حين تحتاج ضماناً بعدم التدهور.

من أين أبدأ لتعلّمه عملياً؟ ابدأ بكتابة البحث الثنائي بنفسك لأنه أبسط مثال، ثم انتقل إلى الفرز بالدمج لأنه يوضّح خطوة الدمج بجلاء، وجرّب دائماً تتبّع الخوارزمية يدوياً على قائمة من أربعة عناصر قبل تشغيل الكود.