یعنی هیچ کسی این سوالو بلد نیست..

(۲۰ مهر ۱۳۹۲ ۰۸:۰۲ ب.ظ)آنجلا نوشته شده توسط:  یعنی هیچ کسی این سوالو بلد نیست..

سلام
$T(n)=\frac{3}{2}T(\frac{n}{2})-\frac{1}{2}T(\frac{n}{4})-\frac{1}{n}$
$n=2^k$
$T(2^k)=\frac{3}{2}T(\frac{2^k}{2})-\frac{1}{2}T(\frac{2^K}{4})-\frac{1}{2^k}$
$T(2^k)=G(k)$
$G(k)=\frac{3}{2}G(k-1)-\frac{1}{2}G(k-2)-2^{-k}$
$2G(k)=3G(k-1)-G(k-2)-2^{1-k}*$
$G(k-1)=\frac{3}{2}G(k-2)-\frac{1}{2}G(k-3)-2^{1-k}**$
$*-**=2G(k)-G(k-1)=3G(k-1)-\frac{5}{2}G(k-2) \frac{1}{2}G(k-3)$
$G(k)=2G(k-1)-\frac{5}{4}G(k-2) \frac{1}{4}G(k-3)$
$G(k)-2G(k-1) \frac{5}{4}G(k-2)-\frac{1}{4}G(k-3)=0$
$G_k-2G_{k-1} \frac{5}{4}G_{k-2}-\frac{1}{4}G_{k-3}=0$
$G^k-2G^{k-1} \frac{5}{4}G^{k-2}-\frac{1}{4}G^{k-3}=0$
$\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$
$G^3-2G^2 \frac{5}{4}G-\frac{1}{4}=0$
$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}$
$G(k)=c_1{1}^k c_2{\frac{1}{2}}^k c_3k{\frac{1}{2}}^k=\Theta (k{\frac{1}{2}}^k)$
$G(k)=\Theta (k{\frac{1}{2}}^k)\Rightarrow T(2^k)=\Theta (k{\frac{1}{2}}^k)\Rightarrow T(n)=\frac{logn}{n}$