تالار گفتمان مانشت
حل رابطه بازگشتی - نسخه‌ی قابل چاپ

حل رابطه بازگشتی - ahmadnouri - 21 مهر ۱۳۹۰ ۱۱:۳۴ ب.ظ

دوستان در حل روابط زیر لطفا کمک کنین
[tex]T(n)=T(n-1) lgn[/tex]
[tex]T(n)=T(n-2) 2lgn[/tex]

RE: حل رابطه بازگشتی - mfXpert - 22 مهر ۱۳۹۰ ۱۲:۲۳ ق.ظ

اولیش با یه نگاه حل میشه! از مرتبه بیگ اوی nlgn هستش.
از روش جایگذاری داریم:
[tex]T(n)=lg(n) lg(n-1) lg(n-2) ... lg(1)=lg(n*(n-1)*(n-2)*...*1)=lg(n!)[/tex]
و میدونیم که تابع [tex]lg(n!)[/tex] از مرتبه [tex]nlgn[/tex] هستش.پس مرتبه تابع برابر هست با تتای nlgn

دومی هم حلش نباید خیلی سخت باشه.اما الان حال حل کردنش رو ندارم

RE: حل رابطه بازگشتی - deledivouneh - 22 مهر ۱۳۹۰ ۱۲:۳۵ ق.ظ

یه نکته تو کتاب پوران پژوهش هست که گفته
T(n)=T(n-a)+a lgn
هر رابطه به این شکل عبارت است از:
T(n)=nlgn

RE: حل رابطه بازگشتی - deledivouneh - 25 مهر ۱۳۹۰ ۰۱:۲۱ ب.ظ

ابتدا طرفین رو بر n تقسیم میکنیم.چون اگه همینطوری بخوای ساده کنی میبینی که بعدا به مشکل میخوری.
حالا پس داریم:

RE: حل رابطه بازگشتی - ahmadnouri - 26 مهر ۱۳۹۰ ۱۲:۵۱ ق.ظ

ببخشید اگه من جواب میدم

بجای [tex]\frac{T(n)}{n}=f(m)[/tex]
بنابرای میشه نوشت [tex]\frac{T(\sqrt{n})}{\sqrt{n}}=\frac{T(n^{\frac{1}{2}})}{n^{\frac{1}{2}}} =f(\frac{m}{2})[/tex]