حالت‌های بهترین، بدترین و متوسط

در علوم کامپیوتر حالت‌های بهترین، بدترین و متوسط (به انگلیسی: Best, worst and average case) برای اجرای الگوریتم عبارت است از اینکه الگوریتم مورد نظر ما در چه حدی از منابع استفاده می‌کند. معمولا منبعی که در نظر گرفته می‌شوند زمان اجرا است. ولی میتواند حافظه یا منابع دیگری در نظر گرفته شود.

آیا الگوریتم مورد نظر حداقل استفاده را از حافظه می‌کند یا حداکثر؛ یا متوسط؛ که در ضمن این حافظه می‌تواند یک حافظه جانبی یا حافظه داخلی باشد؟

در تجزیه و تحلیل پیچیدگی زمانی الگوریتم‌ها حالت متوسط و بدترین حالت اجرای یک الگوریتم بیشتر استفاده می‌شوند.

در مبحث رایانش بی‌درنگ، بدترین زمان اجرای الگوریتم حالتی است که به ما این تضمین را می‌دهد که الگوریتم ما همیشه به جواب خواهد رسید.

این عبارات (بهترین، بدترین و حالت متوسط) در مباحث و علوم دیگر هم کاربرد دارند. برای نمونه: بدترین دما برای این که یک قطعه الکترونیکی بسوزد یا بهترین زمان برای اینکه یک بیماری بهبود یابد تا به اوج خود نرسد و غیره.

مقدمه

حالت‌های بهترین، بدترین و متوسط از روش‌های تجزیه و تحلیل پیچیدگی زمانی الگوریتم‌ها است. زمانی که می‌خواهیم پیچیدگی زمانی یک الگوریتم را محاسبه کنیم آن را در بدترین حالت و بهترین حالت و حالت متوسط بررسی می‌کنیم.

که معمولاً بدترین حالات را در نظر می‌گیریم؛ تا یک تضمینی برای جواب دادن الگوریتم مورد نظر داشته باشیم.

بهترین حالت زمانی برای یک الگوریتم

عبارت بهترین حالت زمانی در علوم کامپیوتر برای شرح دادن الگوریتمی به کار می‌رود که تحت شرایط آرمانی عمل می‌کند. برای نمونه، بهترین حالت زمانی برای به انجام رسیدن یک الگوریتم جستجوی خطی در یک لیستی از اعداد زمانی است که دادهٔ موردنظر ما در خانهٔ اول لیست قرار گرفته باشد.

برای انتخاب یک الگوریتم یا گسترش دادن یک الگوریتم به ندرت از بهترین حالت استفاده می‌کنند: بیشتر افراد ترجیح می‌دهند که روی بدترین حالت یا حالت متوسط یک الگوریتم کار کنند یا استفاده کنند.

بهترین حالت زمانی معمولاً برای داده‌های محدود و خاصی در نظر گرفته می‌شود

حالت متوسط

تحلیل حالت متوسط یک الگوریتم دارای اهمیت بیشتری نسبت به بدترین حالت و بهترین حالت الگوریتم می‌باشد. اگر تعداد تکرار یک دستور العمل در یک الگوریتم با n ورودی را در حالت متوسط با (A(n نشان دهیم آنگاه یک رابطه ساده جهت به دست آوردن حالت متوسط به صورت زیر می‌باشد:

P(i).F(i) مجموع = A(n)

که در آن s مجموعه حالات ممکنه و (P(i احتمال رخ دادن حالت i ام و (F(i تعداد تکرار دستور مورد نظر در حالت i ام می‌باشد.

مثال: فرض کنید یک آرایه مرتب (صعودی) و کلیدx داده شده باشند. متوسط زمان اجرای الگوریتم جستجوی دودویی Binary Search را محاسبه کنید.

Function BinarySearch(A, n, x)
low ←1
high←n
while low≤high do
mid←(low+high)/2
if x=A(mid) then
return mid
elsif x>A(mid) then
low←mid+1
else
high←mid-1
endif
repeat
return 0
end.

در این الگوریتم اگر x داخل آرایه موجود باشد تعدادی مقایسه با عناصر آرایه صورت می‌گیرد و نهایتاً جستجو موفق خواهد بود و اگر x داخل آرایه موجود نباشد تعدادی مقایسه با عناصر آرایه صورت می‌گیرد و نهایتاً جستجو ناموفق خواهد بود. مقایسه‌ها به صورت جستجو در یک درخت جستجوی دودویی انجام می‌شوند.

بدترین حالت در مقابل حالت متوسط

عملکرد بدترین حالت زمانی و حالت متوسط تقریباً شبیه به همدیگر هستند؛ ولی در عمل، قانون و روش هر کدام متفاوت از دیگری است.

نمونه

برای نمونه اگر بخواهیم پیچیدگی زمانی جستجوی ترتیبی را در حالت بهترین، بدترین و متوسط بررسی کنیم به صورت زیر داریم:

  int i=۰;
  for(i=0;i<=n;i++)
  {
     if(a[i] == x)
     {
        cout<<"find!";
        return 1;
    }
     else if(a[i]!= x)
     contiue;
 }
  cout<<"Not Found!";
  return 0;

در بهترین حالت: وقتی داده مورد نظر (x) را می‌خواهیم جستجو کنیم در ابتدای آرایه وجود دارد. پیچیدگی زمانی آن برابر $O(1)$ می‌شود.

در حالت متوسط: وقتی داده مورد نظر (x) را می‌خواهیم جستجو کنیم در وسط آرایه وجود دارد. پیچیدگی زمانی آن برابر $O(n/2)$ می‌شود.

در بدترین حالت: وقتی داده مورد نظر (x) را می‌خواهیم جستجو کنیم در انتهای آرایه وجود دارد. پیچیدگی زمانی آن برابر $O(n)$ می‌شود.

جستارهای وابسته

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Best, worst and average case». در دانشنامهٔ ویکی‌پدیای انگلیسی.
ebook.veyq.ir
www.irandisheh.com