سلام

برای حل این رابطه بازگشتی باید علاوه بر تغییر متغیر از روش حل معادلات ناهمگن هم استفاده کنیم. راه حل به این صورت هست که:

اول از تغییر متغیر رو به رو استفاده میکنیم : [tex]n=2^m[/tex] و از اینجا [tex]m=logn[/tex] به دست میاد

خوب حالا میریم جایگزاری رو انجام میدیم: [tex]T(2^m)=\frac{3}{2}T(2^{m-1})-\frac{1}{2}T(2^{m-2})-\frac{1}{2^m}[/tex]

الان برای ساده تر شدن معادله از تغییر اسم استفاده میکنیم : [tex]T(2^m)=F(m)[/tex]

پس معادله به این شکل میشه : [tex]F(m)=\frac{3}{2}F(m-1)-\frac{1}{2}F(m-2)-(\frac{1}{2})^m[/tex]

اگه دقت کنید معادله به صورت رو به رو میشه : [tex]F(m)-\frac{3}{2}F(m-1) \frac{1}{2}F(m-2)=-(\frac{1}{2})^m[/tex] که قسمدر قسمت راستش به صورت همگن هست و چپ ناهمگن. پس ریشه ها به صورت زیر میشن:

[tex](x^2-\frac{3}{2}x \frac{1}{2})(x-\frac{1}{2})=0=>(x-\frac{1}{2})(x-1)(x-\frac{1}{2})=o=>x=\frac{1}{2},x=1[/tex]

دقت کنید که [tex]\: x=\frac{1}{2}[/tex] ریشه مضاعف هست پس داریم:
[tex]F(m)=(\alpha_1 \alpha_2m)(\frac{1}{2})^m \alpha_3(1)^m,m=\log n=>T(n)=(\alpha_1 \alpha_2\log n)(\frac{1}{n}) \alpha_3[/tex]

و در آخر با جایگزاری [tex]T(1),T(2)[/tex] در معادله بالا مقدار [tex]\alpha_1و\alpha_2و\alpha_3[/tex] به دست میان.

[tex]T(1)=(\alpha_1 \alpha_2\log(1)) \alpha_3=>\alpha_1 \alpha_3=1[/tex]

[tex]T(1)=\frac{1}{2}(\alpha_1 \alpha_2\log(2)) \alpha_3=>\frac{1}{2}(\alpha_1 \alpha_2) \alpha_3=\frac{3}{2}[/tex]

بعدش معادلات رو باید حل کرد

ممنون دوست عزیز
خواهشاً سوال رو بخونید بعد جواب بدید، این مراحل رو میدونم من سوالم همین بدست اوردن آلفاها هست.
میدونم یه جایگذاری ساده هست ولی من جوابم با کتاب جور نمیشه میخوام ببینم اشکال کارم کجاست.

(۱۶ دى ۱۳۹۳ ۰۸:۳۵ ب.ظ)Ametrine نوشته شده توسط:  ممنون دوست عزیز
خواهشاً سوال رو بخونید بعد جواب بدید، این مراحل رو میدونم من سوالم همین بدست اوردن آلفاها هست.
میدونم یه جایگذاری ساده هست ولی من جوابم با کتاب جور نمیشه میخوام ببینم اشکال کارم کجاست.

جوابای منم درست در نیومد

سلام.خب دوستمون اکثرشو نوشت حالا من تیکه اخرشو مینویسم:

معادله که این بود: [tex]T(n)=\frac{3}{2}T(\frac{n}{2})-\frac{1}{2}T(\frac{n}{4})-\frac{1}{n}[/tex]

اینم شروط اولیه: [tex]T(1)=1,T(2)=\frac{3}{4}[/tex]

خب تا اینجا هم پیش اومدیم که: [tex]T(n)=(\alpha_1 \alpha_2Lg(n))\frac{1}{n} \alpha_3[/tex]

خب با توجه به شرایط اولیه پیش میریم:
[tex]T(1)=1=(\alpha_1 \alpha_2Lg(1))\frac{1}{1} \alpha_3\rightarrow\alpha_1 \alpha_3=1[/tex]
[tex]T(2)=\frac{3}{2}=(\alpha_1 \alpha_2Lg(2))\frac{1}{2} \alpha_3\rightarrow\alpha_1 \alpha_2 2\alpha_3=3[/tex]
(طرفین رو در ۲ ضرب کردم)
خب الان همون طور که متوجه شدی یه مشکلی هستش؟؟
بله ۳ تا مجهول داریم و ۲ تا معادله و این کار ما رو راه نمیندازه.پس یه کاری میکنیم اونم این که یه جمله دیگه رو به دست میاریم
خب [tex]T(3)[/tex] رو به دست میاریم!!!
ولی دقت کنی یه نکته ظریف میبینی و اونم اینکه ما تو جمله [tex]T(n)[/tex] یه [tex]\frac{n}{4}[/tex] داریم که اگه ۳ بذاریم به جمله [tex]T(0)[/tex] وابسته میشیم که به درد کارمون نمیخوره ولی [tex]T(4)[/tex] جون میده واسه کار ما
خب [tex]T(4)[/tex] رو حساب میکنیم:
[tex]T(4)=\frac{3}{2}T(\frac{4}{2})-\frac{1}{2}T(\frac{4}{4})-\frac{1}{4}\rightarrow T(4)=\frac{3}{2}[/tex]

خب حالا معادله سوم رو تشکیل میدیم:
[tex]T(4)=\frac{3}{2}=(\alpha_1 \alpha_22Lg(2))\frac{1}{4} \alpha_3\rightarrow\alpha_1 2\alpha_2 4\alpha_3=6[/tex]

خب معادله اول رو اینطوری مینویسیم:
[tex]\alpha_1 \alpha_3=1\rightarrow\alpha_1=1-\alpha_3[/tex]
حالا اینو تو معادله ۲ و ۳ جایگداری کنیم [tex]\alpha_2=1,\alpha_3=1[/tex]
و طبق رابطه اول هم [tex]\alpha_1=0[/tex]
پس جواب کلی میشه:
[tex]T(n)=(\alpha_1 \alpha_2Lg(n))\frac{1}{n} \alpha_3\rightarrow T(n)=\frac{Lg(n)}{n} 1[/tex]

اینم از این

تشکــر