تالار گفتمان مانشت
حل سوال ۱ دکتری ۹۶ ( رابطه بازگشتی ) - نسخه‌ی قابل چاپ

حل سوال ۱ دکتری ۹۶ ( رابطه بازگشتی ) - arash691 - 07 اسفند ۱۳۹۵ ۰۹:۱۰ ب.ظ

[tex]T(n)=T(\sqrt{n})+\log n\: \: \longrightarrow \: n=2^m\: \: \: \: T(2^m)\: =\: T(2^{\frac{m}{2}})+m\: \: \: \longrightarrow\: \: \: S(m)=T(2^m)\: \: \: \longrightarrow\: S(m)=S(\frac{m}{2})+m\: \: \: S(m)=\theta(m)\: \: then\: T(n)=\theta(\log n)[/tex]