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

سلام
تشریح پیچیدگی الگوریتم های این دوتا سوال رو میخاستم کمکم کنید.
سوال اول:
[tex]T(n)=4\sqrt{n}T(\sqrt{n}) 2n^2[/tex]
جواب: [tex]\theta(n^2)[/tex]

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


تشکر

(09 آبان 1393 07:46 ب.ظ)mina_1 نوشته شده توسط: [ -> ]سلام
تشریح پیچیدگی الگوریتم های این دوتا سوال رو میخاستم کمکم کنید.
سوال اول:
[tex]T(n)=4\sqrt{n}T(\sqrt{n}) 2n^2[/tex]
جواب: [tex]\theta(n^2)[/tex]

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


تشکر

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

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

(09 آبان 1393 08:10 ب.ظ)kingmax نوشته شده توسط: [ -> ]

(09 آبان 1393 07:46 ب.ظ)mina_1 نوشته شده توسط: [ -> ]سلام
تشریح پیچیدگی الگوریتم های این دوتا سوال رو میخاستم کمکم کنید.
سوال اول:
[tex]T(n)=4\sqrt{n}T(\sqrt{n}) 2n^2[/tex]
جواب: [tex]\theta(n^2)[/tex]

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


تشکر

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

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

تشکر از لطف شما
درمورد سوال دوم اینکه مرتبه دقیق رو بیان کردید اگه بیشتر توضیح بدین ممنون میشم

خوب اینم مثل اولی چند جمله ای هست که کلا شامل دو جمله هست اولی مرتبه اش n-1 هست و دومی 1 خوب معلومه که n-1 بزرگتره و مرتبه دقیق سوال که با تتا نشونش میدن میشه n-1 ولی همین n-1 را میتوان
با (O(n-1
(O(n
(o(n
(θ(n-1
(Ω(n-1
(Ω(n-2
(w(n-2
نمایش داد همه ی اینا مفهوم مرتبه n-1 را میرسونن

(09 آبان 1393 08:10 ب.ظ)kingmax نوشته شده توسط: [ -> ]

(09 آبان 1393 07:46 ب.ظ)mina_1 نوشته شده توسط: [ -> ]سلام
تشریح پیچیدگی الگوریتم های این دوتا سوال رو میخاستم کمکم کنید.
سوال اول:
[tex]T(n)=4\sqrt{n}T(\sqrt{n}) 2n^2[/tex]
جواب: [tex]\theta(n^2)[/tex]

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


تشکر

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

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

سلام این سوال در پست دیگه ای هم پرسیده شده.جوابش هم کامل هست.لینکشم میذارم براتون.اولین مورد با دو تا تغییر متغیر حل میشه که در نهایت جواب [tex]n^2[/tex] میشه و دومی هم فک کنم جوابش تو کتاب دکتر قدسی اشتباهه و باید [tex]2^n[/tex] شه

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.