۰
subtitle
ارسال: #۱
رابطه بازگشتی
سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
۳
ارسال: #۲
RE: رابطه بازگشتی
سلام. دوستمون بالا برات کامل توضیح رو نوشته.حالا منم یه توضیحی میدم:
رابطمون اینه:[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] شه.حالا چرا ۱؟چون درخت رو تا زمانی میشکنیم که به ۱ میرسیم دیگه درسته؟
پس ارتفاع هم اینجوری به دست میاد.بقیشم که دیگه یه سری هندسیه
رابطمون اینه:[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] شه.حالا چرا ۱؟چون درخت رو تا زمانی میشکنیم که به ۱ میرسیم دیگه درسته؟
پس ارتفاع هم اینجوری به دست میاد.بقیشم که دیگه یه سری هندسیه
ارسال: #۳
RE: رابطه بازگشتی
(۲۶ مرداد ۱۳۹۳ ۱۲:۵۲ ق.ظ)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]
خیلی ممنون
۰
ارسال: #۴
RE: رابطه بازگشتی
ارسال: #۵
RE: رابطه بازگشتی
(۲۵ مرداد ۱۳۹۳ ۱۰:۵۲ ب.ظ)ADELZX نوشته شده توسط:(25 مرداد ۱۳۹۳ ۱۰:۲۶ ب.ظ)shayesteb نوشته شده توسط: سلام دوستان
میشه این رابطه بازگشتی را حل کنید.
[tex]T(n)=T(\frac{2n}{5}) T(\frac{3n}{10}) n[/tex]
ممنون میشم
ارتفاع درخت که معادل یه سری میشه پس همون cn میشه کل رابطه در نهایت تتای n هستش
ممنون از پاسختون. میشه بگید ارتفاع درخت را چطوری محاسبه کردید؟
ارسال: #۶
RE: رابطه بازگشتی
(۲۵ مرداد ۱۳۹۳ ۱۰:۵۶ ب.ظ)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]
۰
۰
ارسال: #۸
RE: رابطه بازگشتی
سلام. وقت بخیر. سطر اول یعنی ریشه فقط یه 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 میشه.
[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 میشه.
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| نظر در رابطه با استاد داور | علیصا | ۰ | ۱,۷۴۴ |
۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا |
|
| درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) | Saman | ۶ | ۷,۴۹۲ |
۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ آخرین ارسال: saeed_vahidi |
|
| رابطه n~1 | Mr.R3ZA | ۰ | ۱,۹۸۳ |
۲۰ خرداد ۱۳۹۷ ۰۱:۳۵ ق.ظ آخرین ارسال: Mr.R3ZA |
|
| توصیه های مهم در رابطه با انتخاب رشته (مهم) | Happiness.72 | ۰ | ۲,۱۵۱ |
۱۹ خرداد ۱۳۹۷ ۱۲:۳۶ ق.ظ آخرین ارسال: Happiness.72 |
|
| رابطه چند به یک | somayeh afsh | ۰ | ۱,۷۳۹ |
۰۷ خرداد ۱۳۹۷ ۱۲:۲۸ ب.ظ آخرین ارسال: somayeh afsh |
|
| رسم درخت بازگشتی برای t(n)=9t(n/3)+n | jumper | ۶ | ۶,۶۹۸ |
۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ آخرین ارسال: jumper |
|
| حل رابطه جایگذاری با تکرار | rahkaransg | ۱ | ۲,۳۳۱ |
۱۷ دى ۱۳۹۶ ۱۱:۲۹ ق.ظ آخرین ارسال: rahkaransg |
|
| حل روابط بازگشتی درجه ۳ | rahkaransg | ۲ | ۳,۰۹۴ |
۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ آخرین ارسال: rahkaransg |
|
| جواب رابطه های بازگشتی | rahkaransg | ۰ | ۱,۸۴۹ |
۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ آخرین ارسال: rahkaransg |
|
| تقسیم در جبر رابطه ای | Ella | ۱ | ۲,۲۸۹ |
۲۸ آذر ۱۳۹۶ ۱۲:۰۰ ق.ظ آخرین ارسال: Ella |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close