سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
(۲۵ مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط: سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
ارتفاع درخت معادل یه سری میشه که رابطه cn رو به ما میده، پس کل زمان در نهایت از تتای n هستش
(۲۵ مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط: سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش
ممنون از پاسختون. میشه بگید ارتفاع درخت را چطوری محاسبه کردید؟
(۲۵ مرداد ۱۳۹۳ ۱۰:۵۶ ب.ظ)shayesteb نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط: سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش
ممنون از پاسختون. میشه بگید ارتفاع درخت را چطوری محاسبه کردید؟
مجموع هزینه های هر سطح درخت رو که جمع بزنی به سری زیر میرسی که خب جواب واضحه
[tex]\sum_{i=1}^{\log n}(\frac{7}{10})^in=\theta(n)[/tex]
سلام. دوستمون بالا برات کامل توضیح رو نوشته.حالا منم یه توضیحی میدم:
رابطمون اینه:[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
طبق قضیه میدونیم که توی این روابط:[tex]T(n)=T(\alpha n) T(\beta n) n[/tex]
اگه این شرط رو داشته باشیم:[tex]\alpha \beta<1[/tex] جواب برابر [tex]\theta(n)[/tex] میشه حالا برای ارتفاع:
یه بار دیگه رابطه رو داشته باش:[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
خب هر بار درخت ما به [tex]\frac{2n}{5}[/tex] و [tex]\frac{3n}{10}[/tex] شکسته میشه و اگه دقت کنی شاخه [tex]\frac{3n}{10}[/tex] سریع تر به ۱ میرسه(همون طور که میدونی ما درخت رو تا زمانی که به ۱ میرسیم میشکنیم) و شاخه [tex]\frac{2n}{5}[/tex] دیرتر به ۱ میرسه و ارتفاع هم طولانی ترین مسیره دیگه درسته؟
پس شاخه [tex]\frac{2n}{5}[/tex] همون ارتفاع میشه حالا میخوایم ارتفاع رو حساب کنیم:
[tex]k=(\frac{2}{5})^kn=1\rightarrow n=(\frac{5}{2})^k\rightarrow k=\lg^n_{\frac{5}{2}}[/tex]
که این [tex]k[/tex] همون ارتفاع درخته.یه توضیح درباره فرمول بالا هر چند حتما خودت بلدی ولی خب برای تمرین خودمه
فرض کردیم که [tex]k[/tex] ارتفاع درخته و باید برابر [tex](\frac{2}{5})^kn=1[/tex] شه.حالا چرا ۱؟چون درخت رو تا زمانی میشکنیم که به ۱ میرسیم دیگه درسته؟
پس ارتفاع هم اینجوری به دست میاد.بقیشم که دیگه یه سری هندسیه
(۲۶ مرداد ۱۳۹۳ ۱۲:۵۲ ق.ظ)miladcr7 نوشته شده توسط: سلام. دوستمون بالا برات کامل توضیح رو نوشته.حالا منم یه توضیحی میدم:
رابطمون اینه:[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
طبق قضیه میدونیم که توی این روابط:[tex]T(n)=T(\alpha n) T(\beta n) n[/tex]
اگه این شرط رو داشته باشیم:[tex]\alpha \beta<1[/tex] جواب برابر [tex]\theta(n)[/tex] میشه حالا برای ارتفاع:
یه بار دیگه رابطه رو داشته باش:[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
خب هر بار درخت ما به [tex]\frac{2n}{5}[/tex] و [tex]\frac{3n}{10}[/tex] شکسته میشه و اگه دقت کنی شاخه [tex]\frac{3n}{10}[/tex] سریع تر به ۱ میرسه(همون طور که میدونی ما درخت رو تا زمانی که به ۱ میرسیم میشکنیم) و شاخه [tex]\frac{2n}{5}[/tex] دیرتر به ۱ میرسه و ارتفاع هم طولانی ترین مسیره دیگه درسته؟
پس شاخه [tex]\frac{2n}{5}[/tex] همون ارتفاع میشه حالا میخوایم ارتفاع رو حساب کنیم:
[tex]k=(\frac{2}{5})^kn=1\rightarrow n=(\frac{5}{2})^k\rightarrow k=\lg^n_{\frac{5}{2}}[/tex]
که این [tex]k[/tex] همون ارتفاع درخته.یه توضیح درباره فرمول بالا هر چند حتما خودت بلدی ولی خب برای تمرین خودمه
فرض کردیم که [tex]k[/tex] ارتفاع درخته و باید برابر [tex](\frac{2}{5})^kn=1[/tex] شه.حالا چرا ۱؟چون درخت رو تا زمانی میشکنیم که به ۱ میرسیم دیگه درسته؟
پس ارتفاع هم اینجوری به دست میاد.بقیشم که دیگه یه سری هندسیه
از لطفتون ممنونم خیلی خوب توضیح دادید
(۲۶ مرداد ۱۳۹۳ ۱۲:۰۸ ق.ظ)ADELZX نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۵۶ ب.ظ)shayesteb نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط: سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش
ممنون از پاسختون. میشه بگید ارتفاع درخت را چطوری محاسبه کردید؟
مجموع هزینه های هر سطح درخت رو که جمع بزنی به سری زیر میرسی که خب جواب واضحه
[tex]\sum_{i=1}^{\log n}(\frac{7}{10})^in=\theta(n)[/tex]
خیلی ممنون
خواهش میکنم
سلام. وقت بخیر. سطر اول یعنی ریشه فقط یه nlgn داریم. توی سطر دو ۵ تا[tex]\frac{\frac{n}{5}}{\lg(\frac{n}{5^2})}[/tex]داریم. توی سطر سوم هم ۲۵ تا[tex]\frac{\frac{n}{5}}{\lg(\frac{n}{5^2})}[/tex]. با توجه به اینکه داریم lg(m/n)=lgm−lgn میشه حاصل تمام مقادیر درخت رو به این شکل نوشت:
[tex]\frac{n}{\lg n} 5\ast\frac{\frac{n}{5}}{\lg(\frac{n}{5})} ....=n(1 \frac{1}{\lg n} \frac{1}{\lg n-\lg5} \frac{1}{\lg n-2\lg5} ... \frac{1}{\lg n-klg5})[/tex] به نظرم از مرتبه nlglgn میشه.