کسی میتونه بگه چرا مرتبه زمانی این سوال از nlogn هست؟؟
[tex]T(n)\: =\: \frac{2}{n}\sum^{n-1}_{k=0^{ }}T(k)\: \: n[/tex]
واسه راهنمایی گفته شده که طرفین رو در n ضرب کنیم و سپس T(n-1) رو پیدا کرده و از T(n) کم کنیم ولی من با این راه به جواب n میرسم!!!
راه حلم توی ضمیمه هست. البته آخرش رو شانسی گفتم میشه n
سلام.
فکر میکنم خط چهارم راه حلتون درست نیست. به علاوه اینکه توجه کنید حتی اگر به همین جواب آخر هم می‌رسیدید، مرتبه‌ی جواب از n نمیشد و از مرتبه‌ی [tex]O(n^2)[/tex] میشد.
فکر میکنم راه حل سؤال به این شکل هست:
[tex]nT(n)=2\sum_{k=0}^{n-1}T(k) n[/tex]
[tex](n-1)T(n-1)=2\sum_{k=0}^{n-2}T(k) n-1[/tex]
[tex]nT(n)-(n-1)T(n-1)=2T(n-1) 1[/tex]
[tex]nT(n)=(n 1)T(n-1) 1[/tex]
[tex]T(n)=\frac{n 1}{n}T(n-1) \frac{1}{n}[/tex]
بعد از این برای پیدا کردن مرتبه، میشه از جایگذاری مکرر کمک گرفت:
[tex]T(n)=\frac{n 1}{n}(\frac{n}{n-1}(\frac{n-1}{n-2}...(\frac{n-n 2}{n-n 1})) \frac{1}{n})[/tex]
همانطور که می‌بینید، در این ضرب‌های مکرر، صورت و مخرج‌های پی‌درپی با هم ساده میشن، در نهایت فکر میکنم چیزی که می‌مونه اینطور میشه:
[tex]2(n 1)logn \in O(nlogn)[/tex]
چون [tex]\frac{1}{n}[/tex] در نهایت مرتبه‌ی logn داره و در جایگذاری مکرر هم دیدیم که یک مرتبه‌ی در logn ضرب خواهد شد.