سلام خسته نباشید.این سوال توی کتاب ۶۰۰ مسئله دکتر قدسیه.زمان اجراشو خواسته
اینم تابع:[tex]T(n)=T(\frac{n}{3}) T(\frac{n}{6}) n^{\sqrt{\lg n}}[/tex]
توی حلشون هم گفتن چون [tex]T(\frac{n}{6})<=T(\frac{n}{3})[/tex] پس داریم:[tex]T(\frac{n}{6}) T(\frac{n}{3})=2T(\frac{n}{3})[/tex] و از قضیه اصلی حل کردند.میخواستن ببینم این کاری که انجام دادند([tex]T(\frac{n}{6}) T(\frac{n}{3})=2T(\frac{n}{3})[/tex]) میشه همیشه انجام داد یا توی این مثال خاص اینجور بوده؟
اگر شما اون بخش آخر تایع رو تایع f در نظر بگیرید اون وقت طبق همون نکته ای که از مسئله های ۶۰۰میتونیم استخراج کنیم میشه گفت که چون [tex]T(\frac{n}{3}) T(\frac{n}{6})[/tex] پس جمع دو کسر [tex]\frac{3n}{6}[/tex] هست به این دلیل که جمع دوتا شون به [tex]T(n)[/tex] نرسیده پس زمان اجرای این تابع بازگشتی میشه تابع f که اومده!
چون اینجا کران بالا رو میخواد، اینا اومدن اینکارو کردن
حالا به طور کلی چه وقت هایی مجازیم این کار رو انجام بدیم؟