۲تا سوال داشتم.
۱-وقتی که توان معادله ناهمگن عدد گویا می شه باید چیکار کرد؟مثل :
T(2^k )=3T(2^(k-1) )+2^(3k/2)
۲- این چجوری حل میشه؟
T(n)=T(n/9)+T(8n/9)+θ(n)
صورت سوال را برای خوانایی بیشتر مجددا قرار دادم.
[tex]T(2^k)=3T(2^{k-1}) 2^{\frac{3k}{2}}[/tex]
[tex]T(n)=T(\frac{n}{9}) T(\frac{8n}{9}) θ(n)[/tex]
___________________________________________________________________
سوال دوم خیلی ساده است :
[tex]T(n)=T(\frac{n}{9}) T(\frac{8n}{9}) θ(n)[/tex]
باید درخت بازگشتی آن را رسم کنید و پاسخ آن می شود :
[tex]\theta(nlogn)[/tex]
------------------------------------------------------------------------------
برای حل سوال اول باید از تغییر متغیر زیر استفاده کنید :
[tex]m\: =\: 2k[/tex]
رابطه به این شکل می شود :
[tex]T(m)=3T(\frac{m}{2}) m^{\frac{3}{2}}[/tex]
این رابطه با استفاده از قضیه Master قابل حل است که می شود :
[tex]T(m)=\theta(m^{\frac{3}{2}})[/tex]
حالا m را جا گذاری نمایید :
[tex]T(2^k)=\theta(2^{\frac{3k}{2}})[/tex]