(۲۲ آبان ۱۳۹۵ ۱۱:۳۷ ق.ظ)ziba_khofte نوشته شده توسط:  سلام . میشه در حل این رابطه بازگشتی به من کمک کنید؟

از براکت‌ها که میشه صرف نظر کرد:
[tex]T(n)=2T(\frac{n}{2})+2[/tex]
که این رو هم میشه به روش Akra-Bazi یا بسط دادن حل کرد. در
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که P=1 بدست میاد، پس
[tex]T(n)=n^{1\: }(1+\int_1^n\frac{2}{x^2}dx)=n(1-\frac{2}{n} + 2)=3n[/tex]
در روش بسط دادن هم:
[tex]T(n)=2T(\frac{n}{2})+2=2(2T(\frac{n}{4})+2)+2=4T(\frac{n}{4})+4+2=8T(\frac{n}{8}​)+8+4+2=...=2^kT(\frac{n}{2^k})+2^k+2^{k-1}+...+4+2[/tex]
که K رو میتونیم تا [tex]2^k=n\: \rightarrow\: k=\lg(n)[/tex] جلو ببریم. پس
[tex]T(n)=2^{\log n}+\frac{2^{\log n}}{2\: }+\frac{2^{\log n}}{\: 4}+...+8+4+2=n+\frac{n}{2}+\frac{n}{4}+...+4+2\approx2n=\theta(n)[/tex]