خوارزمية فرق تسد المعنى: شرح بأمثلة

ما هي خوارزميات فرق تسد؟ (ولا ، إنها ليست "فرق واتفق")

يُعد Divide and Conquer نموذجًا خوارزميًا (يُطلق عليه أحيانًا خطأ "Divide and Concur" - وهو اسم مضحك ومناسب) ، وهو مشابه للبرمجة الجشعة والديناميكية. تحل خوارزمية "فرق تسد" النموذجية مشكلة باستخدام الخطوات الثلاث التالية.

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

تسمح لنا هذه الطريقة عادةً بتقليل التعقيد الزمني إلى حد كبير.

على سبيل المثال ، يستخدم Bubble Sort تعقيدًا O(n^2)، بينما يقلل التصنيف السريع (تطبيق Divide And Conquer) من تعقيد الوقت إلى O(nlog(n)). البحث الخطي لديه تعقيد زمني O(n)، بينما البحث الثنائي (تطبيق تقسيم وقهر) يقلل من التعقيد الزمني إلى O(log(n)).

فيما يلي بعض الخوارزميات القياسية من مجموعة خوارزميات فرق تسد.

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

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

دمج الفرز  هو أيضًا خوارزمية فرز. تقسم الخوارزمية المصفوفة إلى نصفين ، ثم تقوم بفرزها بشكل متكرر ، ثم تقوم أخيرًا بدمج النصفين المصنفين. التعقيد الزمني لهذه الخوارزمية O(nLogn)، سواء كان ذلك في أفضل الحالات ، أو متوسط ​​الحالة ، أو أسوأ حالة. لقد حان الوقت التعقيد يمكن فهمها بسهولة من يساوي تكرار ل: T(n) = 2T(n/2) + n.

أقرب زوج من النقاط  تكمن المشكلة في إيجاد أقرب زوج من النقاط في مجموعة من النقاط في المستوى xy. يمكن حل المشكلة في O(n^2)الوقت المناسب عن طريق حساب مسافات كل زوج من النقاط ومقارنة المسافات لإيجاد الحد الأدنى. تحل خوارزمية فرق تسد المشكلة في O(nLogn)الوقت المناسب.

خوارزمية Strassen  هي خوارزمية فعالة لمضاعفة مصفوفتين. طريقة بسيطة لضرب مصفوفتين تحتاج إلى 3 حلقات متداخلة وهي O(n^3). خوارزمية Strassen تضاعف مصفوفتين في O(n^2.8974)الوقت المناسب.

 تعد خوارزمية Cooley-Tukey Fast Fourier Transform (FFT) هي الخوارزمية الأكثر شيوعًا لـ FFT. إنها خوارزمية فرق تسد والتي تعمل في O(nlogn)الوقت المناسب.

كانت خوارزمية كاراتسوبا  أول خوارزمية الضرب أسرع بشكل مقارب من خوارزمية "المدرسة الابتدائية" التربيعية. إنه يقلل من مضاعفة رقمين من رقمين n على الأكثر إلى n ^ 1.585 (وهو تقريب لوغاريتم 3 في الأساس 2) منتجات من رقم واحد. لذلك فهي أسرع من الخوارزمية الكلاسيكية ، التي تتطلب n ^ 2 منتجات أحادية الرقم.

فرق تسد (D & C) مقابل البرمجة الديناميكية (DP)

كلا النموذجين (D & C و DP) يقسم المشكلة المحددة إلى مشكلات فرعية ويحل المشكلات الفرعية. كيف تختار واحد منهم لمشكلة معينة؟ يجب استخدام فرق تسد عندما لا يتم تقييم نفس المشاكل الفرعية عدة مرات. وإلا يجب استخدام البرمجة الديناميكية أو Memoization.

على سبيل المثال ، يعتبر Binary Search خوارزمية Divide and Conquer ، ولا نقوم أبدًا بتقييم المشكلات الفرعية نفسها مرة أخرى. من ناحية أخرى ، لحساب رقم فيبوناتشي التاسع ، يجب تفضيل البرمجة الديناميكية.