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

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

غالباً ما يساعد بارادايم فرق تسد في اكتشاف خوارزميات كفئة. كانت فرق تسد المفتاح، على سبيل المثال، لطريقة كاراتسوب للضرب، خوارزميتا الترتيب السريع والتريب الدمجي، خوارزمية ستراسين لضرب المصفوفات، وتحويل فوريي السريع. في كل الأمثلة، أدى نهج فرق تسد إلى تطوير تكلفة الحل. مثلا، إذا كان لحالات الأساس حجم ثابت محدود، تقسيم المسألة ودمج الحلول الجزئية هو نسبي لحجم المسألة n، وهنالك عدد محدود من المسائل الجزئية p بحجم ~ n/p في كل مرحلة، ولذلك تكلفة خوارزمية فرق تسد تكون (O(n log n.

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

تميل خوارزميات فرق تسد بطبيعة الحال إلى الاستفادة المثلى من الذاكرة الخابية.

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