(۲۶ مرداد ۱۳۹۳ ۱۲:۵۲ ق.ظ)miladcr7 نوشته شده توسط:  سلام. دوستمون بالا برات کامل توضیح رو نوشته.حالا منم یه توضیحی میدم:

رابطمون اینه:$T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n$


طبق قضیه میدونیم که توی این روابط:$T(n)=T(\alpha n) T(\beta n) n$

اگه این شرط رو داشته باشیم:$\alpha \beta<1$ جواب برابر $\theta(n)$ میشه حالا برای ارتفاع:

یه بار دیگه رابطه رو داشته باش:$T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n$

خب هر بار درخت ما به $\frac{2n}{5}$ و $\frac{3n}{10}$ شکسته میشه و اگه دقت کنی شاخه $\frac{3n}{10}$ سریع تر به ۱ میرسه(همون طور که میدونی ما درخت رو تا زمانی که به ۱ میرسیم میشکنیم) و شاخه $\frac{2n}{5}$ دیرتر به ۱ میرسه و ارتفاع هم طولانی ترین مسیره دیگه درسته؟
پس شاخه $\frac{2n}{5}$ همون ارتفاع میشه حالا میخوایم ارتفاع رو حساب کنیم:

$k=(\frac{2}{5})^kn=1\rightarrow n=(\frac{5}{2})^k\rightarrow k=\lg^n_{\frac{5}{2}}$

که این $k$ همون ارتفاع درخته.یه توضیح درباره فرمول بالا هر چند حتما خودت بلدی ولی خب برای تمرین خودمه
فرض کردیم که $k$ ارتفاع درخته و باید برابر $(\frac{2}{5})^kn=1$ شه.حالا چرا ۱؟چون درخت رو تا زمانی میشکنیم که به ۱ میرسیم دیگه درسته؟
پس ارتفاع هم اینجوری به دست میاد.بقیشم که دیگه یه سری هندسیه

(۲۶ مرداد ۱۳۹۳ ۱۲:۰۸ ق.ظ)ADELZX نوشته شده توسط:  

(25 مرداد ۱۳۹۳ ۱۰:۵۶ ب.ظ)shayesteb نوشته شده توسط:  

(25 مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:  

(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط:  سلام دوستان

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


$T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n$

ممنون میشم

ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش

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

مجموع هزینه های هر سطح درخت رو که جمع بزنی به سری زیر میرسی که خب جواب واضحه

$\sum_{i=1}^{\log n}(\frac{7}{10})^in=\theta(n)$

(۲۵ مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط:  سلام دوستان

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


$T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n$

ممنون میشم

(۲۵ مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:  

(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط:  سلام دوستان

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


$T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n$

ممنون میشم

ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش

(۲۵ مرداد ۱۳۹۳ ۱۰:۵۶ ب.ظ)shayesteb نوشته شده توسط:  

(25 مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:  

(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط:  سلام دوستان

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


$T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n$

ممنون میشم

ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش

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