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

[Afshin_Zavar]

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

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 میشه ۰،
سوال اصلاً چی میخواد ، حساب کردنه این روابط و یا زمان بازگشتی الگریتمها بر اساس این روابط داده شده باشه ؟

[Afshin_Zavar]

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

[mohandese_hiclass]

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