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

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

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

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

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

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

تحلیل حالت متوسط یک الگوریتم دارای اهمیت بیشتری نسبت به بدترین حالت و بهترین حالت الگوریتم می‌باشد. اگر تعداد تکرار یک دستور العمل در یک الگوریتم با n ورودی را در حالت متوسط با (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) را می‌خواهیم جستجو کنیم در ابتدای آرایه وجود دارد. پیچیدگی زمانی آن برابر ${\displaystyle O(1)}$

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

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

• الگوریتم مرتب‌سازی
• الگوریتم جستجو
• پیچیدگی زمانی
• نظریه پیچیدگی محاسباتی

• ebook.veyq.ir
• www.irandisheh.com