هوالعلیم
لطفا راهنمایی ...
متشکرم.
[tex]T(n)=2T(\frac{n}{2}) T(\frac{n}{logn}) n[/tex]
هوالعلیم
لطفا راهنمایی ...
متشکرم.
[tex]T(n)=2T(\frac{n}{logn}) 3n[/tex]
هوالعلیم
لطفا راهنمایی ...
با تشکر
[tex]T(n)=T(\frac{n}{2}) T(\sqrt{n}) n[/tex]
هوالعلیم
لطفا راهنمایی ...
متشکرم.
[tex]T(n)=2T(n-c) K[/tex]
الف: اگه K تابعی بر حسب n باشه.
ب: اگه K عدد ثابت مثبت صحیح باشه.
جوابش میشه [tex]\Theta (2^{\frac{n}{c}})[/tex]
روش بدست آوردنش هم بشیوه نوشتن مکرر تابع هستش من چند حالت اولش رو می نویسم:
[tex]T(n)=2T(n-c) K[/tex]
[tex]=2(2T(n-2c) K) K[/tex]
[tex]=2^{2}T(n-2c) 2K K[/tex]
[tex]=2^{2}(2T(n-3c) K) 2K K[/tex]
[tex]=2^{3}T(n-3c) 2^{2}K 2K K[/tex]
یک بار رابطه بازگشتی رو به صورت زیر در نظر بگیرید و مرتبه رو به دست بیارید.
[tex]T(n)=T(\frac{n}{2}) T(\frac{n}{2}) n[/tex]
یک بار دیگه رابطه بازگشتی رو به صورت زیر در نظر بگیرید و مرتبه رو به دست بیارید.
[tex]T(n)=T(\sqrt{n}) T(\sqrt{n}) n[/tex]
مرتبه هر کدوم که بزرگتر بود میشه مرتبه رابطه بازگشتی اصلی
پس با این اوصاف میشه از مرتبه n درسته؟
(۱۷ بهمن ۱۳۹۰ ۱۱:۳۷ ب.ظ)پشتکار نوشته شده توسط: پس با این اوصاف میشه از مرتبه n درسته؟
فکر کنم بشه nlogn
خیلی ممنونم
روش جالبیه
اولی می شه بیگ اوی nLogn
دومی می شه بیگ اوی n
نتیجه:
بیگ اوی nLogn
مورد الف چی؟
مورد الف هم همون میشه .
(۱۷ بهمن ۱۳۹۰ ۱۱:۵۴ ب.ظ)yaali نوشته شده توسط: مورد الف چی؟
مورد الف کمی سخت میشه ولی با استفاده از همین شیوه می تونید به جواب برسید
این رو از کجا آوردید؟
به نظرم فقط با ترسیم درخت حل شه
فکر کنم اگه بجای logn قرار بدیم رادیکال n ساده‌تر بشه . با توجه به بزرگتر بودن رادیکال n نسبت به logn
جواب هم میشه از (جواب)o
با جایگذاری رادیکالn بجای logn
[tex]t(n)=2t(n/\sqrt{n}) 3n\Rightarrow t(n)=2t(\sqrt{n}) 3n\Rightarrow n=2^m\Rightarrow t(2^m)=2t(2^{m/2}) 3*2^m\Rightarrow t(m)=2t(m/2) 3*2^m[/tex]
فقط تا همین جا تونستم حل کنم.