التحليل الاحتمالي للخوارزميات
في تحليل الخوارزميات ، يُعدّ التحليل الاحتمالي للخوارزميات منهجًا لتقدير التعقيد الحسابي لخوارزمية أو مسألة حسابية. ينطلق هذا المنهج من افتراض حول توزيع احتمالي على مجموعة جميع المدخلات الممكنة. يُستخدم هذا الافتراض بعد ذلك لتصميم خوارزمية فعّالة أو لاستنتاج تعقيد خوارزمية معروفة. يختلف هذا المنهج عن منهج الخوارزميات الاحتمالية ، ولكن يمكن الجمع بينهما.
بالنسبة للخوارزميات غير الاحتمالية، وتحديدًا الحتمية ، فإن أكثر أنواع تقديرات التعقيد الاحتمالي شيوعًا هي تعقيد الحالة المتوسطة وتعقيد شبه المؤكد. للحصول على تعقيد الحالة المتوسطة، يُقيّم الوقت المتوقع للخوارزمية عند إعطاء توزيع مُدخلات، بينما في تقدير تعقيد شبه المؤكد، يُقيّم ما إذا كانت الخوارزمية تقبل تقدير تعقيد مُعطى يتحقق بشكل شبه مؤكد .
في التحليل الاحتمالي للخوارزميات الاحتمالية (العشوائية)، يتم أيضًا أخذ توزيعات أو متوسط جميع الخيارات الممكنة في الخطوات العشوائية في الاعتبار، بالإضافة إلى توزيعات المدخلات.
انظر أيضاً
مراجع
- فريز، آلان م.؛ ريد، بروس (1998)، "التحليل الاحتمالي للخوارزميات"، في حبيب، ميشيل؛ ماكديارميد، كولين؛ راميريز-ألفونسين، خورخي؛ ريد، بروس (محررون)، الأساليب الاحتمالية للرياضيات المنفصلة الخوارزمية ، الخوارزميات والتوافقية، المجلد 16، سبرينغر، الصفحات 36-92 ، doi : 10.1007/978-3-662-12788-9_2 ، ISBN 9783662127889
- هوفري، ميخا (1987)، التحليل الاحتمالي للخوارزميات: حول منهجيات الحوسبة لتقييم أداء خوارزميات الحاسوب ، سبرينغر، doi : 10.1007/978-1-4612-4800-2 ، ISBN 9781461248002
- فريز، أ.م. (1990)، "التحليل الاحتمالي لخوارزميات الرسوم البيانية"، في تينهوفر، ج.؛ ماير، إ.؛ نولتماير، هـ.؛ سيسلو، م.م. (محررون)، نظرية الرسوم البيانية الحاسوبية ، ملحق الحوسبة، المجلد 7، سبرينغر، الصفحات 209-233 ، doi : 10.1007/978-3-7091-9076-0_11 ، ISBN 9783709190760
- تحليل الخوارزميات
- نماذج أولية للخوارزميات وهياكل البيانات