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

ابرابزار
جز (ماني صفحهٔ تحلیل حالت متوسط الگوریتم را به حالت‌های بهترین، بدترین و متوسط منتقل کرد: Best, worst and average case)
(ابرابزار)
حالت‌های بهترین، بدترین و متوسط (Best, worst and average case) از روش‌های تحلیل الگوریتم است.
{{حذف زمان‌دار/پیغام
|اهمیت= بی‌منبع، میان‌ویکی وارد نشده، احتمال آنکه پیشتر ساخته شده باشد وجود دارد
|timestamp = 20120630140608
}}
 
== حالت متوسط ==
 
تحلیل حالت متوسط یک الگوریتم دارای اهمیت بیشتری نسبت به بدترین حالت و بهترین حالت الگوریتم می باشدمی‌باشد.
اگر تعداد تکرار یک دستور العمل در یک الگوریتم با n ورودی را در حالت متوسط با (A(n نشان دهیم آنگاه یک رابطه ساده جهت به دست آوردن حالت متوسط به صورت زیر می باشد می‌باشد:
{{چپچین}}
P(i).F(i) مجموع = A(n)
 
{{پایان چپ‌چین}}
که در آن s مجموعه حالات ممکنه و (P(i احتمال رخ دادن حالت i ام و (F(i تعداد تکرار دستور مورد نظر در حالت i ام می باشدمی‌باشد.
 
مثال : فرض کنید یک آرایه مرتب (صعودی) و کلیدx داده شده باشند . متوسط زمان اجرای الگوریتم جستجوی دودویی Binary Search را محاسبه کنید.
 
<source lang="cpp">
 
Function BinarySearch( A, n, x)
<source lang=cpp>
low ←1
Function BinarySearch( A, n, x)
high←n
low ←1
while low≤high do
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.
</source>
 
در این الگوریتم اگر x داخل آرایه موجود باشد تعدادی مقایسه با عناصر آرایه صورت می گیردمی‌گیرد و نهایتا جستجو موفق خواهد بود و اگر x داخل آرایه موجود نباشد تعدادی مقایسه با عناصر آرایه صورت می گیردمی‌گیرد و نهایتا جستجو ناموفق خواهد بود .مقایسه هامقایسه‌ها به صورت جستجو در یک درخت جستجوی دودویی انجام می شوندمی‌شوند.
 
== منابع ==
{{چپچین}}
 
{{پایان چپ‌چین}}
[[en:Best, worst and average case]]
۱۶۰٬۳۷۶

ویرایش