تالار گفتمان مانشت

سلام
حل این رابطه بازگشتی از چه مرتبه زمانی است؟
( با روش تغییر متغیر)
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]

با تشکر از جوابتون
من سوال رو توی این قسمت مطرح کردم "طراحی الگوریتم(مهندسی و آی تی)"
حالا نمیدونم مشکل کجاست؟.ممنون میشم اگر راهنمای کنید.

---

یه سوال دیگه هم داشتم .مرتبه زمانی این رابطه رو هم میخواستم بدونم (اگر با درخت بازگشتی بگین که خیلی بهتر)در غیر اینصورت با تغییر متغیر
ممنون
4n^1/2T(n^1/2)+2n^2

(29 شهریور 1395 08:38 ق.ظ)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]انجام دادیم بقیه ش رو میشه با درخت بگیم. که نوشتم خیلی سخت تر به جواب میرسه. حالا اگه بخواید مینویسم ولی واقعا به درد نمیخوره و گیج کننده ست.

هر دو سوال رو کاملا متوجه شدم
سو ال دوم از کتاب 600 مسله بود.
سپاس فراوان