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

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

منابع

• www.prozhe.com

• ebook.veyq.ir

• www.irandisheh.com

• www.nooreaseman.com

• www.iran-stu.com

• com-eng.ir

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