با سلام.
مرتبه زمانی این تابع چنده؟
کد:
int F(N)
{
if (N<3) return 1;
return F (n-3) - F (n-2) + F (n-1);
}بدلیل اینکه الگوریتم بازگشتی تابع در صورت سوال عنوان شده است در ابتدا باید رابطه‌ی بازگشتی تابع را بنویسیم که خواهیم داشت:
[tex]T(n)= T(n-3) T(n-2) T(n-1) 1[/tex]
که از راه تقریب می توان گفت که مرتبه‌ی آن نمایی خواهد شد.حدودا [tex]O(3^n)[/tex]
اشتباهی که بسیار رایج نیز می باشد این است که بنویسید:
[tex]T(n)= T(n-3) - T(n-2) T(n-1)[/tex]
بعد معادله مشخصه رو بنویسید.ریشه‌ها برابرند با -۱ و ۱ که -۱ ریشه مضاعف میباشد.در نتیجه بگویید مرتبه‌ی تابع میشه [tex]O(n)[/tex].
(۲۴ دى ۱۳۸۹ ۰۱:۳۱ ق.ظ)حامد نوشته شده توسط: که از راه تقریب می توان گفت که مرتبه‌ی آن نمایی خواهد شدمنظورتون ا این چمله ای که فرمودین چه روشی هستش؟لطف میکنید توضیحش بدین؟
(۲۴ دى ۱۳۸۹ ۱۲:۰۵ ب.ظ)sos006 نوشته شده توسط:میدانیم که:(24 دى ۱۳۸۹ ۰۱:۳۱ ق.ظ)حامد نوشته شده توسط: که از راه تقریب می توان گفت که مرتبه‌ی آن نمایی خواهد شدمنظورتون ا این چمله ای که فرمودین چه روشی هستش؟لطف میکنید توضیحش بدین؟
[tex]T(n-2)\leq T(n-1)[/tex]
[tex]T(n-3)\leq T(n-1)[/tex]
پس:
[tex]T(n)\leq T(n-1) T(n-1) T(n-1) 1\leq3T(n-1) 1[/tex]
بصورت بازگشتی که جایگذاری کنید خواهید داشت:
[tex]T(n)\leq 3^n \Rightarrow T(n)=O(3^n)[/tex]