خوارزمية فرق تسد

في علم الحاسوب، خوارزمية فرق تسد (بالإنجليزية: divide and conquer)‏ هي بارادايم تصميم خوارزميات مهم مبني على استدعاء ذاتي متعدد الفروع. تعمل خوارزمية فرق تسد عن طريق تقسيم المسألة بشكل عودي إلى مسألتين جزئيتين أو أكثر من نفس النوع، حتى تصبح المسائل الجزئية بسيطة بما فيه الكفاية لتحل بشكل مباشر. ومن ثم تدمج حلول المسائل الجزئية لتعطي حلاً للمسألة الجزئية. هذا الأسلوب هو الأساس للعديد من الخوارزميات الكفئة لجميع الأنواع من المسائل، مثل الترتيب (على سبيل المثلا ترتيب دمجي، ترتيب سريع)، البحث (خوارزمية بحث ثنائي)، ، تحليل نحوي، حساب تحويل فوريي المنقطع، والمضروب. من ناحية أخرى، القدرة على فهم وتصميم خوارزميات فرق تسد هي مهارة تستغرق وقتا لإتقانها. كما هو الحال في برهنة مبرهنة بالاستقراء، من الضروري في كثير من الأحيان استبدال المسألة الأصلية بمسألة عامة أكثر أو مسألة معقدة من أجل جعل الاستدعاء الذاتي يعمل، وليس هنالك طريقة منهجية للحصول على التعميم الملائم. عادة ما يتم برهنة صحة خوارزمية فرق تسد بالاستقراء الرياضي، ويتم تحديد كلفتها الحسابية غالبا عن طريق حل .