سلام
حل این رابطه بازگشتی از چه مرتبه زمانی است؟
( با روش تغییر متغیر)
k<=2 T(k)=1
T(n)=n^1/2T(n^1/2)+n
سلام.
سوالتون رو توی جای درستی نپرسیدید.
کافی هست طرفین رو بر n تقسیم کنیم. نتیجه میشه:
[tex]\frac{T(n)}{n}=\frac{T(\sqrt{n})}{\sqrt{n}}+1[/tex]
حالا میایم مقدار [tex]\frac{T(n)}{n}\: [/tex] رو برابر با [tex]S(n)\: [/tex] در نظر میگیریم. در نتیجه:
[tex]S(n)=S(\sqrt{n})+1[/tex]
حالا از روش تغییر متغیر n رو برابر با [tex]۲^m[/tex] میگیریم، پس داریم:
[tex]S(2^m)=s(2^{\frac{m}{2}})+1[/tex]
حالا عبارت [tex]S(2^m)[/tex] رو برابر [tex]r(m)[/tex] می گیریم، پس داریم:
[tex]r(m)=r(\frac{m}{2})+1[/tex] که مرتبه ش میشه [tex]\theta(\log\: m)[/tex] که چون [tex]n=2^{m\: }\: \longrightarrow\: m=\log n[/tex] میشه [tex]\theta(\log\log n)[/tex] اما توی مرحله ی اول همه ی عبارت رو تقسیم بر n کردیم. پس مرتبه میشه [tex]\theta(n\cdot\log\log n)[/tex]
با تشکر از جوابتون
من سوال رو توی این قسمت مطرح کردم "طراحی الگوریتم(مهندسی و آی تی)"
حالا نمیدونم مشکل کجاست؟.ممنون میشم اگر راهنمای کنید.
یه سوال دیگه هم داشتم .مرتبه زمانی این رابطه رو هم میخواستم بدونم (اگر با درخت بازگشتی بگین که خیلی بهتر)در غیر اینصورت با تغییر متغیر
ممنون
۴n^1/2T(n^1/2)+2n^2
(۲۹ شهریور ۱۳۹۵ ۰۸:۳۸ ق.ظ)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]انجام دادیم بقیه ش رو میشه با درخت بگیم. که نوشتم خیلی سخت تر به جواب میرسه. حالا اگه بخواید مینویسم ولی واقعا به درد نمیخوره و گیج کننده ست.
هر دو سوال رو کاملا متوجه شدم
سو ال دوم از کتاب ۶۰۰ مسله بود.
سپاس فراوان