اینطوری حل می شه:
اگه بجای logn قرار بدیم رادیکال n:
با توجه به بزرگتر بودن رادیکال n نسبت به logn و اینکه این عبارت توی مخرجه، پس هر مرتبه ای بدست بیاد، از مرتبه‌ی رابطه‌ی اولیه کوچکتر خواهد بود( چون تقسیماتش کمتره درختش کوچکتر می شه) یعنی داریم:
[tex]T(n)=2T(\frac{n}{2}) T(\frac{n}{logn}) n\geq S(n)=2S(\frac{n}{2}) S(\frac{n}{\sqrt{n}}) n=2S(\frac{n}{2}) S(\sqrt{n}) n[/tex]
حالا برای حل (S(n داریم:
یک بار رابطه بازگشتی رو به صورت زیر در نظر می گیریم و مرتبه رو به دست میاریم.
[tex]S(n)= 2S(\frac{n}{2}) S(\frac{n}{2}) n=3S(\frac{n}{2}) n=O(n^{Log{_{2}}^{3}})[/tex]
یک بار دیگه رابطه بازگشتی رو به صورت زیر در نظر می گیریم و مرتبه رو به دست میاریم.
[tex]S(n)= 2S(\sqrt{n}) S(\sqrt{n}) n=3S(\sqrt{n}) n=O(n)[/tex]
مرتبه هر کدوم که بزرگتر بود میشه مرتبه رابطه بازگشتی اصلی (S(n یعنی:
[tex]S(n)=O(n^{{Log_{2}}^{3}})[/tex]
حالا می تونیم مرتبه‌ی رابطه T رو نسبت به S بگیم.
طبق توضیحاتی که در اول پست دادم داریم:
[tex]\begin{Bmatrix}T(n)\geq S(n) \\ S(n)=O(n^{Log{_{2}}^{3}}) \end{Bmatrix}\Rightarrow T(n)=\Omega(n^{Log{_{2}}^{3}})[/tex]
دقت شود که این یک حد پایین برای رابطه است.
لطفا اساتید در مورد این جواب نظر بدهند ...
(۲۱ بهمن ۱۳۹۰ ۰۴:۰۶ ب.ظ)yaali نوشته شده توسط: یک بار دیگه رابطه بازگشتی رو به صورت زیر در نظر می گیریم و مرتبه رو به دست میاریم.ببخشید این قسمت رو چطوری بدست آوردید؟
[tex]S(n)= 2S(\sqrt{n}) S(\sqrt{n}) n=3S(\sqrt{n}) n=O(n)[/tex]
[tex]S(n)=3S(\sqrt{n}) n\Rightarrow S(2^{m})=3S(2^{\frac{m}{2}}) 2^{m}\Rightarrow H(m)=3H(\frac{m}{2}) 2^{m}\overset{Master}{\rightarrow}O(2^{m})\Rightarrow O(2^{Log n})\Rightarrow O(n)[/tex]
اینطوری حل می شه:
اگه بجای logn قرار بدیم رادیکال n:
با توجه به بزرگتر بودن رادیکال n نسبت به logn و اینکه این عبارت توی مخرجه، پس هر مرتبه ای بدست بیاد، از مرتبه‌ی رابطه‌ی اولیه کوچکتر خواهد بود( چون تقسیماتش کمتره درختش کوچکتر می شه) یعنی داریم:
[tex]T(n)=2T(\frac{n}{Logn}) 3n\geq S(n)=2S(\sqrt{n}) 3n[/tex]
پس جواب S رو بدست میاریم:
[tex]S(n)=2S(\sqrt{n}) 3n=S(2^{m})=2S(2^{\frac{m}{2}}) 3*2^{m}\Rightarrow H(m)=2H(\frac{m}{2}) 3*2^{m}\overset{Master}{\rightarrow}O(3*2^{m})=O(3*2^{Logn})=O(3n)=O(n)[/tex]
حالا داریم:
[tex]T(n)\geq S(n)\Rightarrow T(n)=\Omega(n)[/tex]
لطفا اساتید در مورد این جواب نظر بدهند ...
(۲۱ بهمن ۱۳۹۰ ۰۴:۳۲ ب.ظ)yaali نوشته شده توسط: [tex]S(n)=3S(\sqrt{n}) n\Rightarrow S(2^{m})=3S(2^{\frac{m}{2}}) 2^{m}\Rightarrow H(m)=3H(\frac{m}{2}) 2^{m}\overset{Master}{\rightarrow}O(2^{m})\Rightarrow O(2^{Log n})\Rightarrow O(n)[/tex]من فکر کردم در قسمت آخر چون ۲^m چند جمله ای نیست نمیشه از قضیه استفاده کرد.
باید بصورت چند جمله ای بزرگتر باشه( یعنی اگه یک اپسیلون به a در قضیه اصلی اضافه کنیم بازهم f(n بزرگتر بشه که در اینجا صدق می کنه.)
نه اینکه حتما باید خود f(n چند جمله ای باشه.
(۲۱ بهمن ۱۳۹۰ ۰۵:۲۰ ب.ظ)yaali نوشته شده توسط: باید بصورت چند جمله ای بزرگتر باشه( یعنی اگه یک اپسیلون به a در قضیه اصلی اضافه کنیم بازهم f(n بزرگتر بشه که در اینجا صدق می کنه.)این مطلب رو نمی دونستم . فکر کردم باید خود f هم چند جمله ای باشه. ممنون.
نه اینکه حتما باید خود f(n چند جمله ای باشه.
برای اینکه بتونیم بفهمیم جایی می شه از Master رفت یا نه:
علاوه از شرایط خود قضیه
باید اون اپسیلون توی فرمول قضیه اصلی رو برای رابطه مون تست کنیم.
اگه جواب داد می شه از مستر رفت در غیر اینصورت نه.
خدا رو شکر حل شد.
اگه K ثابت باشه جواب همونی می شه که فرمودید.
اگه K یک تابع بر حسب n باشه، حالا اینکه جواب چی می شه بستگی داره به تابع K
در هر دو حالت هم روش جایگذاری جواب می ده.
به خاطر کمک‌ها سپاسگزارم.
ببخشید اما مگر نه اینکه وقتی میشه از مستر استفاده کرد که درجه تابع G(N)=3*2^N
چند جمله ای باشد و اینجا جی ان چند جمله ای نیست
حال اگر درخت بازگشتی ان را در این مرحله بسازیم به اندازه
[tex]2^{m}\sum_{0}^{logm-1}3^×(TOW۲^i )[/tex]
[tex]O(2^{m}3^×(TOW۲^×lgm )[/tex]
اگر از قوانین لگاریتم استفاده کنیم:
[tex]O(2^{m}3^m )[/tex]
, و از قبل داشتیم:[tex]2^{m}=N[/tex]
حال اگر از قوانین لگاریتم استفاده کنیم خواهیم داشت:
[tex]O(N*N)[/tex]
درخت بازگشتی مطمئن‌تر نیست؟
هر چند که این مقدار کمتر از معادله اصلی است به همان دلیل جایگذاری لگاریتم ان و رادیکال ان
در مورد نحوه بکارگیری Master اینجا توضیح دادم
ارسال ۷ به بعد)مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اون لینک مطالعه میکنم حتما
اما اجالتا چرا با درخت بازگشتی شد ان به توان دو
در ثانی من فک میکنم پیدا کردن کف با اون تغیر متغیر سعیده چیز زیادی دستگیرمون نشه چون به هر حال ما می تونیم مقادیر دیگه ای جای لگاریتم قرار بدیم که درجه رابطمون را بشکنه
متشکرم
(۲۱ بهمن ۱۳۹۰ ۱۱:۴۲ ب.ظ)atharrashno نوشته شده توسط: چرا با درخت بازگشتی شد ان به توان دوشما ارتفاع درخت رو چند گرفتید؟ و چرا؟
(۲۱ بهمن ۱۳۹۰ ۱۱:۴۲ ب.ظ)atharrashno نوشته شده توسط: من فک میکنم پیدا کردن کف با اون تغیر متغیر سعیده چیز زیادی دستگیرمون نشه چون به هر حال ما می تونیم مقادیر دیگه ای جای لگاریتم قرار بدیم که درجه رابطمون را بشکنهاولا بنده ادعایی بر صحیح و کامل و بی نقص بودن جواب ندارم.
در ثانی
بله چیزای دیگه هم می شه. اما در اینجا ظاهرا رادیکال n نزدیکترین و بهترین عبارت برای جایگزینیه.
به نظر شما چه عبارتی بگذاریم که بشه حلش کرد؟
در ضمن این جواب من یک حد پایین برای پاسخ رابطه‌ی اصلی است.
(۲۱ بهمن ۱۳۹۰ ۱۰:۰۹ ب.ظ)atharrashno نوشته شده توسط: حال اگر از قوانین لگاریتم استفاده کنیم خواهیم داشت:
[tex]O(N*N)[/tex]
[tex]T(n)=2T(\frac{n}{logn}) 3n< T(n)=2T(\frac{n}{2}) 3n=O(nlogn)[/tex]
پس مقدار مجانبیش حتما از nlogn کمتره.
باید یه کران پایینم براش پیدا کرد تا بشه ساندویچش کرد خورد
.
فکر کنم ساندویچ نشه. چون من در بالا (ارسال ۵) براش حد پایین n رو بدست آوردم.