تالار گفتمان مانشت

هوالعلیم

لطفا راهنمایی ...
متشکرم.

[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 درسته؟

(17 بهمن 1390 11:37 ب.ظ)پشتکار نوشته شده توسط: [ -> ]پس با این اوصاف میشه از مرتبه n درسته؟

فکر کنم بشه nlogn

خیلی ممنونم
روش جالبیه
اولی می شه بیگ اوی nLogn
دومی می شه بیگ اوی n

نتیجه:

بیگ اوی nLogn

مورد الف چی؟

مورد الف هم همون میشه .

(17 بهمن 1390 11:54 ب.ظ)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]
فقط تا همین جا تونستم حل کنم.