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

ارتفاع درخت بازگشت

ارسال:
  

majid10 پرسیده:

ارتفاع درخت بازگشت

سلاااااااام بر همه علم پژوهان مانشتی ...
سوالی که اینبار در ذهن مبارکم متولد شده اینه که در درخت بازگشتی زیر
[تصویر:  424809_c0cd2c430c3554a2a4a36348a93072d8.jpg]
ارتفاع درخت چرا شده lg n ؟؟ و کلن نحوه بدست اوردن ارتفاع درخت چیجوریه؟؟ و توی همین سوال جواب (مجموع سطوح) رو چه طور بدست اورده؟
دمه همتون گرم ...

Sent from my Nexus 5 using Tapatalk
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Pure Liveliness پاسخ داده:

RE: ارتفاع درخت بازگشت

سلام.
ریشه ی درخت یعنی هزینه به ازای [tex]T(n)[/tex] برابر هست با [tex]\frac{n}{\log n}[/tex]
پس هزینه برای [tex]T(\frac{n}{2})[/tex] برابر میشه با [tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})}=\frac{\frac{n}{2}}{\log n-\log_22}=\frac{\frac{n}{2}}{\log n-1}[/tex]
هزینه به ازای [tex]T(\frac{n}{2^k})[/tex] برابر میشه با [tex]\frac{\frac{n}{2^K}}{\log(\frac{n}{2^K})}=\frac{\frac{n}{2^k}}{\log n-\log_22^K}=\frac{\frac{n}{2^k}}{\log n-k}[/tex]
کی میرسیم به ریشه ی درخت؟ وقتی به شرط های اولیه برسیم. اغلب [tex]T(۱)[/tex] یا [tex]T(۲)[/tex]
باید ببینیم این روال تقسیم n به ۲ کجا میرسه به ۲ یعنی [tex]T(\frac{n}{2^k})[/tex] کی برابر با [tex]T(2)[/tex] میشه؟
[tex]T(\frac{n}{2^k})=T(2)\: \: \longrightarrow\: (\frac{n}{2^k})=2\: \: \longrightarrow\: n=2^{k\: }\: \: \: \longrightarrow k=\log n-1[/tex]
چرا ۲؟ چون مخرج نباید ۰ باشه. اگه ۱ در نظر بگیریم مخرج ۰ میشه.
اینم یه مثال دیگه از محاسبه ی ارتفاع درخت :https://manesht.ir/forum/thread-33826.html

واسه به دست آوردن مجموع هزینه های سطوح
با توجه به بالا که :
هزینه به ازای [tex]T(n)[/tex] برابر هست با [tex]\frac{n}{\log n}[/tex]
هزینه برای [tex]T(\frac{n}{2})[/tex] برابر میشه با [tex]\frac{\frac{n}{2}}{\log(\frac{n}{2})}=\frac{\frac{n}{2}}{\log n-\log_22}=\frac{\frac{n}{2}}{\log n-1}[/tex]
هزینه برای [tex]T(\frac{n}{4})[/tex] برابر میشه با [tex]\frac{(\frac{n}{4})}{\log(\frac{n}{4})}=\frac{\frac{n}{4}}{\log n-\log4}=\frac{\frac{n}{4}}{\log n-1}[/tex]
هزینه به ازای [tex]T(\frac{n}{2^k})[/tex] برابر میشه با [tex]\frac{\frac{n}{2^K}}{\log(\frac{n}{2^K})}=\frac{\frac{n}{2^k}}{\log n-\log_22^K}=\frac{\frac{n}{2^k}}{\log n-k}[/tex]
جمع هزینه ی سطح دوم میشه: [tex]2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}[/tex]
جمع هزینه ی سطح سوم میشه: [tex]۴.\frac{\frac{n}{۴}}{\log(\frac{n}{۴})}[/tex]
.
.
جمع هزینه ی سطح kام میشه: [tex]۲^k.\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}[/tex]
جمع هزینه های کل سطوح:
[tex]\frac{n}{\log n}+2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}+4.\frac{\frac{n}{4}}{\log(\frac{n}{4}​)}+...+2^k\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}[/tex]
[tex]\frac{n}{\log n}+2.\frac{\frac{n}{2}}{\log(\frac{n}{2})}+4.\frac{\frac{n}{4}}{\log(\frac{n}{4}​)}+...+2^k\frac{\frac{n}{2^k}}{\log(\frac{n}{2^k})}=\frac{n}{\log n}+\frac{n}{\log n-1}+\frac{n}{\log n-2}+...+\frac{n}{\log2}[/tex]
چون [tex]2^k=n\: [/tex] هست جمع آخرین سطح به اون صورت شد. از طرفی مخرج نمیتونه ۰ باشه.
[tex]n\cdot(\frac{1}{\log n}+\frac{1}{\log n-1}+...+\frac{1}{1})=n.\sum^{\log n}_{i=1}\frac{1}{i}=n.\ln\log n[/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

majid10 پاسخ داده:

RE: ارتفاع درخت بازگشت

خیلی خیلی ممنون

Sent from my Nexus 5 using Tapatalk
نقل قول این ارسال در یک پاسخ



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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