أفضل وأسوأ ومتوسط الحالات
في علوم الحاسوب ، تُعبّر أفضل حالات خوارزمية معينة ، وأسوأها ، ومتوسطها، عن استخدام الموارد على الأقل ، والأكثر ، والمتوسط ، على التوالي. عادةً ما يكون المورد المُعتبر هو وقت التشغيل، أي التعقيد الزمني ، ولكن قد يكون أيضًا الذاكرة أو موردًا آخر. أفضل حالة هي الدالة التي تُنفّذ أقل عدد من الخطوات على بيانات إدخال مكونة من n عنصرًا. أسوأ حالة هي الدالة التي تُنفّذ أكبر عدد من الخطوات على بيانات إدخال بحجم n. متوسط الحالة هو الدالة التي تُنفّذ متوسط عدد الخطوات على بيانات إدخال مكونة من n عنصرًا. [ 1 ]
في الحوسبة في الوقت الحقيقي ، غالبًا ما يكون وقت التنفيذ في أسوأ الحالات مصدر قلق خاص لأنه من المهم معرفة مقدار الوقت الذي قد يكون مطلوبًا في أسوأ الحالات لضمان أن الخوارزمية ستنتهي دائمًا في الوقت المحدد.
يُعدّ كلٌّ من متوسط الأداء وأسوأ حالات الأداء من أكثر المقاييس استخدامًا في تحليل الخوارزميات. أما أفضل حالات الأداء ، فأقل شيوعًا ، لكن له استخداماته؛ فعلى سبيل المثال، عند معرفة أفضل حالات الأداء لكل مهمة على حدة، يُمكن استخدامها لتحسين دقة تحليل أسوأ الحالات الإجمالي. ويستخدم علماء الحاسوب تقنيات التحليل الاحتمالي ، ولا سيما القيمة المتوقعة ، لتحديد أوقات التشغيل المتوقعة.
تُستخدم هذه المصطلحات في سياقات أخرى؛ على سبيل المثال، أسوأ وأفضل نتيجة محتملة لوباء، وأسوأ درجة حرارة يتعرض لها عنصر الدائرة الإلكترونية، وما إلى ذلك. عندما تُستخدم مكونات ذات تحمل محدد ، يجب تصميم الأجهزة للعمل بشكل صحيح مع أسوأ مجموعة من التفاوتات والظروف الخارجية.
أفضل أداء ممكن للخوارزمية
يُستخدم مصطلح "أفضل أداء" في علوم الحاسوب لوصف سلوك الخوارزمية في ظل الظروف المثلى. على سبيل المثال، يكون أفضل أداء لعملية بحث خطي بسيط في قائمة ما عندما يكون العنصر المطلوب هو العنصر الأول في القائمة.
نادراً ما يعتمد تطوير الخوارزميات واختيارها على الأداء الأمثل: فمعظم المؤسسات الأكاديمية والتجارية تهتم أكثر بتحسين متوسط التعقيد وأداء أسوأ الحالات . كما يمكن تعديل الخوارزميات بسهولة لتحقيق وقت تشغيل جيد في أفضل الحالات عن طريق تضمين حلول ثابتة لمجموعة محدودة من المدخلات، مما يجعل هذا المقياس عديم الجدوى تقريباً. [ 2 ]
الأداء في أسوأ الحالات مقابل الأداء بعد الاستهلاك مقابل الأداء في الحالة المتوسطة
تتشابه تحليلات الأداء في أسوأ الحالات وتحليلات الأداء في الحالة المتوسطة في بعض الجوانب، ولكنها تتطلب في الممارسة العملية أدوات وأساليب مختلفة.
يُعدّ تحديد معنى المدخلات النموذجية أمرًا صعبًا، وغالبًا ما تتسم هذه المدخلات المتوسطة بخصائص تجعل من الصعب وصفها رياضيًا (على سبيل المثال، الخوارزميات المصممة للعمل على سلاسل نصية). وبالمثل، حتى عندما يكون من الممكن تقديم وصف منطقي لحالة "متوسطة" معينة (والتي قد تنطبق فقط على بعض استخدامات الخوارزمية)، فإنها غالبًا ما تؤدي إلى تحليل أكثر تعقيدًا للمعادلات. [ 3 ]
يقدم تحليل أسوأ الحالات تحليلاً آمناً (لا يتم التقليل من شأن أسوأ الحالات أبداً)، ولكنه قد يكون متشائماً للغاية ، لأنه قد لا يكون هناك مدخلات (واقعية) من شأنها أن تتخذ هذا العدد الكبير من الخطوات.
في بعض الحالات، قد يكون من الضروري استخدام تحليل متشائم لضمان السلامة. مع ذلك، غالبًا ما يكون هذا التحليل متشائمًا للغاية، لذا فإن التحليل الأقرب إلى القيمة الحقيقية، وإن كان متفائلًا (ربما باحتمالية فشل منخفضة معروفة)، يُعدّ نهجًا أكثر عملية. يُعرف أحد المناهج الحديثة في النظرية الأكاديمية لسد الفجوة بين تحليل أسوأ الحالات وتحليل الحالة المتوسطة بالتحليل المُعدَّل .
عند تحليل الخوارزميات التي تستغرق عادةً وقتًا قصيرًا لإكمالها، ولكنها تتطلب دوريًا وقتًا أطول بكثير، يمكن استخدام تحليل الاستهلاك لتحديد أسوأ وقت تشغيل ممكن على مدى سلسلة (قد تكون لانهائية) من العمليات . يمكن أن تكون تكلفة الاستهلاك هذه أقرب بكثير إلى متوسط التكلفة، مع توفير حد أقصى مضمون لوقت التشغيل. على سبيل المثال، غالبًا ما تعتمد الخوارزميات المتصلة بالإنترنت على تحليل الاستهلاك.
يرتبط تحليل أسوأ الحالات بتعقيد أسوأ الحالات . [ 4 ]
العواقب العملية
تتمتع العديد من الخوارزميات ذات الأداء السيئ في أسوأ الحالات بأداء جيد في المتوسط. وهذا أمر إيجابي بالنسبة للمسائل التي نسعى لحلها، إذ يُمكننا أن نأمل أن تكون الحالات المحددة التي تهمنا متوسطة الصعوبة. أما في مجال التشفير ، فهذا أمر سلبي للغاية، فنحن نرغب في أن تكون الحالات النموذجية لمسألة التشفير صعبة. وهنا، يُمكن استخدام أساليب مثل الاختزال الذاتي العشوائي لبعض المسائل المحددة لإثبات أن أسوأ حالة ليست أصعب من الحالة المتوسطة، أو بعبارة أخرى، أن الحالة المتوسطة ليست أسهل من أسوأ حالة.
من ناحية أخرى، فإن بعض هياكل البيانات مثل جداول التجزئة لها سلوكيات سيئة للغاية في أسوأ الحالات، ولكن جدول التجزئة المكتوب جيدًا ذو الحجم الكافي لن يعطي إحصائيًا أسوأ حالة أبدًا؛ يتبع متوسط عدد العمليات التي يتم تنفيذها منحنى اضمحلال أسي، وبالتالي فإن وقت تشغيل العملية محدود إحصائيًا.
أمثلة
خوارزميات الفرز
| الخوارزمية | بنية البيانات | التعقيد الزمني: الأفضل | التعقيد الزمني: متوسط | التعقيد الزمني: الأسوأ | تعقيد المساحة: الأسوأ |
|---|---|---|---|---|---|
| فرز سريع | المصفوفة | O( n log( n )) | O( n log( n )) | O( n 2 ) | على ) |
| فرز الدمج | المصفوفة | O( n log( n )) | O( n log( n )) | O( n log( n )) | على ) |
| فرز الكومة | المصفوفة | O( n log( n )) | O( n log( n )) | O( n log( n )) | O(1) |
| نوع ناعم | المصفوفة | على ) | O( n log( n )) | O( n log( n )) | O(1) |
| فرز الفقاعات | المصفوفة | على ) | O( n 2 ) | O( n 2 ) | O(1) |
| فرز الإدراج | المصفوفة | على ) | O( n 2 ) | O( n 2 ) | O(1) |
| فرز التحديد | المصفوفة | O( n 2 ) | O( n 2 ) | O( n 2 ) | O(1) |
| نوع بوجو | المصفوفة | على ) | O( n n !) | O(∞) | O(1) |
- تُطبَّق خوارزمية فرز الإدراج على قائمة من n عنصرًا، بافتراض أن جميعها مختلفة ومرتبة عشوائيًا في البداية. في المتوسط، نصف عناصر القائمة A1 ... Aj أصغر من العنصر Aj +1 ، والنصف الآخر أكبر منه. لذلك، تقارن الخوارزمية العنصر ( j + 1 ) المراد إدراجه ، في المتوسط، بنصف القائمة الفرعية المرتبة مسبقًا، وبالتالي tj = j / 2. يُعطي حساب زمن التشغيل في الحالة المتوسطة دالة تربيعية لحجم المدخلات، تمامًا كما هو الحال في أسوأ الحالات.
- عند تطبيق خوارزمية الفرز السريع على قائمة مكونة من n عنصرًا، بافتراض أن جميعها مختلفة ومرتبة عشوائيًا في البداية، فإن هذه الخوارزمية الشائعة تتميز بأداء متوسط قدره O( n log( n ))، مما يجعلها خوارزمية سريعة جدًا عمليًا. ولكن عند إدخال بيانات في أسوأ الحالات، يتراجع أداؤها إلى O( n² ). كذلك، عند تطبيقها باستخدام سياسة "الأقصر أولًا"، فإن تعقيد المساحة في أسوأ الحالات يكون محدودًا بـ O(log( n )).
- تستغرق خوارزمية فرز الكومة زمنًا قدره O(n) عندما تكون جميع العناصر متطابقة. أما خوارزمية تحويل الكومة إلى كومة (Heapify) فتستغرق زمنًا قدره O(n)، ثم يستغرق حذف كل عنصر من العناصر n زمنًا قدره O(1). ويزداد زمن التشغيل إلى O(nlog(n)) إذا كان يجب أن تكون جميع العناصر مختلفة.
- تستغرق خوارزمية Bogosort زمنًا قدره O(n) عند فرز العناصر في التكرار الأول. في كل تكرار، يتم التحقق من ترتيب جميع العناصر. يوجد n! تبديلًا ممكنًا؛ باستخدام مولد أرقام عشوائية متوازن، يتم الحصول على كل تبديل تقريبًا للمصفوفة في n! تكرارًا. نظرًا لمحدودية ذاكرة الحواسيب، فإن الأرقام المولدة تتكرر؛ وقد لا يكون من الممكن الوصول إلى كل تبديل. في أسوأ الأحوال، يؤدي هذا إلى زمن قدره O(∞)، أي حلقة لا نهائية.
هياكل البيانات
| بنية البيانات | تعقيد الخطة | تعقيد المساحة | |||||||
|---|---|---|---|---|---|---|---|---|---|
| متوسط: الفهرسة | متوسط: البحث | متوسط: الإدخال | المتوسط: الحذف | الأسوأ: الفهرسة | الأسوأ: البحث | الأسوأ: الإدخال | الأسوأ: الحذف | أسوأ | |
| المصفوفة الأساسية | O(1) | على ) | على ) | على ) | O(1) | على ) | على ) | على ) | على ) |
| مصفوفة ديناميكية | O(1) | على ) | على ) | — | O(1) | على ) | على ) | — | على ) |
| كومة | على ) | على ) | O(1) | O(1) | على ) | على ) | O(1) | O(1) | على ) |
| طابور | على ) | على ) | O(1) | O(1) | على ) | على ) | O(1) | O(1) | على ) |
| قائمة مرتبطة بشكل فردي | على ) | على ) | O(1) | O(1) | على ) | على ) | O(1) | O(1) | على ) |
| قائمة مرتبطة ثنائياً | على ) | على ) | O(1) | O(1) | على ) | على ) | O(1) | O(1) | على ) |
| قائمة التخطي | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) | على ) | على ) | على ) | O( n log ( n )) |
| جدول التجزئة | — | O(1) | O(1) | O(1) | — | على ) | على ) | على ) | على ) |
| شجرة البحث الثنائية | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) | على ) | على ) | على ) | على ) |
| شجرة ديكارتية | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | — | على ) | على ) | على ) | على ) |
| شجرة B | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) |
| شجرة حمراء سوداء | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) |
| شجرة متفرعة | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) |
| شجرة AVL | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) |
| شجرة Kd | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | على ) | على ) | على ) | على ) | على ) |
- البحث الخطي في قائمة مكونة من n عنصرًا. في أسوأ الحالات، يجب على البحث زيارة كل عنصر مرة واحدة. يحدث هذا عندما تكون القيمة المراد البحث عنها إما العنصر الأخير في القائمة، أو غير موجودة فيها. مع ذلك، في المتوسط، بافتراض أن القيمة المراد البحث عنها موجودة في القائمة وأن احتمالية أن تكون القيمة المراد البحث عنها متساوية في كل عنصر من عناصر القائمة، فإن البحث يزور n /2 عنصرًا فقط.
انظر أيضاً
- خوارزمية الفرز - مجال يتم فيه إجراء قدر كبير من تحليل الأداء لمختلف الخوارزميات.
- بنية بيانات البحث – أي بنية بيانات تسمح باسترجاع عناصر محددة بكفاءة
- تحليل الدائرة في أسوأ الحالات
- تحليل مُنعّم
- عنصر الفاصل المحدود
- تدوين كبير
مراجع
- ↑ "أفضل وأسوأ ومتوسط تعقيد الحالات - التعقيد وسهولة المعالجة - دليل علوم الحاسوب الميداني" . www.csfieldguide.org.nz . تاريخ الاسترجاع: 23-10-2025 .
- ↑ مقدمة في الخوارزميات (كورمن، ليسرسون، ريفست، وستين) 2001، الفصل 2 "البدء". في تعقيد الحالة الأفضل ، فإنه يعطي الحد الأدنى لوقت تشغيل الخوارزمية لأي حالات من المدخلات.
- ↑ سبيلمان، دانيال ؛ تينغ، شانغ هوا (2009)، "التحليل المُنعّم: محاولة لشرح سلوك الخوارزميات في الممارسة العملية" (ملف PDF) ، مجلة اتصالات رابطة مكائن الحوسبة ، 52 (10)، ACM: 76-84 ، doi : 10.1145/1562764.1562785 ، S2CID 7904807
- ↑ "تعقيد أسوأ الحالات" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 21-07-2011 . تم الاطلاع عليه بتاريخ 30-11-2008 .
- نظرية التعقيد الحسابي
- تحليل الخوارزميات