حل یک رابطه

[life24]

با درود
عزیزان این رابطه که ظاهرا بازگشتی هست چطور حل شده؟ خط اول از1 +3 صرف نظر میکنیم به دلایلی.

[Maximus]

داداش این که اسونه کجاش مشکل داری

[Maximus]

http://8pic.ir/images/4oas9ebhahx9zfhg6jrm.jpg

[life24]

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

[Phenotype_2]

این روابط عجیب غریب چیه دارین مینویسین؟
t که فقط روی توانهای 2 تعریف شده.
عجب! اون جیزهایی که بینشون مساوی گزاشتی واقعن مساوین؟

[Maximus]

اسم این روش تکرار با جایگذاری هست
اینقدر جایگذاری می کنیم تا به تی یک برسیم اما رسیدن به تی یک خیلی وقت گیر هست پس به دنبال الگو میگردیم پس از پیدا کردن الگو
بجای تی ان ، تی یک جایگذاری میکنیم و بدست میاریم

[life24]

جسارتا مشکل اینجاست من اون 2 قسمت که فلش زدم و دقیقا بحث جایگذاری هست رو نمیفهمم چطور جایگذاری کرده!!!!!! (باعث خجالت )

[Phenotype_2]

جسارتا مشکل اینجاست من اون 2 قسمت که فلش زدم و دقیقا بحث جایگذاری هست رو نمیفهمم چطور جایگذاری کرده!!!!!! (باعث خجالت )

T (n) =2T (n/2) + n
سوال اینه؟ اصلا متوجه نمیشم چی نوشتین. ولی اگه سوال اینه خودم حلش میکنم واستون.
به ترییب توانهای دو رو حانشین n میکنیم.
T(2) = 2T (1) + 2
T(4) = 2T (2) + 4 = 2²T (1) + 2³
T(8) =2T (4) + 8 = 2³T (1) +2⁴
T(16) = 2T (8) + 16 = 2⁴T (8) + 2⁵

میشه حدس زد برای هر N نا منفی ناکوچکتر از 1 دا یم:
T (2 ^ n) = 2 ^ n + 2 ^ n+1
این حدس رو با استقرا میشه ثابت کرد. ولی نمیتونید اون لگاریتمها رو بنویسید.

[Maximus]

http://8pic.ir/images/d8p3iye16720qrmwmc1r.jpg

[life24]

عالی بود. مشکلم حل شد.