07 مرداد 1390, 11:39 ب.ظ
09 مرداد 1390, 01:06 ب.ظ
[tex]\small \bg_white \fn_jvn T(n)=4T(\frac{\sqrt{n}}{3}) \log^{2} n\\ \xrightarrow[ ]{n=2^{(2^{\mathbf{x}})}}\ T(2^{(2^{\mathbf{x}})})=4T(2^{(2^{\mathbf{x-1}})}) 4^{\mathbf{x}}\\ \xrightarrow[ ]{T(2^{(2^{\mathbf{x}})})=F(\mathbf{x})}\ F(\mathbf{x})=4F(\mathbf{x}-1) 4^{\mathbf{x}}\\ (r-4)^{2}=0\Rightarrow F(\mathbf{x})=(a\mathbf{x} b )4^{\mathbf{x}}=\mathbf{\theta} (x4^{\mathbf{x}})=\mathbf{\theta} (\log \log n \ log^{2} n)[/tex]
09 مرداد 1390, 07:31 ب.ظ
قسمت آخر از روی معادله مشخصه شکل جواب بدست اومده
از ۱/۳ هم بدلیل وجود رادیکال روی n میشه صرف نظر کرد چون رادیکال تاثیر بیشتری روی کم شدن n داره
تا تقسیم بر ۳/
اگر اشتباه میگم دوستان کمک کنند
البته این تغییر متغیر راحت‌تر جواب میده:
[tex]\tiny \fn_jvn \small \bg_white \fn_jvn T(n)=4T(\frac{\sqrt{n}}{3}) \log^{2} n\\ \xrightarrow[ ]{n=2^{\mathbf{x}}}\ T(2^{\mathbf{x}})=4T(2^{\frac{\mathbf{x}}{2}}) \mathbf{x}^{2}\\ \xrightarrow[ ]{T(2^{\mathbf{x}})=F(\mathbf{x})}\ F(\mathbf{x})=4F(\frac{\mathbf{x}}{2}) \mathbf{x}^{2}\\ \xrightarrow[ ]{master} F(\mathbf{x})=\mathbf{\theta} (\log x\ x^{2})=\mathbf{\theta} (\log \log n \ log^{2} n)[/tex]
از ۱/۳ هم بدلیل وجود رادیکال روی n میشه صرف نظر کرد چون رادیکال تاثیر بیشتری روی کم شدن n داره
تا تقسیم بر ۳/
اگر اشتباه میگم دوستان کمک کنند
البته این تغییر متغیر راحت‌تر جواب میده:
[tex]\tiny \fn_jvn \small \bg_white \fn_jvn T(n)=4T(\frac{\sqrt{n}}{3}) \log^{2} n\\ \xrightarrow[ ]{n=2^{\mathbf{x}}}\ T(2^{\mathbf{x}})=4T(2^{\frac{\mathbf{x}}{2}}) \mathbf{x}^{2}\\ \xrightarrow[ ]{T(2^{\mathbf{x}})=F(\mathbf{x})}\ F(\mathbf{x})=4F(\frac{\mathbf{x}}{2}) \mathbf{x}^{2}\\ \xrightarrow[ ]{master} F(\mathbf{x})=\mathbf{\theta} (\log x\ x^{2})=\mathbf{\theta} (\log \log n \ log^{2} n)[/tex]