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

می خوام ببینم مرتبه زمانی برای ۲ مثال زیر چطوری بدست میارن
من راه حلشو متوجه نمیشم

سلام.
دومی که خیلی سادس. نه درخت میخواد نه لازمه با روشای دیگه حلش کنید. جمع 3 تا عبارته که بزرگترین مرتبه تو این چند جمله ای به عنوان تتا مرتبش در نظر گرفته میشه. رشد رادیکال n که خیلی آهسته تر از nدومه و از دور خارج میشه. n دوم هم از مرتبه nه . آخریشم که nه دیگه. یعنی کلاً از مرتبه n در میاد.

در مورد سوال اول همان طور که ذکر کرده عبارت [tex]S(n)=2T(n/3) \theta (n^{\sqrt{lgn}})[/tex] را به جای [tex]T(n)[/tex] قرار داده

چون [tex]T(n)\leq S(n)[/tex] یعنی به جای عبارت [tex]T(n/6)[/tex] چون [tex]T(n/6)\leq T(n/3)[/tex] عبارت [tex]T(n/3)[/tex] قرار

داده لذا در معادله جدید اگر بنابر قاعده : [tex]T(n)=aT(n/b) C.F(n)[/tex] پیش برویم داریم [tex]n^{log a} < O(n^{\sqrt{lgn}})[/tex] پس عبارت [tex]\theta (n^{\sqrt{lgn}})[/tex] مرتبه زمانی مد نظر هست

---

[tex]\sqrt{n}[/tex] کمتر از [tex]n/2[/tex] هستش لذا بین دو عبارت بعدی [tex]a=1< (b=2)^{(k=1)}[/tex] پس داریم :

[tex]T(n)=\theta (n^{k})=\theta (n)[/tex]

من خوب متوجه نشدم. سوال اول رو لطفا دوباره توضیح بدین. چرا برای [tex]S(n)[/tex]
این عبارت رو در نظر گرفتین؟!
من تو مبحث مرتبه زمانی و پیچیدگی مشکل دارم. یعنی سوالات رو نمیتونم خوب تحلیل کنم!!
تشکر.