می خوام ببینم مرتبه زمانی برای ۲ مثال زیر چطوری بدست میارن
من راه حلشو متوجه نمیشم
سلام.
دومی که خیلی سادس. نه درخت میخواد نه لازمه با روشای دیگه حلش کنید. جمع ۳ تا عبارته که بزرگترین مرتبه تو این چند جمله ای به عنوان تتا مرتبش در نظر گرفته میشه. رشد رادیکال 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]
این عبارت رو در نظر گرفتین؟!
من تو مبحث مرتبه زمانی و پیچیدگی مشکل دارم. یعنی سوالات رو نمیتونم خوب تحلیل کنم!!
تشکر.