کسی یک راه آسون و سریع برای پیدا کردن مرتبه این رابطه بازگشتی سراغ نداره؟؟
[tex]T(n)=\frac{n}{n 1}T(n-1) \: n^2[/tex]
سلام.اگه ممکنه گزینه ها رو هم بذارید
من یه تحلیل مینویسم. امیدوارم درست باشه
اگه نگاه کنید متوجه میشید که اندازه ورودی هر دفعه داره یکی کم میشه(n میشه n-1 ).پس واسه اینکه به شرایط اولیه، یعنی ورودی یک برسیم، باید n بار این رابطه رو تکرار کنیم. هزینه هر بار هم که n^2 می باشد. پس در کل میشه n^3
البته اون n تقسیم بر n+1 هم که میشه یک تقریبا. پس تاثیری نداره
اگه خیلی مختصر بود بگین تا با جزئیات بیشتری توضیح بدم
کافیه طرفین وسطین بکنید و یک تبدیل تابعی انجام بدهید خیلی راحت درمیاد
[tex](n ^{ }1)T_n\: =\: n\: T_{n-1}\: \: n^2(n 1)\: ,\: \: \: \: \: \: \: \: \: \: \: \: \: F_n=(n 1)T_n[/tex]
مرتبه تابع جدید رو حساب کنید، مرتبه تابع اولیه میشه مرتبه تابع جدید تقسیم بر n
این یک رابطه بازگشتیه ناهمگنه که در اون [tex]\frac{n}{n 1}[/tex] برابر ۱ میشه که خونده نمیشه و بر اساس فرمولی که برای این مدل رابطه که توی آخر کتاب نیپولتان یا توی مبحث روابط بازگشتیه درس ساختمان گسسته هستش با یک نگاه مشخص میشه که معادله مشخصه این رابطه به این شکل هست:
[tex](r-1)(r-1)^3[/tex]
این معادله یک ریشه[tex]r=1[/tex] داره
چون معادله بالا درجه ۴ هستش و ۱ ریشه داره فرمول کلی تابع داده شده در سوال میشه
[tex]c cn cn^2 cn^3[/tex]
که از مرتبه [tex]n^3[/tex] هستش
طرفین رو در n+1 ضرب کن و بعد تغییر متغیر بده