مبدأ فرق تسد (Divide and Conquer)
إن كثيرا من الخوارزميات تستخدم مبدأ "فرق تسد" أثناء عملها. تتلخص فكرة هذا المبدأ في تقسيم المشكلة المطروحة إلى عدة مشاكل أصغر في الحجم (ونعني بالكبر والصغر هنا هو عدد العناصر التي يتم معالجتها) ومماثلة للمشكلة الكبيرة من حيث المبدأ (عادة ما تكون المشكلات الصغيرة مستقلة عن بعضها ), وبعد حل كل مشكلة صغيرة على حدة تأتي مرحلة تجميع الأجزاء المحلولة بحيث تكون معا حل المشكلة. وهكذا فإن المراحل الأساسية التي تمر بها كل خوارزمية
• مرحلة التفريق أو التقسيم (The Divide Step) وفي هذا المرحلة يتم تحديد حجم المشاكل الصغيرة والتي إليها تنقسم المشكلة الكبيرة.
• مرحلة السيادة (The Conquer Step) وهنا يتم حل المشاكل الصغيرة, كل على حدة.
• مرحلة التجميع (The Combine Step ) وهنا يتم تجميع حلول المشاكل الصغيرة والتي تكون معا حل المشكلة الأصلية .
وهكذا تستمر عملية التقسيم حتى تصل المشكلة إلى حجم يمكن معه حلها مباشرة دون اللجوء إلى التقسيم.
___________________________________________
في هذه الوريقات قمت بتوضيح مبدأ Divide and Conquer
والعديد الخوارزميات التي تستخدمه مثل
Quick Sort
Merge Sort
MaxMin Problem
Binary Search
Integer Exponentiation
مع تبيين تعقيد كل خوارزمية