سلام دوستان خسته نباشید میشه حل این سوال رو برام توضیح بین خیلی ممنون میشم.
[attachment=21398]
(۲۰ اسفند ۱۳۹۵ ۰۲:۱۳ ب.ظ)Hopegod نوشته شده توسط: سلام دوستان خسته نباشید میشه حل این سوال رو برام توضیح بین خیلی ممنون میشم.از روش درخت بازگشت حل کنید ، براحتی حل میشه .
سلام
جواب این تست [tex]\Theta(n^2)[/tex]
روش اول:
به کمک تعیین حدود و قضیه اصلی [tex]2T(\frac{n}{4})+n^2\le T(n)\le2T(\frac{n}{2})+n^2\: \: \Longrightarrow\: \: \: \Theta(n^2)\le T(n)\le\Theta(n^2)[/tex] پس [tex]T(n)\in\theta(n^2)[/tex]
روش دوم:
به کمک قضیه آکرا
[tex]\frac{1}{4^p}+\frac{1}{2^p}=1\: \: \: \Longrightarrow\: x=2^p\: \Longrightarrow\: \: x^2-x-1=0\: \: \Longrightarrow\: \: x=\frac{(1\pm\sqrt{5})}{2}\: \: \Longrightarrow\: p=\lg\frac{(1+\sqrt{5})}{2}[/tex]
محاسبه انتگرال [tex]\int_1^n\frac{x^2}{x^{p+1}}\: dx=\frac{1}{2-p}(n^{2-p}-1)\in\theta(n^{2-p})[/tex]
پس مرتبه رابطه برابر با [tex]\theta(n^p(1+\theta(n^{2-p})))=\theta(n^p+n^2)=\theta(n^2)[/tex] چون مقدار P کمتر از ۲ است
روش سومی هم برای اینگونه روابط وجود داره که نیاز به شروط توقف بازگشتی داره
اگر به جای n مقدار [tex]2^m[/tex] قرار دهیم داریم [tex]T(2^m)=T(2^{m-1})+T(2^{m-2})+(2^m)^2\: \Longrightarrow\: T(2^m)=S(m)\: \Longrightarrow\: S(m)=S(m-1)+S(m-2)+4^m[/tex] که دارای معادله مشخصه [tex](x^2-x-1)(x-4)=0[/tex]و با استفاده از راه حل کلاسیک معادله را حل می کنیم البته اگر سه شرط توقف بتونیم بدست بیاوریم
روش چهارم هم استفاده از روش درختیه اقدام به محاسبه هزینه ها تا دو شاخه کوتاهتر و طولانی تر میکینم
خیلی ممنونم
