21 مهر 1390, 11:34 ب.ظ
22 مهر 1390, 12:23 ق.ظ
اولیش با یه نگاه حل میشه! از مرتبه بیگ اوی 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
دومی هم حلش نباید خیلی سخت باشه.اما الان حال حل کردنش رو ندارم
از روش جایگذاری داریم:
[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
دومی هم حلش نباید خیلی سخت باشه.اما الان حال حل کردنش رو ندارم
22 مهر 1390, 12:35 ق.ظ
یه نکته تو کتاب پوران پژوهش هست که گفته
T(n)=T(n-a)+a lgn
هر رابطه به این شکل عبارت است از:
T(n)=nlgn
T(n)=T(n-a)+a lgn
هر رابطه به این شکل عبارت است از:
T(n)=nlgn
25 مهر 1390, 01:21 ب.ظ
ابتدا طرفین رو بر n تقسیم میکنیم.چون اگه همینطوری بخوای ساده کنی میبینی که بعدا به مشکل میخوری.
حالا پس داریم:
حالا پس داریم:
26 مهر 1390, 12:51 ق.ظ
ببخشید اگه من جواب میدم
بجای [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]
بجای [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]