سلام ممنون میشم بگین چه جوری روابط بازگشتی رو به روش تغییر متغییر میشه حل کرد.!!؟
به عنوان نمونه ..مثال صفحه ۳۵ یوسفی چاپ بهار ۹۴
سلام.
چون توی بعضی از روابط بازگشتی گاهی رادیکال داریم محاسبه ش سخت هست و با روش های معمولی نمیتونیم احتمالا حلش کنیم. باید یه کاری کنیم که از شر رادیکال خلاص بشیم.
این جا برای این که رادیکال رو از بین ببریم شاید پیشنهاد بشه که رادیکال رو به صورت توان [tex]\frac{1}{2}[/tex] بنویسیم. اما خب فرقی نداره و بعدش نمیشه هیچ کاری کرد. این جا ها که رادیکال داریم میشه ۲ به توان m گرفت n رو. اگه رادیکال تودرتو بود و اینا فرق داشت قضیه.
[tex]T(n)=3T(\sqrt[3]{n})+\log n[/tex]
حالا تغییر متغیر برای خلاص شدن از رادیکال: [tex]n=2^m\: \longrightarrow\: \log n=m[/tex]
[tex]T(2^m)=3T(\sqrt[3]{2^m})+\log2^m=3T(2^{\frac{m}{3}})+m[/tex]تغییر متغیر دوم برای تبدیل به رابطه ی بازگشتی غیر توانی : [tex]T(2^m)=S(m)[/tex]
[tex]S(m)=3S(\frac{m}{3})+m[/tex] که از مرتبه ی mlogm هست و چون [tex]\log n=m[/tex] پس میشه از مرتبه ی [tex]\log n\times\log\log n[/tex]
(۰۵ اسفند ۱۳۹۵ ۰۷:۱۵ ب.ظ)sara27 نوشته شده توسط: سلام ممنون میشم بگین چه جوری روابط بازگشتی رو به روش تغییر متغییر میشه حل کرد.!!؟
به عنوان نمونه ..مثال صفحه ۳۵ یوسفی چاپ بهار ۹۴
واسه تمرین بیشتر رابطه های زیر رو خودتون حل کنید :
[tex]T(n)=\: T(n^{\frac{1}{3}})+T(n^{\frac{2}{3}})+\log n[/tex]
[tex]T(n)=2T(\sqrt{n})+\frac{n}{\log n}[/tex]