لطفا اینو حل کنید با روش کامل:
توی جزوه ی هادی یوسفی گفته بعدا حل میشه ولی حلش رو ندیدم.توی جزوه ی قدسی هم گفته بعدا حل میشه اما حلش رو نیاورده.
==
[tex]t(n)=3t(n/3) n/lgn[/tex]
سلام
خوب دوست عزیزم بیا یکم این رابطه رو دست کاری کنیم ببینیم میتونیم به جواب برسیم ؟ اولین کارمون اینه که تغییر متغییر بدیم مثلآ بیا بجای [tex]n[/tex] بزاریم : [tex]3^k[/tex] پس رابطه ما اینجوری میشه :
[tex]T(3^k)=3T(3^{k-1}) \frac{3^k}{log(3^K))}[/tex]
در ضمن میدونیم که پایه لگاریتم تاثیری در مرتبه نداره پس من پایه رو ۳ در نظر میگیرم و این رابطه رو بازم ساده تر میکنم :
[tex]T(3^k)=3T(3^{k-1}) \frac{3^k}{k}[/tex]
خوب حالا بیا تغییر تابع بدهیم : یعنی بجای تابع [tex]T(3^k)[/tex] بزاریم : [tex]g(k)[/tex] در این صورت رابطه ما میشه :
[tex]g(k)=3g(k-1) \frac{3^k}{k}[/tex]
فکر کنم تا اینجا آسون بود. مگه نه ؟
خوب حالا بیا این رابطه رو با جایگذاری حل کنیم : میدانیم که : [tex]g(2)=3g(1) \frac{3^2}{2}[/tex]
همچنین میدانیم : [tex]g(3)=3g(2) \frac{3^3}{3}[/tex]
و همنیطور : [tex]g(4)=3g(3) \frac{3^4}{4}[/tex] و در نهایت میدانیم که : [tex]g(5)=3g(4) \frac{3^5}{5}[/tex]
تا اینجا هم که تابلو بود. حالا بیا برای بدست آوردن مدل رابطه مثلآ [tex]g(5)[/tex] رو حساب کنیم :
[tex]g(5)=3[3[3[3g(1) \frac{3^2}{2}] \frac{3^3}{3}] \frac{3^4}{4}] \frac{3^5}{5}=3^4 \frac{3^5}{2} \frac{3^5}{3} \frac{3^5}{4} \frac{3^5}{5}[/tex]
از این حدس میزنم که رابطه این مدلیه که : [tex]g(k)=3[3[3\cdots [3g(1) \frac{3^2}{2}] \frac{3^3}{3}] \frac{3^4}{4}] \cdots \frac{3^k}{k}=3^{k-1} \frac{3^k}{2} \frac{3^k}{3} \frac{3^k}{4} \cdots \frac{3^k}{k}[/tex]
و با کمی ساده سازی میفههم که :
[tex]g(k)=3^{k-1} \frac{3^k}{2} \frac{3^k}{3} \frac{3^k}{4} \cdots \frac{3^k}{k}=3^{k-1} 3^k(\frac{1}{2} \frac{1}{3} \frac{1}{4} \cdots \frac{1}{k})=[tex]g(k)\approx O(3^k(ln(k)))[/tex]
[/tex]
در نتیجه میتوان گفت که :[tex]g(k)\approx O(3^k(ln(k)))[/tex]
حال تغییر تابع رو برمیگردونیم و داریم : [tex]T(3^k)\approx O(3^k(ln(k)))[/tex]
و حال تغییر متغییر رو برمیگردونیم و داریم : [tex]T(n)\approx O(nloglog(n)) = O(nlog^2(n))[/tex]
سعی کردم آسون بگم.
موفق باشی.
با سلام:
دوستان اینم یه روش تستی برای حل مرتبه زمانی به فرم زیر:
اگر فرم کلی مثال ما به این صورت باشد:
[tex]T(n)=aT(n/b) n^{loga}(logn)^{k}[/tex]
مرتبه زمانی اینجوریه محاسبه میشه:
[tex]\Theta (n^{loga}(log n)^{k 1})[/tex]
این یکی از تبصره های قانونmaster هست/...
نکته :در این توضیحات نوشتم [tex]n^{loga}[/tex] منظورم اینه که جواب [tex]loga[/tex] باید برابر با توان n باشه/...
توجه:منظورم از [tex]log a[/tex] همون لگاریتم a در مبنای b هست/...(بلد نبودم چه جوری بایدبنویسن. )
امیدوارم تونسته باشم خوب توضیح داده باشم/... (از کاربر azad_ahmadi بابت تذکرشون ممنونم.)
موفق و پیروز باشید یا حق/...
(۱۷ آذر ۱۳۹۱ ۰۲:۰۳ ق.ظ)deh-ab نوشته شده توسط:(11 آذر ۱۳۹۱ ۱۱:۱۱ ق.ظ)csharpisatechnology نوشته شده توسط: لطفا اینو حل کنید با روش کامل:با سلام:
توی جزوه ی هادی یوسفی گفته بعدا حل میشه ولی حلش رو ندیدم.توی جزوه ی قدسی هم گفته بعدا حل میشه اما حلش رو نیاورده.
==
[tex]t(n)=3t(n/3) n/lgn[/tex]
دوست عزیز روش حل این رابطه به زبان ساده تر اینجوریه
اگر فرم کلی مثال ما به این صورت باشد:
[tex]T(n)=aT(n/b) n^{loga}(logn)^{k}[/tex]
مرتبه زمانی اینجوریه محاسبه میشه:
[tex]\Theta (n^{loga}(log n)^{k 1})[/tex]
این یکی از تبصره های قانونmaster هست/...
نکته :در این توضیحات نوشتم [tex]n^{loga}[/tex] منظورم اینه که جواب [tex]loga[/tex] باید برابر با توان n باشه/...
توجه:منظورم از [tex]log a[/tex] همون لگاریتم a در مبنای b هست/...(بلد نبودم چه جوری بایدبنویسن. )
امیدوارم تونسته باشم خوب توضیح داده باشم/...
موفق و پیروز باشید یا حق/...
سلام. این مساله ای که فرمودین ربطی به سوال پرسیده شده نداره دوست عزیز.
چرا که nlogn نیست و n/logn داده شده. برای حل این سوال باید یا از روش جناب naderx استفاده کرد(روش تغییر متغیر) و یا از روش درخت.
موفق باشید.
(۱۷ آذر ۱۳۹۱ ۰۲:۳۰ ب.ظ)azad_ahmadi نوشته شده توسط:(17 آذر ۱۳۹۱ ۰۲:۰۳ ق.ظ)deh-ab نوشته شده توسط:(11 آذر ۱۳۹۱ ۱۱:۱۱ ق.ظ)csharpisatechnology نوشته شده توسط: لطفا اینو حل کنید با روش کامل:با سلام:
توی جزوه ی هادی یوسفی گفته بعدا حل میشه ولی حلش رو ندیدم.توی جزوه ی قدسی هم گفته بعدا حل میشه اما حلش رو نیاورده.
==
[tex]t(n)=3t(n/3) n/lgn[/tex]
دوست عزیز روش حل این رابطه به زبان ساده تر اینجوریه
اگر فرم کلی مثال ما به این صورت باشد:
[tex]T(n)=aT(n/b) n^{loga}(logn)^{k}[/tex]
مرتبه زمانی اینجوریه محاسبه میشه:
[tex]\Theta (n^{loga}(log n)^{k 1})[/tex]
این یکی از تبصره های قانونmaster هست/...
نکته :در این توضیحات نوشتم [tex]n^{loga}[/tex] منظورم اینه که جواب [tex]loga[/tex] باید برابر با توان n باشه/...
توجه:منظورم از [tex]log a[/tex] همون لگاریتم a در مبنای b هست/...(بلد نبودم چه جوری بایدبنویسن. )
امیدوارم تونسته باشم خوب توضیح داده باشم/...
موفق و پیروز باشید یا حق/...
سلام. این مساله ای که فرمودین ربطی به سوال پرسیده شده نداره دوست عزیز.
چرا که nlogn نیست و n/logn داده شده. برای حل این سوال باید یا از روش جناب naderx استفاده کرد(روش تغییر متغیر) و یا از روش درخت.
موفق باشید.
اره حرفتون درسته من اصلا تقسیم را ندیده بودم/...
از همه عذر خواهی میکنم/...
دوست عزیز بلی اما این رابطه قانون ۲ از master هست اما به شرطی که k از صفر بزرگتر باشه اما اینجا لگاریتم زیر مخرج هست پس توان منفی داره که از صفر کوچک تر میشه و توی پوران و دستنویس و قدسی و کتب دیگه هم خوندم به master حل نمیشه باید تبدیل کنیم . فعلا دارم رو جواب نادر فکر می کنم که به نظرم کامل تره
فقط یه چیز بگم آقا نادر ، فکر می کنم آخر جواب اشتباه کردین:
( nloglog(n نمیشه (n*log^2(n
بلکه همون خودش میشه.
اگه بود (n*log(n)*log(n اونوقت میتونستیم بنویسیم (n*log^2(n
==
دوستانی که موافق هستن با بنده ،سپاس رو بزنن