سلام
میشه اینو حل کنید؟
T(n)=2√nT(√n) + nlogn
سلام
طرفینو تقسیم بر n کن از تغییر متغییر g(n)=t(n)/n
سلام . با تشکر از راهنمایی دوستمون من روال کار رو توضیح میدم
[tex] {\color{Red}T(n)=2\sqrt{n}T(\sqrt{n}) nlogn}[/tex]
ابتدا طرفین تساوی رو بر n تقسیم میکنیم
[tex]\frac{T(n)}{n}=\frac{2\sqrt{n}T(\sqrt{n})}{n} \frac{nlogn}{n} \Rightarrow \frac{T(n)}{n}=\frac{2T(\sqrt{n})}{n*n^{-\frac{1}{2}}} \frac{nlogn}{n} \Rightarrow \frac{T(n)}{n}=\frac{2T(\sqrt{n})}{n^{\frac{1}{2}}} logn \Rightarrow \frac{T(n)}{n}=\frac{2T(\sqrt{n})}{\sqrt{n}} logn[/tex]
حالا از تغییر متغیر [tex]\frac{T(n)}{n}= S(n)[/tex] استفاده می کنیم که معادل [tex]T(n)=nS(n)[/tex] است
[tex]S(n)= 2S(\sqrt{n}) logn[/tex]
و حالا برای حل این T از تغییر متغیر [tex]n=2^{m}[/tex] استفاده کرده و به روش مستر حل میکنیم
[tex]S(m)= 2S(\frac{m}{2}) m \Rightarrow \theta (mlogm) \Rightarrow \theta (logn.loglogn)[/tex]
خب حالا با توجه به [tex]T(n)=nS(m)[/tex] که از قبل داشتیم جواب کلی میشه :
[tex]T(n)=nS(m) \Rightarrow n\theta (logn.loglogn) \Rightarrow {\color{Red} \theta(nlogn.loglogn)}[/tex]