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

در علوم کامپیوتر حالت‌های بهترین، بدترین و متوسط (به انگلیسی: 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 داخل آرایه موجود نباشد تعدادی مقایسه با عناصر آرایه صورت می‌گیرد و نهایتا جستجو ناموفق خواهد بود. مقایسه‌ها به صورت جستجو در یک درخت جستجوی دودویی انجام می‌شوند.

نمونه

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

<source lang="c">

 int i=0;
 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;

<source lang="c">

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

در بدترین حالت : وقتی داده مورد نظر را که می خواهیم جستجو کنیم در ابتدای آرایه وجود دارد . به این حالت بهترین حالت گفته می شود که پیچیدگی زمانی آن برابر 1 می شود.

در بهترین حالت : وقتی داده مورد نظر را که می خواهیم جستجو کنیم در ابتدای آرایه وجود دارد . به این حالت بهترین حالت گفته می شود که پیچیدگی زمانی آن برابر 1 می شود.

منابع

• www.prozhe.com

• ebook.veyq.ir

• www.irandisheh.com

• www.nooreaseman.com

• www.iran-stu.com

• com-eng.ir

• مشارکت‌کنندگان ویکی‌پدیا. «Best, worst and average case». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئیه ۲۰۰۸.