مرسی مرسی.میشه اینو هم حل کنید؟؟
T(n)=2√nT(√n) + nlogn
(۰۵ دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)fatima2007 نوشته شده توسط: سلام شما اینو چطور حل میکنید؟
میشه مراحلش و جواب اخرشو بگذارید
۴T(∛n/5)+logn
سلام
چون رشد جذر از تقسیم بیشتره از تقسیم بر ۵ صرف نظر میکنیم و با تغییر متغییر [tex]n=3^{3^k}[/tex] داریم :
[tex]T(3^{3^k})=4T(3^{3^{k-1}}) log(3^{3^k})[/tex]
حال با تغییر تابع [tex]G(k)=T(3^{3^k})[/tex] داریم :
[tex]G(k)=4G(k-1) 3^k[/tex]
با حل این رابطه بازگشتی ناهمگن داریم : [tex]G(k)=4^K[/tex]
حال با تغییر تابع و تغییر متغییر به صورت برعکس داریم :
[tex]T(n)=4^{loglogn}[/tex]
سلام.
این سوال رو میتونیم به شکل قضیه اصلی تبدیل کنیم.
(۰۵ دى ۱۳۹۱ ۰۱:۳۴ ب.ظ)nazaninzahra2 نوشته شده توسط:سلام. میشه بگید چطور از ۴^k ، تونستین ۴^loglogn رو بدست بیارید!(05 دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)fatima2007 نوشته شده توسط: سلام شما اینو چطور حل میکنید؟
میشه مراحلش و جواب اخرشو بگذارید
۴T(∛n/5)+logn
سلام
چون رشد جذر از تقسیم بیشتره از تقسیم بر ۵ صرف نظر میکنیم و با تغییر متغییر [tex]n=3^{3^k}[/tex] داریم :
[tex]T(3^{3^k})=4T(3^{3^{k-1}}) log(3^{3^k})[/tex]
حال با تغییر تابع [tex]G(k)=T(3^{3^k})[/tex] داریم :
[tex]G(k)=4G(k-1) 3^k[/tex]
با حل این رابطه بازگشتی ناهمگن داریم : [tex]G(k)=4^K[/tex]
حال با تغییر تابع و تغییر متغییر به صورت برعکس داریم :
[tex]T(n)=4^{loglogn}[/tex]
سلام . اینم یه حل عمومی تر
[tex]{\color{Red} T(n)=4T(\frac{\sqrt[3]{n}}{5}) logn \Rightarrow}[/tex]
[tex]n=5^{m}[/tex]
[tex]T(5^{m})=4T(\frac{5^{\frac{m}{3}}}{5}) log5^{m}[/tex]
[tex]T(5^{m})=S(m)[/tex]
[tex] S(m)=4S(\frac{m}{3}-1) m\Rightarrow m^{\log_{3}4}\Rightarrow {\color{DarkBlue} (logn)^{\log_{3}4}}[/tex]
[tex]n=5^{m}[/tex]
[tex]T(5^{m})=4T(\frac{5^{\frac{m}{3}}}{5}) log5^{m}[/tex]
[tex]T(5^{m})=S(m)[/tex]
[tex] S(m)=4S(\frac{m}{3}-1) m\Rightarrow m^{\log_{3}4}\Rightarrow {\color{DarkBlue} (logn)^{\log_{3}4}}[/tex]
(۰۵ دى ۱۳۹۱ ۰۵:۳۹ ب.ظ)mp1368 نوشته شده توسط: سلام . اینم یه حل عمومی ترسلام
[tex]T(5^{m})=4T(\frac{5^{\frac{m}{3}}}{5}) mlog5\Rightarrow T(5^{m})=4T(5^{\frac{m}{3}}-1) m[/tex]
این قسمت رو اشتباه نوشتین.
[tex]T(\frac{5^{\frac{m}{3}}}{5})\neq T(5^{\frac{m}{3}}-1)=T(5^{(\frac{m}{3}-1)})[/tex]
(۰۵ دى ۱۳۹۱ ۰۲:۱۵ ب.ظ)azad_ahmadi نوشته شده توسط: سلام.سلام
این سوال رو میتونیم به شکل قضیه اصلی تبدیل کنیم.
(۰۵ دى ۱۳۹۱ ۰۱:۳۴ ب.ظ)nazaninzahra2 نوشته شده توسط:سلام. میشه بگید چطور از ۴^k ، تونستین ۴^loglogn رو بدست بیارید!(05 دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)fatima2007 نوشته شده توسط: سلام شما اینو چطور حل میکنید؟
میشه مراحلش و جواب اخرشو بگذارید
۴T(∛n/5)+logn
سلام
چون رشد جذر از تقسیم بیشتره از تقسیم بر ۵ صرف نظر میکنیم و با تغییر متغییر [tex]n=3^{3^k}[/tex] داریم :
[tex]T(3^{3^k})=4T(3^{3^{k-1}}) log(3^{3^k})[/tex]
حال با تغییر تابع [tex]G(k)=T(3^{3^k})[/tex] داریم :
[tex]G(k)=4G(k-1) 3^k[/tex]
با حل این رابطه بازگشتی ناهمگن داریم : [tex]G(k)=4^K[/tex]
حال با تغییر تابع و تغییر متغییر به صورت برعکس داریم :
[tex]T(n)=4^{loglogn}[/tex]
مگه فرض نکردیم [tex]n=3^{3^k}[/tex] ؟ دوبار از دو طرف لگاریتم بگیرین به این نتیجه میرسین که [tex]k=loglogn[/tex]
(۰۵ دى ۱۳۹۱ ۰۶:۴۹ ب.ظ)nazaninzahra2 نوشته شده توسط: سلام
این قسمت رو اشتباه نوشتین.
[tex]T(\frac{5^{\frac{m}{3}}}{5})\neq T(5^{\frac{m}{3}}-1)=T(5^{(\frac{m}{3}-1)})[/tex]
سلام .
ببخشید اشتباه تایپی بود ولی کلا این مرحله رو اضافی نوشتم با حذفش جواب جمع و جور و ساده تر شد.
موفق باشید