۰
subtitle
ارسال: #۱
سوال ۵۱ دولتی مهندسی کامپیوتر سال ۸۸
۰
ارسال: #۲
RE: سوال ۵۱ مهندسی کامپیوتر ۸۸
[tex]\small \bg_white \fn_jvn T(n)=4T(\frac{\sqrt{n}}{3}) \log^{2} n\\ \xrightarrow[ ]{n=2^{(2^{\mathbf{x}})}}\ T(2^{(2^{\mathbf{x}})})=4T(2^{(2^{\mathbf{x-1}})}) 4^{\mathbf{x}}\\ \xrightarrow[ ]{T(2^{(2^{\mathbf{x}})})=F(\mathbf{x})}\ F(\mathbf{x})=4F(\mathbf{x}-1) 4^{\mathbf{x}}\\ (r-4)^{2}=0\Rightarrow F(\mathbf{x})=(a\mathbf{x} b )4^{\mathbf{x}}=\mathbf{\theta} (x4^{\mathbf{x}})=\mathbf{\theta} (\log \log n \ log^{2} n)[/tex]
۰
ارسال: #۳
RE: سوال ۵۱ مهندسی کامپیوتر ۸۸
قسمت آخر از روی معادله مشخصه شکل جواب بدست اومده
از ۱/۳ هم بدلیل وجود رادیکال روی n میشه صرف نظر کرد چون رادیکال تاثیر بیشتری روی کم شدن n داره
تا تقسیم بر ۳/
اگر اشتباه میگم دوستان کمک کنند
البته این تغییر متغیر راحت‌تر جواب میده:
[tex]\tiny \fn_jvn \small \bg_white \fn_jvn T(n)=4T(\frac{\sqrt{n}}{3}) \log^{2} n\\ \xrightarrow[ ]{n=2^{\mathbf{x}}}\ T(2^{\mathbf{x}})=4T(2^{\frac{\mathbf{x}}{2}}) \mathbf{x}^{2}\\ \xrightarrow[ ]{T(2^{\mathbf{x}})=F(\mathbf{x})}\ F(\mathbf{x})=4F(\frac{\mathbf{x}}{2}) \mathbf{x}^{2}\\ \xrightarrow[ ]{master} F(\mathbf{x})=\mathbf{\theta} (\log x\ x^{2})=\mathbf{\theta} (\log \log n \ log^{2} n)[/tex]
از ۱/۳ هم بدلیل وجود رادیکال روی n میشه صرف نظر کرد چون رادیکال تاثیر بیشتری روی کم شدن n داره
تا تقسیم بر ۳/
اگر اشتباه میگم دوستان کمک کنند
البته این تغییر متغیر راحت‌تر جواب میده:
[tex]\tiny \fn_jvn \small \bg_white \fn_jvn T(n)=4T(\frac{\sqrt{n}}{3}) \log^{2} n\\ \xrightarrow[ ]{n=2^{\mathbf{x}}}\ T(2^{\mathbf{x}})=4T(2^{\frac{\mathbf{x}}{2}}) \mathbf{x}^{2}\\ \xrightarrow[ ]{T(2^{\mathbf{x}})=F(\mathbf{x})}\ F(\mathbf{x})=4F(\frac{\mathbf{x}}{2}) \mathbf{x}^{2}\\ \xrightarrow[ ]{master} F(\mathbf{x})=\mathbf{\theta} (\log x\ x^{2})=\mathbf{\theta} (\log \log n \ log^{2} n)[/tex]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close