این سوال ۳۷ آزمون ۲۵% اول پارسه است
تو حلش به نظرم پارسه اشتباه کرده یعنی تغییر متغیر اشتباه داده
معادل این سوال، سواله ۲۳ فصل اول ۶۰۰ مسله قدسی هست که با روش پارسه اصلا درست در نمی یاد
من خودم اینجوری حل میکنم
[tex]\frac{T(n)}{n}=\frac{8T(\sqrt{n})}{\sqrt{n}} 2n[/tex]
[tex]S(n)=8S(\sqrt{n}) n[/tex]
[tex]S(2^m)=8S(2^{\frac{m}{2}}) 2^m[/tex]
[tex]S(m)=8S(\frac{m}{2}) 2^m[/tex]
تا اینجا میمونم چون [tex]2^m[/tex] محدود به چند جمله ای نیست که بشه Master زد
اما با درخت بریم میشه [tex]O(2^m)[/tex] که با تغییر متغیر میشه [tex]S(n)=O(n)[/tex]
و [tex]T(n)=O(n^2)[/tex]
لطفا کسی بلده راهنمایی کنه ممنون
سلام.راه حلتون درسته.به نظرم مشکلی نداره.
فقط اون [tex]S(m)\: =\: 8S(\frac{m}{2})\: \: 2^m[/tex] که نوشتین،به جای تابع S،دیگه باید از یه تابع دیگه استفاده کنید.مثلا بنویسید:
[tex]H(m)\: =\: 8H(\frac{m}{2})\: \: 2^m[/tex]
در نتیجه مرتبه [tex]H(m)[/tex] میشه [tex]O(2^m)[/tex]
پس مرتبه [tex]S(n)[/tex] میشه [tex]O(n)[/tex]
و در نهایت مرتبه [tex]T(n)[/tex] میشه [tex]O(n^2)[/tex]
جوابتون درسته.
ممنون از کمکهای خوبتون
امیدوارم موفق باشید
(۱۰ بهمن ۱۳۹۴ ۰۴:۰۹ ق.ظ)Iranian Wizard نوشته شده توسط: سلام.راه حلتون درسته.به نظرم مشکلی نداره.
فقط اون [tex]S(m)\: =\: 8S(\frac{m}{2})\: \: 2^m[/tex] که نوشتین،به جای تابع S،دیگه باید از یه تابع دیگه استفاده کنید.مثلا بنویسید:
[tex]H(m)\: =\: 8H(\frac{m}{2})\: \: 2^m[/tex]
در نتیجه مرتبه [tex]H(m)[/tex] میشه [tex]O(2^m)[/tex]
پس مرتبه [tex]S(n)[/tex] میشه [tex]O(n)[/tex]
و در نهایت مرتبه [tex]T(n)[/tex] میشه [tex]O(n^2)[/tex]
جوابتون درسته.
متاسفانه راه‌حل غلطه و جواب میشه [tex]O(nlog^3n)[/tex]