۰
subtitle
ارسال: #۱
یک مساله از بازگشتی
سلام
میشه اینو حل کنید؟
T(n)=2√nT(√n) + nlogn
میشه اینو حل کنید؟
T(n)=2√nT(√n) + nlogn
۰
۰
ارسال: #۳
RE: یک مساله از بازگشتی
سلام . با تشکر از راهنمایی دوستمون من روال کار رو توضیح میدم
ابتدا طرفین تساوی رو بر n تقسیم میکنیم
حالا از تغییر متغیر [tex]\frac{T(n)}{n}= S(n)[/tex] استفاده می کنیم که معادل [tex]T(n)=nS(n)[/tex] است
و حالا برای حل این T از تغییر متغیر [tex]n=2^{m}[/tex] استفاده کرده و به روش مستر حل میکنیم
خب حالا با توجه به [tex]T(n)=nS(m)[/tex] که از قبل داشتیم جواب کلی میشه :
[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]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close