خوارزميات - افضل واسوأ سيناريو

خوارزمية افضل واسوأ سيناريو

أسوأ تحليل سيناريو (يتم عادة)

في تحليل أسوأ الحالات ، نحسب الحد الأعلى لوقت تشغيل الخوارزمية. يجب أن نعرف الحالة التي تؤدي إلى تنفيذ أقصى عدد من العمليات. بالنسبة للبحث الخطي ، تحدث أسوأ حالة عندما لا يكون العنصر المراد البحث عنه (x في الكود أعلاه) موجودًا في المصفوفة. عندما لا يكون x موجودًا ، تقارنه دالة search () بجميع عناصر arr [] واحدًا تلو الآخر. لذلك ، فإن التعقيد الزمني الأسوأ للبحث الخطي سيكون Θ (n).

متوسط ​​تحليل سيناريو (يتم أحيانًا)

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

أفضل تحليل سيناريو (زائف)

في أفضل تحليل للحالة ، نحسب الحد الأدنى في وقت تشغيل الخوارزمية. يجب أن نعرف الحالة التي تؤدي إلى تنفيذ حد أدنى من العمليات. في مشكلة البحث الخطي ، تحدث أفضل حالة عندما يكون x موجودًا في الموقع الأول. عدد العمليات في أفضل الحالات ثابت (لا يعتمد على n). لذا فإن التعقيد الزمني في أفضل الأحوال سيكون Θ (1)

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

اشترك فى القائمة البريدية

عن الكاتب

شارك على وسائل التواصل

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

ثلاثة × 2 =