سلام . دوستان این دو معادله رو از کتاب ۶۰۰ مساله آوردم . نمیفهمم که چه فرقی توی این دوتا هست که دومین رابطه جوابش مثل اولی نمیشه ! من وقتی درختش رو رسم میکنم به این نتیجه میرسم که جواب باید دقیقا مثل اولی باشه . ممنون میشم توضیحی برای دومی ارائه بدید
![[تصویر: 426819_42lw_capture.jpg]](https://img.manesht.ir/426819_42lw_capture.jpg)
شاید دلیلش اینه که جمع ضرایب کوچکتر از ۱ میشه پس ثابت در نظر میگیرتش
(۰۹ آذر ۱۳۹۵ ۱۲:۵۶ ب.ظ)kilookiloo نوشته شده توسط: سلام . دوستان این دو معادله رو از کتاب ۶۰۰ مساله آوردم . نمیفهمم که چه فرقی توی این دوتا هست که دومین رابطه جوابش مثل اولی نمیشه ! من وقتی درختش رو رسم میکنم به این نتیجه میرسم که جواب باید دقیقا مثل اولی باشه . ممنون میشم توضیحی برای دومی ارائه بدیدسلام.با روشهای زیادی میشه حلش کرد.
شاید دلیلش اینه که جمع ضرایب کوچکتر از ۱ میشه پس ثابت در نظر میگیرتش
۱)درخت بازگشت
[attachment=20938]
---------------------------------------------------
۲)قضیه Akra-Bazzi
ابتدا p رو محاسبه میکنیم:
[tex]\frac{1}{4^p}\: +\: \frac{1}{2^p}\: =\: 1\: \: \longrightarrow\: \: (\frac{1}{4})^p+(\frac{1}{2})^p=1\: \: \longrightarrow\: \: (\frac{1}{2^2})^p+(\frac{1}{2})^p=1\: \: \longrightarrow\: \: 2^{-2p}\: +\: 2^{-p}\: =1\: \: \longrightarrow\: (2^{-p})^2\: +\: (2^{-p})\: =1[/tex]
[tex](2^{-p})^2\: +\: (2^{-p})\: =1\: \longrightarrow\: if\: 2^{-p}=k\: \: \longrightarrow\: \: k^2\: +\: k\: -1\: =0\: \: \longrightarrow\: \: k\: =\: \frac{-1\: \pm\: \sqrt{5}}{2}\: \: \longrightarrow\: \: 2^{-p}\: =\: \frac{-1\: \pm\: \sqrt{5}}{2}\: \: \: \longrightarrow\: \: \frac{1}{2^p}\: =\: \frac{-1\pm\sqrt{5}}{2}\: \: \longrightarrow\: 2^p\: =\frac{\: 2}{-1\pm\sqrt{5}}\: \: \longrightarrow\: p=\log^{\frac{2}{-1+\sqrt{5}}}_2\: =\: \lg2\: -\: \lg(-1+\sqrt{5})\: =\varepsilon[/tex]
سپس محاسبه فرمول زیر:
[tex]T(n)=\: \theta(n^p(1+\int_1^n\frac{f(u)}{u^{p+1}}du))\: =\: \theta(n^p(1+\int_1^n\frac{u^2}{u^{p+1}}du))\: =\: \theta(n^p(1+\int_1^nu^{1-p}du))\: =\: \theta(n^p(1+\frac{n^{2-p}}{2-p}-\frac{1}{2-p}))\: =\: \theta(n^p(\frac{1-p+n^{2-p}}{2-p}))\: =\: \theta(\frac{n^p}{2-p}\: -\frac{pn^p}{2-p}\: +\frac{\: n^2}{2-p})\: =\: \theta(\frac{(1-p)n^p}{2-p}\: +\: \frac{n^2}{2-p})\: [/tex]
که چون P یک مقدار بین ۰ و ۱ است،پس جواب برابر است با:
[tex]T(n)=\: \theta(n^2)[/tex]
-------------------------------------------------------------
۳- با تغییر متغیر هم میتونید جوابشو بدست بیارید.
سلام. وقت بخیر.
پیشنهاد میکنم روش Akra-Bazi رو مطالعه کنید. اینکه مجموع ضرایب چه رابطه‌ای با توان قسمت ناهمگن داره. تو عکسی که آپلود کردید اگه توان n رو (هم تو قسمت ناهمگن هم تو مرتبه زمانی) برابر ۱ درنظر بگیرید، رابطه درست میشه.
(۰۹ آذر ۱۳۹۵ ۱۲:۵۶ ب.ظ)kilookiloo نوشته شده توسط: سلام . دوستان این دو معادله رو از کتاب ۶۰۰ مساله آوردم . نمیفهمم که چه فرقی توی این دوتا هست که دومین رابطه جوابش مثل اولی نمیشه ! من وقتی درختش رو رسم میکنم به این نتیجه میرسم که جواب باید دقیقا مثل اولی باشه . ممنون میشم توضیحی برای دومی ارائه بدید
شاید دلیلش اینه که جمع ضرایب کوچکتر از ۱ میشه پس ثابت در نظر میگیرتش
سلام.این دو مسله سوال اول و پنجم ۶۰۰مسله هست که اونجا مسله (شماره ۱) اشتباه حل شده( اشتباه چاپی احتمالا ) و اگر به فصل ۹- ۶۰۰ مسله هم توجه کنید مبینید که گزینه صحیح مسله ۱ -گزینه شماره ۴ است در واقع هر دو سوال از نظر رشد یکسان میباشند.
پیچیدگی هر دو یکسان است و در واقع شما سوال اول رو اشتباه حل میکنید که توی ۶۰۰ مسله هم در قسمت حل تشریحی اشتباه حل شده !!!!
مرتبه زمانی هر دو سوال
[tex]T(n)=\: \theta(n^2)[/tex]
ممنون از همه ی دوستان
