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

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

منابع

www.prozhe.com