ارتفاع درخت بازگشت - نسخه‌ی قابل چاپ

ارتفاع درخت بازگشت - majid10 - 05 آبان ۱۳۹۵ ۰۶:۱۴ ب.ظ سلاااااااام بر همه علم پژوهان مانشتی ... سوالی که اینبار در ذهن مبارکم متولد شده اینه که در درخت بازگشتی زیر ارتفاع درخت چرا شده lg n ؟؟ و کلن نحوه بدست اوردن ارتفاع درخت چیجوریه؟؟ و توی همین سوال جواب (مجموع سطوح) رو چه طور بدست اورده؟ دمه همتون گرم ... Sent from my Nexus 5 using Tapatalk

RE: ارتفاع درخت بازگشت - Pure Liveliness - 05 آبان ۱۳۹۵ ۰۶:۴۵ ب.ظ سلام. ریشه ی درخت یعنی هزینه به ازای [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]

RE: ارتفاع درخت بازگشت - majid10 - 06 آبان ۱۳۹۵ ۰۶:۲۶ ب.ظ خیلی خیلی ممنون [PERSON WITH FOLDED HANDS][PERSON WITH FOLDED HANDS] Sent from my Nexus 5 using Tapatalk