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

سلام . میشه در حل این رابطه بازگشتی به من کمک کنید؟

(22 آبان 1395 11:37 ق.ظ)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]

ممنونم.چیزی که من رو به شک انداخته بود که چند جایی دیدم که این رابطه را به عنوان رابطه بازگشتی برای پیدان کردن همزمان عنصر ماکزیمم و مینمم ارایه نوشته بود و نوشته بود که بعد از حل میرسیم به رابطه زیر.منم هر کار کردم نتوانستم این رابطه رو بدست بیاورم.



.left\{\begin{matrix}\frac{3n}{2}-2 \: \: if(n=2k) \\ \frac{3n}{2}-\frac{3}{2} \: \: \: \: \: \: \: \: \: if(n=2k+1)\end{matrix}\right\

[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]

وقت بخیر
ببخشید ممکن بگید انتگرال این رابطه چطوری محاسبه میشود؟!!!

(25 آبان 1395 02:52 ب.ظ)Alirezaj نوشته شده توسط: [ -> ][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]\int^n_1\frac{2}{x^2}dx=2\int^n_1\frac{1}{x^2}dx=2\int^n_1x^{-2}dx=\frac{2x^{-2+1}}{-2+1}=-2x^{-1}|_{x=1}^{x=n}=-2n^{-1}-(-2\cdot(1)^{-1})=-\frac{2}{n}+2[/tex]

[

وقت بخیر
ببخشید ممکن بگید انتگرال این رابطه چطوری محاسبه میشود؟!!!
[/quote]
سلام.
برای محاسبه ی انتگرال:
[tex]\int^n_1\frac{2}{x^2}dx=2\int^n_1\frac{1}{x^2}dx=2\int^n_1x^{-2}dx=\frac{2x^{-2+1}}{-2+1}=-2x^{-1}|_{x=1}^{x=n}=-2n^{-1}-(-2\cdot(1)^{-1})=-\frac{2}{n}+2[/tex]
[/quote]

سلام
خیلی ممنون.