(۰۵ دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)fatima2007 نوشته شده توسط:  سلام شما اینو چطور حل میکنید؟
میشه مراحلش و جواب اخرشو بگذارید

۴T(∛n/5)+logn

سلام
چون رشد جذر از تقسیم بیشتره از تقسیم بر ۵ صرف نظر میکنیم و با تغییر متغییر $n=3^{3^k}$ داریم :
$T(3^{3^k})=4T(3^{3^{k-1}}) log(3^{3^k})$
حال با تغییر تابع $G(k)=T(3^{3^k})$ داریم :
$G(k)=4G(k-1) 3^k$
با حل این رابطه بازگشتی ناهمگن داریم : $G(k)=4^K$
حال با تغییر تابع و تغییر متغییر به صورت برعکس داریم :
$T(n)=4^{loglogn}$

سلام.
این سوال رو میتونیم به شکل قضیه اصلی تبدیل کنیم.

---

(۰۵ دى ۱۳۹۱ ۰۱:۳۴ ب.ظ)nazaninzahra2 نوشته شده توسط:  

(05 دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)fatima2007 نوشته شده توسط:  سلام شما اینو چطور حل میکنید؟
میشه مراحلش و جواب اخرشو بگذارید

۴T(∛n/5)+logn

سلام
چون رشد جذر از تقسیم بیشتره از تقسیم بر ۵ صرف نظر میکنیم و با تغییر متغییر $n=3^{3^k}$ داریم :
$T(3^{3^k})=4T(3^{3^{k-1}}) log(3^{3^k})$
حال با تغییر تابع $G(k)=T(3^{3^k})$ داریم :
$G(k)=4G(k-1) 3^k$
با حل این رابطه بازگشتی ناهمگن داریم : $G(k)=4^K$
حال با تغییر تابع و تغییر متغییر به صورت برعکس داریم :
$T(n)=4^{loglogn}$

سلام. میشه بگید چطور از ۴^k ، تونستین ۴^loglogn رو بدست بیارید!

سلام . اینم یه حل عمومی تر

(۰۵ دى ۱۳۹۱ ۰۵:۳۹ ب.ظ)mp1368 نوشته شده توسط:  سلام . اینم یه حل عمومی تر
$T(5^{m})=4T(\frac{5^{\frac{m}{3}}}{5}) mlog5\Rightarrow T(5^{m})=4T(5^{\frac{m}{3}}-1) m$

سلام
این قسمت رو اشتباه نوشتین.
$T(\frac{5^{\frac{m}{3}}}{5})\neq T(5^{\frac{m}{3}}-1)=T(5^{(\frac{m}{3}-1)})$

---

(۰۵ دى ۱۳۹۱ ۰۲:۱۵ ب.ظ)azad_ahmadi نوشته شده توسط:  سلام.
این سوال رو میتونیم به شکل قضیه اصلی تبدیل کنیم.

---

(۰۵ دى ۱۳۹۱ ۰۱:۳۴ ب.ظ)nazaninzahra2 نوشته شده توسط:  

(05 دى ۱۳۹۱ ۰۱:۲۴ ق.ظ)fatima2007 نوشته شده توسط:  سلام شما اینو چطور حل میکنید؟
میشه مراحلش و جواب اخرشو بگذارید

۴T(∛n/5)+logn

سلام
چون رشد جذر از تقسیم بیشتره از تقسیم بر ۵ صرف نظر میکنیم و با تغییر متغییر $n=3^{3^k}$ داریم :
$T(3^{3^k})=4T(3^{3^{k-1}}) log(3^{3^k})$
حال با تغییر تابع $G(k)=T(3^{3^k})$ داریم :
$G(k)=4G(k-1) 3^k$
با حل این رابطه بازگشتی ناهمگن داریم : $G(k)=4^K$
حال با تغییر تابع و تغییر متغییر به صورت برعکس داریم :
$T(n)=4^{loglogn}$

سلام. میشه بگید چطور از ۴^k ، تونستین ۴^loglogn رو بدست بیارید!

سلام
مگه فرض نکردیم $n=3^{3^k}$ ؟ دوبار از دو طرف لگاریتم بگیرین به این نتیجه میرسین که $k=loglogn$