۰
subtitle
ارسال: #۱
  
مرتبه تابع بازگشتی - آزمون جامع دوم پارسه
کسی یک راه آسون و سریع برای پیدا کردن مرتبه این رابطه بازگشتی سراغ نداره؟؟
[tex]T(n)=\frac{n}{n 1}T(n-1) \: n^2[/tex]
[tex]T(n)=\frac{n}{n 1}T(n-1) \: n^2[/tex]
۴
ارسال: #۲
  
RE: مرتبه تابع بازگشتی - آزمون جامع دوم پارسه
من یه تحلیل مینویسم. امیدوارم درست باشه
اگه نگاه کنید متوجه میشید که اندازه ورودی هر دفعه داره یکی کم میشه(n میشه n-1 ).پس واسه اینکه به شرایط اولیه، یعنی ورودی یک برسیم، باید n بار این رابطه رو تکرار کنیم. هزینه هر بار هم که n^2 می باشد. پس در کل میشه n^3
البته اون n تقسیم بر n+1 هم که میشه یک تقریبا. پس تاثیری نداره
اگه خیلی مختصر بود بگین تا با جزئیات بیشتری توضیح بدم
اگه نگاه کنید متوجه میشید که اندازه ورودی هر دفعه داره یکی کم میشه(n میشه n-1 ).پس واسه اینکه به شرایط اولیه، یعنی ورودی یک برسیم، باید n بار این رابطه رو تکرار کنیم. هزینه هر بار هم که n^2 می باشد. پس در کل میشه n^3
البته اون n تقسیم بر n+1 هم که میشه یک تقریبا. پس تاثیری نداره
اگه خیلی مختصر بود بگین تا با جزئیات بیشتری توضیح بدم
۰
ارسال: #۳
  
RE: مرتبه تابع بازگشتی - آزمون جامع دوم پارسه
سلام.اگه ممکنه گزینه ها رو هم بذارید
۰
ارسال: #۴
  
RE: مرتبه تابع بازگشتی - آزمون جامع دوم پارسه
کافیه طرفین وسطین بکنید و یک تبدیل تابعی انجام بدهید خیلی راحت درمیاد
[tex](n ^{ }1)T_n\: =\: n\: T_{n-1}\: \: n^2(n 1)\: ,\: \: \: \: \: \: \: \: \: \: \: \: \: F_n=(n 1)T_n[/tex]
مرتبه تابع جدید رو حساب کنید، مرتبه تابع اولیه میشه مرتبه تابع جدید تقسیم بر n
[tex](n ^{ }1)T_n\: =\: n\: T_{n-1}\: \: n^2(n 1)\: ,\: \: \: \: \: \: \: \: \: \: \: \: \: F_n=(n 1)T_n[/tex]
مرتبه تابع جدید رو حساب کنید، مرتبه تابع اولیه میشه مرتبه تابع جدید تقسیم بر n
۰
ارسال: #۵
  
RE: مرتبه تابع بازگشتی - آزمون جامع دوم پارسه
این یک رابطه بازگشتیه ناهمگنه که در اون [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] هستش
[tex](r-1)(r-1)^3[/tex]
این معادله یک ریشه[tex]r=1[/tex] داره
چون معادله بالا درجه ۴ هستش و ۱ ریشه داره فرمول کلی تابع داده شده در سوال میشه
[tex]c cn cn^2 cn^3[/tex]
که از مرتبه [tex]n^3[/tex] هستش
۰
ارسال: #۶
  
RE: مرتبه تابع بازگشتی - آزمون جامع دوم پارسه
طرفین رو در n+1 ضرب کن و بعد تغییر متغیر بده
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close