جواب این رابطه تقسیم و غلبه چطوری به دست میاد؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
[tex]T(n)=2T(\sqrt{n}) \log_2n[/tex]
ابتدا تغییر متغیر انجام می دهیم به صورت زیر
[tex]n=2^{k}[/tex]
خواهیم داشت
[tex]T(2^{k})=2T(2^{k/2}) \log_22^{k}[/tex]
رابطه بالا می شود :
[tex]T(2^{k})=2T(2^{k/2}) k[/tex]
برای زیبایی اینگونه تغییر می دهیم :
[tex]g(k)=2g(k/2) k[/tex]
خواهیم داشت :
[tex]g(k)=\theta((k)(\lg k))[/tex]
حال بر حسب n به صورت زیر می شود :
[tex]T(n)=\theta((\lg n)(\lg\lg n))[/tex]