دوستان در حل روابط زیر لطفا کمک کنین
[tex]T(n)=T(n-1) lgn[/tex]
[tex]T(n)=T(n-2) 2lgn[/tex]
اولیش با یه نگاه حل میشه! از مرتبه بیگ اوی 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
دومی هم حلش نباید خیلی سخت باشه.اما الان حال حل کردنش رو ندارم
یه نکته تو کتاب پوران پژوهش هست که گفته
T(n)=T(n-a)+a lgn
هر رابطه به این شکل عبارت است از:
T(n)=nlgn
ابتدا طرفین رو بر n تقسیم میکنیم.چون اگه همینطوری بخوای ساده کنی میبینی که بعدا به مشکل میخوری.
حالا پس داریم:
ببخشید اگه من جواب میدم
بجای [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]