سلام
جواب این تست [tex]\Theta(n^2)[/tex]
روش اول:
به کمک تعیین حدود و قضیه اصلی [tex]2T(\frac{n}{4})+n^2\le T(n)\le2T(\frac{n}{2})+n^2\: \: \Longrightarrow\: \: \: \Theta(n^2)\le T(n)\le\Theta(n^2)[/tex] پس [tex]T(n)\in\theta(n^2)[/tex]
روش دوم:
به کمک قضیه آکرا
[tex]\frac{1}{4^p}+\frac{1}{2^p}=1\: \: \: \Longrightarrow\: x=2^p\: \Longrightarrow\: \: x^2-x-1=0\: \: \Longrightarrow\: \: x=\frac{(1\pm\sqrt{5})}{2}\: \: \Longrightarrow\: p=\lg\frac{(1+\sqrt{5})}{2}[/tex]
محاسبه انتگرال [tex]\int_1^n\frac{x^2}{x^{p+1}}\: dx=\frac{1}{2-p}(n^{2-p}-1)\in\theta(n^{2-p})[/tex]
پس مرتبه رابطه برابر با [tex]\theta(n^p(1+\theta(n^{2-p})))=\theta(n^p+n^2)=\theta(n^2)[/tex] چون مقدار P کمتر از ۲ است
روش سومی هم برای اینگونه روابط وجود داره که نیاز به شروط توقف بازگشتی داره
اگر به جای n مقدار [tex]2^m[/tex] قرار دهیم داریم [tex]T(2^m)=T(2^{m-1})+T(2^{m-2})+(2^m)^2\: \Longrightarrow\: T(2^m)=S(m)\: \Longrightarrow\: S(m)=S(m-1)+S(m-2)+4^m[/tex] که دارای معادله مشخصه [tex](x^2-x-1)(x-4)=0[/tex]و با استفاده از راه حل کلاسیک معادله را حل می کنیم البته اگر سه شرط توقف بتونیم بدست بیاوریم
روش چهارم هم استفاده از روش درختیه اقدام به محاسبه هزینه ها تا دو شاخه کوتاهتر و طولانی تر میکینم