پیچیدگی زمانی چند تابع

[nabavi1387]

سلام دوستان خسته نباشید :

من کتاب طراحی الگوریتم پیام نور تالیف آقای فراهی را مطالعه نمودم و توی تمرین هاش چهار تا تمرین دیدم که متاسفانه نتونستم حلشون کنم می خواستم ببینم کسی می تونه حل کنه من یاد بگیرم؟؟؟

------------------------------------------
7t(n-1)+4t(n-2)
t(0) = 0
t(1) = 2
------------------------------------------
if n=4 1
if n>4 t(sqrt(n))
------------------------------------------
if n=2 d
if n>2 5t(n/2)+n^2


و سوال زیر را نوشته به روش استقرا اما من خودم به نتیجه نرسیدم

if n=1 0
if n=2 1
if n>2 2t(n/2)+2


لطفاً راهنمایی کنید با تشکر :چشمک:

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

سه تای اول که با روش‌های ریشه‌یابی حل روابط بازگشتی قابل حل هستن. دنباله اول چیزی شبیه دنباله فیبوناچی با ضرایب متفاوت هستش. راحت حل می‌شه. دومی تغییر متغیر می‌خواد و سومی هم از دو قسمت حل همگن و ناهمگن تشکیل شده.

رابطه آخر هم اشتباهه. اگه به ازای یک بشه صفر، به ازای دو می‌شه دو، و نه یک. البته دلیلی نداره دو رابطه اولیه داده بشه. وقتی به یه جمله قبلی وابسته هستش فقط یه جمله اولیه یا هر چند جمله اولیه سازگار با جمله اول داده می‌شه. این دو جمله سازگار نیستن.