سلام بچه ها
کسی میتونه کمک کنه بتونم این جور مسائلو بفهمم؟؟
کدام یک از عبارات زیر جواب رابطه ی بازگشتی
[tex]T(n)\leq T(n/5) T(7n/10) n[/tex]
جواب میشه
[tex]T(n)\leq \sum_{i=0}^{\log n,10/7}\(9/10)^{i}n[/tex]
از روش درخت برای حل رابطه استفاده کن.
درخت این رابطه حالت متعادلی رو داره، در هر سطح جمع عناصر براِ i^(9/10 هست و بیشترین ارتفاع برابر با longn 10/7 است.
موفق باشی.
اول ۱/۵+۷/۱۰ رو جمع میزنی میشه : ۹/۱۰
حالا ازش لگاریتم می گیری و به توان i میرسونی و همرو جمع میزنی و نهایتا در n ضرب می کنی(همونجا هم در n ضرب کنی فرقی نداره چون n ثابت هست و در نهایت با یه فاکتور گیری بازم جمع همه باید در n ضرب بشه)
i باید مقدایر ۰ و۱ و ... و لگاریتم n در مبنای base رو بگیره.
base رو چطوری بدست میاریم ؟
ابتدا n/5 رو با ۷n/10 مقایسه می کنیم.
مخرج کوچکتر رو باید به عنوان مبنای لگاریتم در نظر بگیریم :
[tex]\frac{n}{5}<\frac{7n}{10}, \frac{2n}{10}<\frac{7n}{10},\frac{n}{10/2}<\frac{n}{10/7}\Rightarrow \frac{10}{7}<\frac{10}{2}\Rightarrow base=\frac{10}{7}[/tex]
----------
اینجور روابط ها رو باید یاد گرفت اما توی وقت کم زیاد روشون فکر نکن قاعده ی کلی رو حفظ کن چون وقت کمه.