سلام
من از تابع بازگشتی های زیر مشکل دارم ممنون میشم هر کسی که بلده واسم توضیح بده.
t(n)=3t(n/3+5)+n/2
t(n)=t(n-1)+2lgn
سلام. سوال اول چون مقدار n بزرگ فرض میشه و دنباله هم لگاریتمیه، میتونید بنویسید t(n)=3t(n/3)+n/2. مشکلی پیش نمیاد. بجای (t(n/ 3^1000 باید بنویسیم (t(n/ 3^1000+7.5. جوابشم از روی درخت بازگشت و یا روش های دیگه بدست میاد. میشه n/2+3*n/6+9*n/27+... که میشه از مرتبه nlgn.
سوال دوم رو میشه اینجوری نوشت:
t(n)=t(n-1)+2lgn
(t(n-1)=2t(n-2)+2lg(n-1
...
t(2)=2t(1)+2lg1
نتیجه میگیریم:
t(n)=2lgn+2lg(n-1)+2lg(n-2)+...+2lg2
میدونیم lgn=lg(n/2)+1 و n تا جمله داریم. پس از مرتبه nlgn میشه.
(۰۵ مرداد ۱۳۹۱ ۰۳:۳۶ ق.ظ)Jooybari نوشته شده توسط: سلام. سوال اول چون مقدار n بزرگ فرض میشه و دنباله هم لگاریتمیه، میتونید بنویسید t(n)=3t(n/3)+n/2. مشکلی پیش نمیاد. بجای (t(n/ 3^1000 باید بنویسیم (t(n/ 3^1000+7.5. جوابشم از روی درخت بازگشت و یا روش های دیگه بدست میاد. میشه n/2+3*n/6+9*n/27+... که میشه از مرتبه nlgn.اگه اولی از مستر حل بشه میشه
سوال دوم رو میشه اینجوری نوشت:
t(n)=t(n-1)+2lgn
(t(n-1)=2t(n-2)+2lg(n-1
...
t(2)=2t(1)+2lg1
نتیجه میگیریم:
t(n)=2lgn+2lg(n-1)+2lg(n-2)+...+2lg2
میدونیم lgn=lg(n/2)+1 و n تا جمله داریم. پس از مرتبه nlgn میشه.
f(n)=n/2 و n^log3 با پایه ۳ که میشه n
n از n/2 بزرگتره و جواب میشه از مرتبه n
اگه بخوام جوابم مثل شما بشه باید n=n/2 در نظر بگیرم که جوابم در اونصورت nlogn میشه!!
کجارو دارم غلط میگم که جوابم اشتباه بدست میاد؟
واسه دومی هم میشه یکم در مورد اینکه lgn=lg(n/2)+1 رو چه طور به حل ربط دادید یه کم بیشتر توضیح بدید؟
خیلی ممنون
سوال ۱ حالت خاص قضیه مستره. توی این حالت مستر جواب نمیده.
سوال ۲ مجموع n/2 جمله اول میشه:
[tex]n\lg n\geq\lg n \lg(n-1) ... \lg(n/2)\geq (\lg n-1)\times \frac{n}{2}=\frac{n\lg n}{2}-\frac{n}{2}\in \theta(n\times\lg n)[/tex]
نصف دیگه جملات که از این مقدار کمترن.