بدست اوردن مرتبه زمانی از ر روی تابع

[shecarchi]

سلام دوستان.
من تو بدست اوردن مرتبه زمانی از روی تابع مشکل دارم. یکی میگه از روش استقرا یکی میگه کشیدن درخت . مقسمی هم تو کتابش گفته تو رابطه بازگشتی جایگزین میکنیم.

یکی بیاد توضیح بده مثلا برای عبارت زیر چجوری مرتبه زمانی رو بدست بیاریم:

t(n)=2t(n-2)+1

[مسعود اقدسی فام]

سلام دوستان.
من تو بدست اوردن مرتبه زمانی از روی تابع مشکل دارم. یکی میگه از روش استقرا یکی میگه کشیدن درخت . مقسمی هم تو کتابش گفته تو رابطه بازگشتی جایگزین میکنیم.

یکی بیاد توضیح بده مثلا برای عبارت زیر چجوری مرتبه زمانی رو بدست بیاریم:

t(n)=2t(n-2)+1

هم به روش استقرایی می‌شه، و هم به روش حل روابط بازگشتی با استفاده از قضایای ریاضی. اگر لازم باشه هر دو رو توضیح بدم.

[shecarchi]

اگه میشه روش استقرایی رو توضیح بدین.

[Salar Ashgi]

ببینید دوست عزیز واسه پیدا کردن پیچیدگی زمانی (بازگشتی) عموما روش ثابت و یکتایی وجود ندارد و روشها زیاده : روش استقرا ، جایگزینی ، قضیه اصلی یا
همان Master Theorem و ... . که فقط با تمرین زیاد میتوان بر حلشان مسلط شد .

موفق باشید ./

[shecarchi]

این روش مستر چیه یه اموزش درموردش اگه دارین لطف کنین