الفرق بين الخوارزمية العشوائية والتكرار

Anonim

العشوائية مقابل خوارزمية العودية

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

ما هي الخوارزمية العشوائية؟

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

ما هي خوارزمية العودية؟

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

ما هو الفرق بين الخوارزمية العشوائية والخوارزمية؟

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