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