حالة سلوك خوارزمية

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

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

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

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

أفضل أداء لحالة الخوارزمية

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

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

أسوأ حالة مقابل أداء الحالة الوسطى

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

يعطي التحليل الأسوأ حالة تحليلاً آمنًا (أسوأ حالة لا يتم التقليل من شأنها أبدًا)، ولكن يمكن أن يكون متشائمًا بشكل مفرط، حيث قد لا يكون هناك مدخلات (واقعية) من شأنها اتخاذ هذه الخطوات العديدة.

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

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

يرتبط تحليل الحالة الأسوأ بتعقيد الحالة الأسوأ.[3]

انظر أيضًا

مراجع

  1. ^ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".In حالة سلوك خوارزمية, it gives the lower bound on the running time of the algorithm of any instances of input.
  2. ^ Spielman، Daniel؛ Teng، Shang-Hua (2009)، "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF)، Communications of the ACM، ACM، ج. 52، ص. 76-84، DOI:10.1145/1562764.1562785، مؤرشف من الأصل (PDF) في 2019-07-28
  3. ^ "Worst-case complexity" (PDF). مؤرشف من الأصل (PDF) في 2011-07-21. اطلع عليه بتاريخ 2008-11-30.