سلام.. کسی این تست رو بلده ..تست علوم کامپیوتر سال ۹۱/////کلا اینجور سوالا که ضریب فرزندان یه عدد کسریه چه جوری با درخت بازگشتی حل میشه؟
T(n)= 3/2 T(n/2) - 1/2 T(n/4) - 1/n
یعنی هیچ کسی این سوالو بلد نیست..
(۲۰ مهر ۱۳۹۲ ۰۸:۰۲ ب.ظ)آنجلا نوشته شده توسط: یعنی هیچ کسی این سوالو بلد نیست..
سلام
[tex]T(n)=\frac{3}{2}T(\frac{n}{2})-\frac{1}{2}T(\frac{n}{4})-\frac{1}{n}[/tex]
[tex]n=2^k[/tex]
[tex]T(2^k)=\frac{3}{2}T(\frac{2^k}{2})-\frac{1}{2}T(\frac{2^K}{4})-\frac{1}{2^k}[/tex]
[tex]T(2^k)=G(k)[/tex]
[tex]G(k)=\frac{3}{2}G(k-1)-\frac{1}{2}G(k-2)-2^{-k}[/tex]
[tex]2G(k)=3G(k-1)-G(k-2)-2^{1-k}*[/tex]
[tex]G(k-1)=\frac{3}{2}G(k-2)-\frac{1}{2}G(k-3)-2^{1-k}**[/tex]
[tex]*-**=2G(k)-G(k-1)=3G(k-1)-\frac{5}{2}G(k-2) \frac{1}{2}G(k-3)[/tex]
[tex]G(k)=2G(k-1)-\frac{5}{4}G(k-2) \frac{1}{4}G(k-3)[/tex]
[tex]G(k)-2G(k-1) \frac{5}{4}G(k-2)-\frac{1}{4}G(k-3)=0[/tex]
[tex]G_k-2G_{k-1} \frac{5}{4}G_{k-2}-\frac{1}{4}G_{k-3}=0[/tex]
[tex]G^k-2G^{k-1} \frac{5}{4}G^{k-2}-\frac{1}{4}G^{k-3}=0[/tex]
[tex]\frac{G^k}{G^{k-3}}-\frac{2G^{k-1}}{G^{k-3}} \frac{5}{4}\frac{{}G^{k-2}}{G^{k-3}}-\frac{1}{4}\frac{{}G^{k-3}}{G^{k-3}}=0[/tex]
[tex]G^3-2G^2 \frac{5}{4}G-\frac{1}{4}=0[/tex]
[tex]r^3-2r^2 \frac{5}{4}r-\frac{1}{4}=0 \Rightarrow r_1=1,r_2=\frac{1}{2},r_3=\frac{1}{2}[/tex]
[tex]G(k)=c_1{1}^k c_2{\frac{1}{2}}^k c_3k{\frac{1}{2}}^k=\Theta (k{\frac{1}{2}}^k)[/tex]
[tex]G(k)=\Theta (k{\frac{1}{2}}^k)\Rightarrow T(2^k)=\Theta (k{\frac{1}{2}}^k)\Rightarrow T(n)=\frac{logn}{n}[/tex]