(۲۹ شهریور ۱۳۹۵ ۰۸:۳۸ ق.ظ)Alirezaj نوشته شده توسط: با تشکر از جوابتون
من سوال رو توی این قسمت مطرح کردم "طراحی الگوریتم(مهندسی و آی تی)"
حالا نمیدونم مشکل کجاست؟.ممنون میشم اگر راهنمای کنید.
یه سوال دیگه هم داشتم .مرتبه زمانی این رابطه رو هم میخواستم بدونم (اگر با درخت بازگشتی بگین که خیلی بهتر)در غیر اینصورت با تغییر متغیر
ممنون
۴n^1/2T(n^1/2)+2n^2
خواهش میکنم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
با تغییر متغیر:
[tex]T(n)=4\sqrt{n}T(\sqrt{n})+2n^2[/tex]
باز باید یه جوری از شر این رادیکال خلاص بشیم و همین طور از ضریب غیرثابت [tex]\sqrt{n}[/tex]
باز طرفین رو مثل سوال قبل بر n تقسیم می کنیم. میشه:
[tex]\frac{T(n)}{n}=\frac{4\sqrt{n}T(\sqrt{n})}{n}+\frac{2n^2}{n}[/tex] که برابر است با:
[tex]\frac{T(n)}{n}=\frac{4T(\sqrt{n})}{\sqrt{n}}+2n[/tex]
[tex]\frac{T(n)}{n}=S(n)[/tex] در نتیجه: [tex]S(n)=4S(\sqrt{n})+2n[/tex]
که با روش تغییر متغیر n رو میگیریم [tex]۲^m[/tex] تا از شر رادیکال خلاص بشیم.
در نتیجه داریم: [tex]S(2^m)=4S(2^{\frac{m}{2}})+2^{m+1}[/tex]
حالا [tex]S(2^m)=R(m)[/tex] در نظر می گیریم، پس: [tex]R(m)=4R(\frac{m}{2})+2^{m+1}[/tex]
که می تونیم از قضیه ی اصلی بریم و [tex]f(m)=2^{m+1}[/tex] از طرفی [tex]m^{\log_{b^a}}=m^{\log_2^4}=m^2[/tex] و از اونجا که [tex]m^2\in o(2^{m+1})[/tex] پس مرتبه ی تابع میشه: [tex]\theta(2^{m+1})[/tex]
m برابر است با logn: [tex](2^{m+1})=(2\cdot2^m)=(2\cdot2^{\log_2n})=(2\cdot n)[/tex]
و از طرفی یه جا کل عبارت رو بر n تقسیم کردیم، پس مرتبه ی تابع میشه: [tex]\theta(2n^2)=\theta(n^2)[/tex]
نمیشه با درخت بازگشت از اولش گفت، چون که ضریب غیرثابت داره، گره ی ریشه یعنی [tex]T(n)[/tex] که نمیتونه [tex]4\sqrt{n}[/tex] تا فرزند داشته باشه.
اما وقتی مراحل بالا رو تا رسیدن به[tex]R(m)=4R(\frac{m}{2})+2^{m+1}[/tex]انجام دادیم بقیه ش رو میشه با درخت بگیم. که نوشتم خیلی سخت تر به جواب میرسه. حالا اگه بخواید مینویسم ولی واقعا به درد نمیخوره و گیج کننده ست.
