(۱۵ دى ۱۳۹۶ ۰۵:۳۴ ب.ظ)msour44 نوشته شده توسط:  سلام
در سطح صفر(سطح ریشه) درخت بازگشت هزینه برابر n است
در سطح یک [tex]9t(\frac{n}{3})[/tex] داریم که هزینه هر کدام n/3 است پس هزینه ی کل سطح یک برابر با [tex]9(\frac{n}{3})[/tex]
در سطح دو [tex]9^2t(\frac{n}{3^2})[/tex] داریم با هزینه ی کل [tex]9^2(\frac{n}{3^2})[/tex]
به همین ترتیب در سطح i هزینه ی کل برابر با [tex]9^i(\frac{n}{3^i})[/tex]
که اگر [tex]t(1)=1[/tex] فرض کنیم [tex]i=\log_3n[/tex] می شود پس مجموع هزینه ها برابر با
[tex]n+9(\frac{n}{3})+9^2(\frac{n}{3^2})+...+9^i(\frac{n}{3^i})=n(1+3+3^2+...3^i)=n \times\frac{3^{(\log_3n)+1}-1}{3-1}=n\times\frac{3n-1}{2}=\theta(n^2)[/tex]
از خاصیت لگاریتمی [tex]a^{\log_bc}=c^{\log_ba}[/tex] استفاده شد یعنی [tex]3^{(\log_3n)+1}=3\times3^{\log_3n}=3\times n^{\log_33}=3n[/tex]

(۱۶ دى ۱۳۹۶ ۱۲:۵۷ ب.ظ)jumper نوشته شده توسط:  [quote='msour44' pid='450130' dateline='1515157446']


خیلیییی ممنون
حالا برای T(n)=T(n/2)T(2n/3)n هزینه ی سطح i میشه [tex](\frac{7}{6})^i[/tex]
پس در نهایت هزینه کلی چطور محاسبه میشه؟
[tex]T(n)=n\: (1+(\frac{7}{6})+(\frac{7}{6})^2+...(\frac{7}{6})^{\log_{\frac{3}{2}}n})=n(6((\f​rac{7}{6})^{\log_{\frac{3}{2}}n}-
۱))=?[/tex]

(۱۷ دى ۱۳۹۶ ۰۱:۳۱ ق.ظ)msour44 نوشته شده توسط:  

(16 دى ۱۳۹۶ ۱۲:۵۷ ب.ظ)jumper نوشته شده توسط:  [quote='msour44' pid='450130' dateline='1515157446']


خیلیییی ممنون
حالا برای T(n)=T(n/2)T(2n/3)n هزینه ی سطح i میشه [tex](\frac{7}{6})^i[/tex]
پس در نهایت هزینه کلی چطور محاسبه میشه؟
[tex]T(n)=n\: (1+(\frac{7}{6})+(\frac{7}{6})^2+...(\frac{7}{6})^{\log_{\frac{3}{2}}n})=n(6((\f​rac{7}{6})^{\log_{\frac{3}{2}}n}-
۱))=?[/tex]

سوال شما درست نمایش داده نمی شود حداقل برای من لطفا تصحیح کنید. در رابطه ی جدیدی که شما نوشتید احتمالا به صورت [tex]T(n)=T(\frac{n}{2})+T(\frac{2n}{3})+n[/tex] باشه. در این حالت باید دقت کنیم که درخت بازگشتی درخت پر نیست یعنی تمام برگ ها که نقطه ی پایان بازگشتی هستند در یک سطح نیستند مثلا شاخه سمت چپ(n/2) سریعتر به نقطه پایانی می رسد تا شاخه سمت راست درخت (۲n/3) . پس تا شاخه سمت چپ یک هزینه ی حداقلی بدست می اید (همان [tex]\Omega[/tex]) و اگر درخت را تا عمق شاخه سمت راستی پر فرض کنیم هزینه ی حداکثری بدست می اید (همان [tex]O[/tex]). برای شاخه ی سمت چپی n دائم بر ۲ تقسیم می شود پس سطح (i)را در ساده ترین حالت [tex]\log_2n[/tex] میگیرم و در شاخه سمت راست تا سطح [tex]\log_{\frac{3}{2}}n[/tex] در نظر می گیریم همان که شما رابطه ی ان را نوشتید. به نظر میاد در پیدا کردن مرتبه برای این رابطه نیاز به محا سبات لگاریتمی داریم .حالا باز شما رابطه تصحیح بفرماید یا بهتر این رابطه را به صورت سوال جداگانه مطرح کنید تا توسط دوستان پاسخ داده شود.

(۱۷ دى ۱۳۹۶ ۰۹:۰۴ ق.ظ)jumper نوشته شده توسط:  رابطه اصلاح شد من در همان قسمت محاسبات لگاریتمیش مشکل دارم جواب نهایی میشه [tex]nlog_{\frac{3}{2}}n[/tex] یا همان [tex]nlogn[/tex]

(۱۷ دى ۱۳۹۶ ۰۵:۱۳ ب.ظ)msour44 نوشته شده توسط:  

(17 دى ۱۳۹۶ ۰۹:۰۴ ق.ظ)jumper نوشته شده توسط:  رابطه اصلاح شد من در همان قسمت محاسبات لگاریتمیش مشکل دارم جواب نهایی میشه [tex]nlog_{\frac{3}{2}}n[/tex] یا همان [tex]nlogn[/tex]

دوست گرامی رابطه ی بازگشتی [tex]t(n)=t(\frac{n}{2})t(\frac{2n}{3})n[/tex] است یا [tex]t(n)=t(\frac{n}{2})+t(\frac{2n}{3})+n[/tex]؟
فک میکنم دومی باشه با توجه به محاسبه ی هزینه ها.[tex]n(1+\frac{7}{6}+(\frac{7}{6})^2+...(\frac{7}{6})^{\log_{\frac{3}{2}}n})=n\: \times\frac{\: (\frac{7}{6})^{\log_{\frac{3}{2}}n+1}-1}{\frac{7}{6}-1}[/tex] که نیاز به ماشین حساب دارد البته با کمک رابطه ی [tex]\log_ba=\frac{\log_ca}{\log_cb}[/tex] . تقریبا از مرتبه ی [tex]O(n^{1.38})[/tex] می شود که این هزینه ی حداکثری است و در حالت حداقلی در عبارت بالا مبنای لگاریتم به جای ۳/۲ عدد ۲ میشود و دارای مرتبه ی تقریبی [tex]\Omega(n^{1.22})[/tex].اینکه گفتید جواب نهایی [tex]nlogn[/tex] این جواب مربوط به وقتیه که در رابطه ی بازگشتی به جای [tex]t(\frac{n}{2})[/tex] عبارت [tex]t(\frac{n}{3})[/tex] داشته باشیم وگرنه مرتبه همان طور که تقریبی نوشتم بیشتر می شود.