حالتهای بهترین، بدترین و متوسط: تفاوت میان نسخهها
در خواست برای حذف زماندار. (توینکل) |
طیبه سلطانی (بحث | مشارکتها) |
||
خط ۳۸: | خط ۳۸: | ||
{{چپچین}} |
{{چپچین}} |
||
www.prozhe.com |
www.prozhe.com * |
||
{{پایان چپچین}} |
{{پایان چپچین}} |
نسخهٔ ۳۰ ژوئن ۲۰۱۲، ساعت ۱۴:۲۴
این مقاله به دلیل زیر نامزد حذف زماندار شدهاست:
اگر میتوانید مشکل این مقاله را با ویرایش، نگارش، منبعدهی، تغییر نام یا ادغام حل کنید، لطفاً این صفحه را ویرایش کنید و مقاله را در حد استانداردهای ویکیپدیا بهبود دهید. در صورتی که مقاله را بهبود بخشیدید، میتوانید این برچسب را بردارید. اما اگر خودتان سازندهٔ این مقاله هستید، لطفاً خودتان این برچسب را از مقاله برندارید و از فرد دیگر یا نامزدکننده درخواست نمائید تا برچسب را بردارد. کاربر نامزدکننده:در صورتی که این الگو حذف شد، نباید دوباره قرار داده شود و در صورت پابرجا بودن مشکلات، این مقاله برای حذف سریع یا نظرخواهی برای حذف کاندید خواهد شد. اگر این پیغام تا ده روز در این مکان باقی بماند ممکن است مقاله حذف شود. لطفاً با قرار دادن این الگو در صفحه بحث نویسنده، وی را آگاه سازید: برچسب زمان: 20120630140608 مدیران: حذف |
تحلیل حالت متوسط یک الگوریتم دارای اهمیت بیشتری نسبت به بدترین حالت و بهترین حالت الگوریتم می باشد.
اگر تعداد تکرار یک دستور العمل در یک الگوریتم با 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 *