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

تُعدّ استراتيجية "فرق تسد" أداةً فعّالةً لحلّ المشكلات المعقدة من الناحية المفاهيمية: فكل ما تتطلبه هو طريقة لتقسيم المشكلة إلى مشكلات فرعية، وحلّ الحالات البسيطة، ودمج المشكلات الفرعية في المشكلة الأصلية. وبالمثل، لا تتطلب استراتيجية "التقليل والتغلب" سوى اختزال المشكلة إلى مشكلة واحدة أصغر، مثل لغز برج هانوي الكلاسيكي ، الذي يُختزل فيه تحريك برج ارتفاعه${\displaystyle n}$لتحريك برج شاهق الارتفاع${\displaystyle n-1}$.

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

في جميع هذه الأمثلة، أدى أسلوب D&C إلى تحسين التكلفة التقاربية للحل. على سبيل المثال، إذا كانت (أ) الحالات الأساسية ذات حجم ثابت ومحدود، فإن جهد تقسيم المسألة ودمج الحلول الجزئية يتناسب طرديًا مع حجم المسألة.${\displaystyle n}$و(ب) يوجد عدد محدود${\displaystyle p}$من المشكلات الفرعية ذات الحجم ~${\displaystyle {\frac {n}{p}}}$في كل مرحلة، ستكون تكلفة خوارزمية فرق تسد${\displaystyle O(n\log _{p}n)}$.

بالنسبة لأنواع أخرى من أساليب فرق تسد، يمكن تعميم أوقات التشغيل أيضًا. على سبيل المثال، عندما يستغرق (أ) عمل تقسيم المشكلة ودمج الحلول الجزئية${\displaystyle cn}$الوقت، أين${\displaystyle n}$حجم الإدخال و${\displaystyle c}$أ) ثابت ما؛ ب) عندما${\displaystyle n<2}$، يستغرق تنفيذ الخوارزمية وقتًا محدودًا بـ${\displaystyle c}$ج) هناك${\displaystyle q}$مسائل فرعية حيث يكون حجم كل مسألة فرعية ~${\displaystyle {\frac {n}{2}}}$ثم، تكون أوقات التشغيل كما يلي:

• إذا كان عدد المسائل الفرعية${\displaystyle q>2}$إذاً، فإن وقت تشغيل خوارزمية فرق تسد يكون محدوداً بـ${\displaystyle O(n^{\log _{2}q})}$.
• إذا كان عدد المسائل الفرعية واحدًا بالضبط، فإن وقت تشغيل خوارزمية فرق تسد يكون محدودًا بـ${\displaystyle O(n)}$[ ^{10 ]​}

أما إذا استغرق الأمر بدلاً من ذلك عملية تقسيم المشكلة ودمج الحلول الجزئية${\displaystyle cn^{2}}$الوقت، وهناك مشكلتان فرعيتان لكل منهما حجم${\displaystyle {\frac {n}{2}}}$إذاً، فإن وقت تشغيل خوارزمية فرق تسد يكون محدوداً بـ${\displaystyle O(n^{2})}$[ ^{10 ]​}

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

تميل خوارزميات فرق تسد بطبيعتها إلى الاستخدام الأمثل لذاكرة التخزين المؤقت . والسبب هو أنه بمجرد أن تصبح المسألة الفرعية صغيرة بما يكفي، يمكن، من حيث المبدأ، حلها وجميع مسائلها الفرعية داخل ذاكرة التخزين المؤقت ، دون الحاجة إلى الوصول إلى الذاكرة الرئيسية الأبطأ . تُسمى الخوارزمية المصممة لاستغلال ذاكرة التخزين المؤقت بهذه الطريقة " خوارزمية غير معتمدة على ذاكرة التخزين المؤقت" ، لأنها لا تتضمن حجم ذاكرة التخزين المؤقت كمعامل صريح . [ ^{11 ] علاوة} على ذلك، يمكن تصميم خوارزميات فرق تسد للخوارزميات المهمة (مثل الفرز، وتحويل فورييه السريع، وضرب المصفوفات) لتكون خوارزميات مثالية غير معتمدة على ذاكرة التخزين المؤقت - فهي تستخدم ذاكرة التخزين المؤقت بطريقة مثالية على الأرجح، بمعنى تقاربي، بغض النظر عن حجم ذاكرة التخزين المؤقت. في المقابل، فإن النهج التقليدي لاستغلال ذاكرة التخزين المؤقت هو الحجب ، كما هو الحال في تحسين تداخل الحلقات ، حيث يتم تقسيم المسألة صراحةً إلى أجزاء ذات حجم مناسب - وهذا أيضًا يمكن أن يستخدم ذاكرة التخزين المؤقت على النحو الأمثل، ولكن فقط عندما يتم ضبط الخوارزمية لأحجام ذاكرة التخزين المؤقت المحددة لجهاز معين.

توجد نفس الميزة فيما يتعلق بأنظمة التخزين الهرمية الأخرى، مثل NUMA أو الذاكرة الافتراضية ، وكذلك بالنسبة لمستويات متعددة من ذاكرة التخزين المؤقت: بمجرد أن تصبح المشكلة الفرعية صغيرة بما يكفي، يمكن حلها ضمن مستوى معين من التسلسل الهرمي، دون الوصول إلى المستويات الأعلى (الأبطأ).

في العمليات الحسابية التي تتضمن تقريبًا، كالأعداد العشرية ، قد تُعطي خوارزمية فرق تسد نتائج أكثر دقة من طريقة تكرارية تبدو مكافئة لها ظاهريًا. على سبيل المثال، يمكن جمع N عددًا إما بحلقة بسيطة تُضيف كل قيمة إلى متغير واحد، أو بخوارزمية فرق تسد تُسمى الجمع الثنائي ، والتي تُقسّم مجموعة البيانات إلى نصفين، وتحسب مجموع كل نصف بشكل تكراري، ثم تجمع المجموعين. مع أن الطريقة الثانية تُجري نفس عدد عمليات الجمع التي تُجريها الأولى وتتحمل عبء الاستدعاءات التكرارية، إلا أنها عادةً ما تكون أكثر دقة. ^{[ 12 ]}

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

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

في التطبيقات التكرارية لخوارزميات البحث والإنشاء، يجب التأكد من وجود ذاكرة كافية مخصصة لمكدس التكرار، وإلا فقد يفشل التنفيذ بسبب تجاوز سعة المكدس . تتميز خوارزميات البحث والإنشاء الموفرة للوقت عادةً بعمق تكرار صغير نسبيًا. على سبيل المثال، يمكن تنفيذ خوارزمية الفرز السريع بحيث لا تتطلب أبدًا أكثر من${\displaystyle \log _{2}n}$استدعاءات متكررة متداخلة للفرز${\displaystyle n}$أغراض.

Stack overflow can be difficult to prevent when using recursive procedures, since many compilers treat the recursion stack as a contiguous block of memory, and some reserve a fixed amount of space for it. In addition, compilers may store more information on the recursion stack than is strictly required, including the return address, unchanged parameters, and the procedure’s local variables. As a result, the likelihood of stack overflow may be reduced by limiting the number of parameters and local variables in the recursive procedure, or by replacing recursion with an explicit stack data structure.

In any recursive algorithm, there is considerable freedom in the choice of the base cases, the small subproblems that are solved directly in order to terminate the recursion.

Choosing the smallest or simplest possible base cases is more elegant and usually leads to simpler programs, because there are fewer cases to consider and they are easier to solve. For example, a Fast Fourier Transform algorithm could stop the recursion when the input is a single sample, and the quicksort list-sorting algorithm could stop when the input is the empty list; in both examples, there is only one base case to consider, and it requires no processing.

On the other hand, efficiency often improves if the recursion is stopped at relatively large base cases, and these are solved non-recursively, resulting in a hybrid algorithm. This strategy avoids the overhead of recursive calls that do little or no work and may also allow the use of specialized non-recursive algorithms that, for those base cases, are more efficient than explicit recursion. A general procedure for a simple hybrid recursive algorithm is short-circuiting the base case, also known as arm's-length recursion. In this case, whether the next step will result in the base case is checked before the function call, avoiding an unnecessary function call. For example, in a tree, rather than recursing to a child node and then checking whether it is null, checking null before recursing avoids half the function calls in some algorithms on binary trees. Since a D&C algorithm eventually reduces each problem or sub-problem instance to a large number of base instances, these often dominate the overall cost of the algorithm, especially when the splitting/joining overhead is low. Note that these considerations do not depend on whether recursion is implemented by the compiler or by an explicit stack.

Thus, for example, many library implementations of quicksort will switch to a simple loop-based insertion sort (or similar) algorithm once the number of items to be sorted is sufficiently small. Note that, if the empty list were the only base case, sorting a list with ${\displaystyle n}$ entries would entail maximally ${\displaystyle n}$استدعاءات خوارزمية الفرز السريع التي لا تفعل شيئًا سوى العودة فورًا. زيادة الحالات الأساسية إلى قوائم بحجم 2 أو أقل ستؤدي إلى التخلص من معظم هذه الاستدعاءات عديمة الفائدة، وبشكل عام، تُستخدم حالة أساسية أكبر من 2 عادةً لتقليل الوقت المُستغرق في تكلفة استدعاء الدوال أو معالجة المكدس.

بدلاً من ذلك، يمكن استخدام حالات أساسية كبيرة تستخدم خوارزمية فرق تسد، ولكن تُنفذ الخوارزمية لمجموعة محددة مسبقًا من الأحجام الثابتة، حيث يمكن فك الخوارزمية بالكامل إلى كود خالٍ من التكرار والحلقات والشروط (مرتبط بتقنية التقييم الجزئي ). على سبيل المثال، يُستخدم هذا النهج في بعض تطبيقات تحويل فورييه السريع (FFT) الفعالة، حيث تكون الحالات الأساسية عبارة عن تطبيقات مفككة لخوارزميات FFT التي تعتمد على فرق تسد لمجموعة من الأحجام الثابتة. ^{[ 13 ]} يمكن استخدام طرق توليد الكود المصدري لإنتاج العدد الكبير من الحالات الأساسية المنفصلة اللازمة لتنفيذ هذه الاستراتيجية بكفاءة. ^{[ 13 ]}

يُعرف الشكل المعمم لهذه الفكرة باسم "فك التكرار" أو "التوسيع"، وقد تم اقتراح تقنيات متنوعة لأتمتة عملية توسيع الحالة الأساسية. ^{[ 14 ]}

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