(۰۹ آبان ۱۳۹۳ ۰۸:۱۰ ب.ظ)kingmax نوشته شده توسط:  

(09 آبان ۱۳۹۳ ۰۷:۴۶ ب.ظ)mina_1 نوشته شده توسط:  سلام
تشریح پیچیدگی الگوریتم های این دوتا سوال رو میخاستم کمکم کنید.
سوال اول:
$T(n)=4\sqrt{n}T(\sqrt{n}) 2n^2$
جواب: $\theta(n^2)$

سوال دوم:
$T(n)=2T(n-1) \theta(1)$
جواب:$O(n)$


تشکر

سلام ببین اولی چند جمله ای هست و دارای چند جمله که مرتبه عبارت میشه بالاترین مرتبه ای که در چند جمله ای وجود داره و همان طور که میبینی در اولی بالاترین مرتبه متعلق به ۲n^2 هست و و در نتیجه مرتبه جمله دقیقا برابر n^2 هست که با تتا نشون میدن

وسوال دوم مرتبه دقیق سوال n-1 هست ولی خوب oی بزرگ یعنی کوچکتر و مساوی که n-1 کوچکتر از n هست

(۰۹ آبان ۱۳۹۳ ۰۸:۱۰ ب.ظ)kingmax نوشته شده توسط:  

(09 آبان ۱۳۹۳ ۰۷:۴۶ ب.ظ)mina_1 نوشته شده توسط:  سلام
تشریح پیچیدگی الگوریتم های این دوتا سوال رو میخاستم کمکم کنید.
سوال اول:
$T(n)=4\sqrt{n}T(\sqrt{n}) 2n^2$
جواب: $\theta(n^2)$

سوال دوم:
$T(n)=2T(n-1) \theta(1)$
جواب:$O(n)$


تشکر

سلام ببین اولی چند جمله ای هست و دارای چند جمله که مرتبه عبارت میشه بالاترین مرتبه ای که در چند جمله ای وجود داره و همان طور که میبینی در اولی بالاترین مرتبه متعلق به ۲n^2 هست و و در نتیجه مرتبه جمله دقیقا برابر n^2 هست که با تتا نشون میدن

وسوال دوم مرتبه دقیق سوال n-1 هست ولی خوب oی بزرگ یعنی کوچکتر و مساوی که n-1 کوچکتر از n هست