function find_max ( T , low , high)
{
if (low==high)
return T[low]
else
if (high == low+1)
if (T[high] > T [low])
return T[high]
else
return T[low]
else
{
mid=floor((high+low)/2)
LMAX=find_max(T,low,mid)
RMAX=find_max(T,mid+1,high)
return MAXIMUM(LMAX,RMAX)
}
}
اینجوری برهان میاریم :
نخست می بینیم الگوریتم چکار میکنه . الگوریتم میاد برای یافتن بزرگترین عدد در یک آرایه نخست نگاه میکنه ببینه آیا آرایه تک عنصر داره یا بیش از یک عنصر . اگر تک عنصر داره میاد همون تک عنصر رو به نشانه ی بزرگترین عنصر برمیگردونه
پس از اینجا در می یابیم که بهترین حالت برای این الگوریتم با یک if ساده انجام میشه . پس مرتبه این الگوریتم در بهترین حالت میشه 1 .
در حالت میانگین الگوریتم میاد آرایه رو به دو بخش میکنه
floor((high+low)/2سپس توی هر بخش بیشینه رو میابه :LMAX=find_max(T,low,mid)
RMAX=find_max(T,mid+1,high
یعنی داریم :t(n) = 2t(n/2)n/2 یعنی الگوریتم روی نیمی از درآیند ( وردوی ) کار میکنه . چون دو بار روی نیمی از ورودی کار کردیم میشه
2t(n/2)در پایان میایم بیشینه رو میان بیشینه ی چپ و بیشینه ی راست میابیم :
return MAXIMUM(LMAX,RMAX)اینم میشه یک کار .
پس زمان مصرفی برابره با
t(n) = 2 t(n/2)+1حالا شما از روی فرمولها مرتبه میانگین این خوارزمی رو بگو
موضوع: کمک برای یادگیری طراحی الگوریتم (دفعات بازدید: 7774 بار)
