زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۵:۳۰ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

رسم درخت بازگشتی برای t(n)=9t(n/3)+n

ارسال:
  

jumper پرسیده:

رسم درخت بازگشتی برای t(n)=9t(n/3)+n

سلام
چطور جواب رابطه بازگشتی زیر با استفاده از رسم درخت بازگشتی بدست بیارم؟ از قضیه اصلی نمیخوام استفاده کنم.
t(n)=9t(n/3)+n
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

msour44 پاسخ داده:

RE: رسم درخت بازگشتی برای t(n)=9t(n/3)+n

سلام
در سطح صفر(سطح ریشه) درخت بازگشت هزینه برابر 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 پاسخ داده:

RE: رسم درخت بازگشتی برای t(n)=9t(n/3)+n

(۱۵ دى ۱۳۹۶ ۰۵:۳۴ ب.ظ)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]

خیلیییی ممنون
حالا برای [tex]t(n)=t(\frac{n}{2})t(\frac{2n}{3})n[/tex] هزینه ی سطح 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})=?[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

msour44 پاسخ داده:

RE: رسم درخت بازگشتی برای t(n)=9t(n/3)+n

(۱۶ دى ۱۳۹۶ ۱۲:۵۷ ب.ظ)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 پاسخ داده:

RE: رسم درخت بازگشتی برای t(n)=9t(n/3)+n

(۱۷ دى ۱۳۹۶ ۰۱:۳۱ ق.ظ)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] در نظر می گیریم همان که شما رابطه ی ان را نوشتید. به نظر میاد در پیدا کردن مرتبه برای این رابطه نیاز به محا سبات لگاریتمی داریم .حالا باز شما رابطه تصحیح بفرماید یا بهتر این رابطه را به صورت سوال جداگانه مطرح کنید تا توسط دوستان پاسخ داده شود.

رابطه اصلاح شد من در همان قسمت محاسبات لگاریتمیش مشکل دارم جواب نهایی میشه [tex]nlog_{\frac{3}{2}}n[/tex] یا همان [tex]nlogn[/tex]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

msour44 پاسخ داده:

RE: رسم درخت بازگشتی برای t(n)=9t(n/3)+n

(۱۷ دى ۱۳۹۶ ۰۹:۰۴ ق.ظ)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] داشته باشیم وگرنه مرتبه همان طور که تقریبی نوشتم بیشتر می شود.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

jumper پاسخ داده:

RE: رسم درخت بازگشتی برای t(n)=9t(n/3)+n

(۱۷ دى ۱۳۹۶ ۰۵:۱۳ ب.ظ)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] داشته باشیم وگرنه مرتبه همان طور که تقریبی نوشتم بیشتر می شود.

ممنون از وقتی که گذاشتین من سوالمو طبق این لینک
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
پرسیدم. اونجا گفته بود [tex]nlogn[/tex] به هر حال متشکرم
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۸ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۱ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۰,۹۶۲ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۱ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
Question درخواست کمک و راهنمایی در ns2 r.jafari ۳ ۳,۶۳۴ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۳۷ ب.ظ
آخرین ارسال: mohsentafresh
  رسم مدار انکدر ۴ به ۲ moslemrahmati ۰ ۱,۶۵۳ ۲۶ اسفند ۱۳۹۸ ۰۲:۰۷ ب.ظ
آخرین ارسال: moslemrahmati
  تعداد درخت فراگیر ss311 ۰ ۲,۰۵۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close