حالتهای بهترین، بدترین و متوسط: تفاوت میان نسخهها
رده:تحلیل الگوریتمها افزوده شد با استفاده از وپ:ردهساز |
جز r2.7.3) (ربات: افزودن bn, de, eo, hr, zh |
||
خط ۵۲: | خط ۵۲: | ||
[[رده:تحلیل الگوریتمها]] |
[[رده:تحلیل الگوریتمها]] |
||
[[bn:ওয়ার্স্ট কেইস পারফরম্যান্স]] |
|||
[[de:Zeitkomplexität]] |
|||
[[en:Best, worst and average case]] |
[[en:Best, worst and average case]] |
||
[[eo:Komputada tempo]] |
|||
[[hr:Vrijeme računanja]] |
|||
[[zh:計算時間]] |
نسخهٔ ۲ ژوئیهٔ ۲۰۱۲، ساعت ۰۰:۴۹
حالتهای بهترین، بدترین و متوسط (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 *