به زبان مادری این سایت خوبه#-o
زبان مادری من یه زبان دیگه ست
مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0
میشه روش حل کردنش رو بگین
مشکل اصلی من محاسبه پیچیدگی بازگشتی هاست
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0
میشه روش حل کردنش رو بگین
t._cormen_-_introduction_to_algorithms_3rd_edition
مشکل اصلی من محاسبه پیچیدگی بازگشتی هاستاین الگوریتم به اصطلاح از گونه ی تقسیم و غلبه ( divide and conquer ) است . برای این الگوریتم ها میانگین مرتبه را از روی فرمول زیر بدست می آوریم :
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0
میشه روش حل کردنش رو بگین
t(n) = at(n/b)+C(n^k) سپس میانگین برابر است با : if a>b^k =>n^log(a,b)
if a=b^k =>(n^k)*log(n)
if a<b^k =>n^kچون در نمونه ای که دادید :a=2 b=2 k=1
a=b^k میانگین مرتبه از رده :(n^k) * log(n)است . که چون k=1 برابر است با nlogn . استادمون این مسئله و حل کرده بود وجوابی شما آوردید اورده بود ولی روش حلش رو نگفته منم که زیادی باهوشم نمیتونستم حلش کنم ولی الان روش حلرو دونستممشکل اصلی من محاسبه پیچیدگی بازگشتی هاستاین الگوریتم به اصطلاح از گونه ی تقسیم و غلبه ( divide and conquer ) است . برای این الگوریتم ها میانگین مرتبه را از روی فرمول زیر بدست می آوریم :
مثلا این:
t(n)=2t(n/2)+n-1
t(1)=0
میشه روش حل کردنش رو بگین
نخست فرمول را به شکل استاندارد زیر میگیریم :کد: [انتخاب]t(n) = at(n/b)+C(n^k)سپس میانگین برابر است با :کد: [انتخاب]if a>b^k =>n^log(a,b)چون در نمونه ای که دادید :
if a=b^k =>(n^k)*log(n)
if a<b^k =>n^kکد: [انتخاب]a=2 b=2 k=1میانگین مرتبه از رده :
a=b^kکد: [انتخاب](n^k) * log(n)است . که چون k=1 برابر است با nlogn .
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)
}
}
حالا من یک الگوریتم مینویسم ( یافتن بزرگترین عدد در یک آرایه ) شما نخست t(n) رو براش بساز سپس بگو میانگین مرتبه اش چیه :میشه روش حلش رو همبگیدکد: [انتخاب]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)
}
}
خودم تو یک کد ساده موندم مثل خر
اونو ردیف کردم میگم
:-X :-X
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)
}
}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حالا شما از روی فرمولها مرتبه میانگین این خوارزمی رو بگو