مرتبه اجرایی الگوریتمهای بازگشتی؛ دکتر نقیب زاده

[Developer Programmer]

نمی دونم کتاب طراحی الگوریتم های دکتر نقیب زاده (ویرایش اول) رو مطالعه کردید یانه ؛
یکسری روشهایی واسه حل الگوریتمهای بازگشتی ارائه کرده که به نظر حقیر ، در بعضی مواقع به بزرگتر و گنگتر شدن مسائل دامن می زنه!
در حین مطالعه کتاب، به مشکلاتی برخوردم .از دوستان اگه میتونن لطف کنن و تعداد اجرای الگوریتمهای زیر رو محاسبه کنن ...

1. رابطه بازگشتی متجانس مرتبه اول

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

t(0)=0

2.رابطه بازگشتی غیر متجانس مرتبه اول

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

t(0)=0

3. رابطه بازگشتی متجانس مرتبه دوم

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

t(0)=0, t(1)=1

4. رابطه بازگشتی متجانس مرتبه دوم

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

t(1)=1

5.

t(n)=t(n/2)

t(0)=1

6.

t(n)=t(sqrt(t,2))+c

t(4)=1

[اَرژنگ]

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

1. رابطه بازگشتی متجانس مرتبه اول

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

t(0)=0

2.

نگران نباش، این سوال ما را هم گیج میکنه، مثلان شماره یک را میشه ۲ نوع جواب داد.
۱) لُگ(n)
۲) ۱
ولی اینها الگریتم نیستند، روابط بازگشتی هسند و حساب کردن روابط بازگشتی با زمان الگریتمیشان فرق دارد،
مثلاً بالایی برایه تمامه n میشه ۰،
سوال اصلاً چی میخواد ، حساب کردنه این روابط و یا زمان بازگشتی الگریتمها بر اساس این روابط داده شده باشه ؟

[Developer Programmer]

سلام ممنون از وقتی که گذاشتید
هدف، حل روابط بازگشتی است؛ همان Big O و Teta و ...

[mohandese_hiclass]

تو مبحث پیدا کردن پیچیدگی الگوریتمها چون روشها زیادند به روش تکیه نکنید ببنید جوابی که شما اوردید با اون جواب یکی هر چند که روشتون فرق کنه