با درود
دوستان این ها رو میشه بفرمائید چطوری حل کرده؟
من حساب میکنم اصلا جور در نمیاد
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رابطه ی مستر این گونه است:
اگر رابطه بازگشتی به فرم [tex]T(n)=aT(\frac{n}{b}) f(n)[/tex]
باشد آن گاه ما عبارت [tex]n^{\log_b^a}[/tex] را حساب می کنیم و رشد آن را با رشد [tex]f(n)[/tex] مقایسه می کنیم
و سه حالت ممکن است پیش بیاید:
حالت اول: یا رشد [tex]n^{\log_b^a}[/tex] بیشتر است که در این صورت [tex]T(n)\epsilon\theta(n^{\log_b^a})[/tex]
حالت دوم: یا رشد [tex]f(n)[/tex] بیشتر است که در این صورت [tex]T(n)\epsilon\theta(f(n))[/tex]
حالت سوم: یا هر دو هم رشد هستند که در این صورت [tex]T(n)\epsilon\theta(f(n)\log n)[/tex] است.
حالا اگر سوال های شما را بررسی کنیم:
در رابطه ی [tex]T(n)=\sqrt{2}T(\frac{n}{2}) \log n[/tex]
[tex]a=\sqrt{2\: },\: b=2,\: \: f(n)=\log n[/tex] است
و [tex]n^{\log_b^a}=n^{log_2^{\sqrt{2}}}=n^{\frac{1}{2}}=\sqrt{n}[/tex] است
که باید رشد آن را با رشد [tex]f(n)=\log n[/tex] مقایسه کنیم
و چون رشد [tex]\sqrt{n}[/tex] بیشتر از رشد [tex]\log n[/tex] است پس حالت اول مستر رخ می دهد و [tex]T(n)\epsilon\theta(\sqrt{n})[/tex]
برای رابطه ی دوم هم اینگونه عمل می کنیم:
[tex]T(n)=T(\frac{n}{2}) 2^n[/tex]
که [tex]a=1,\: b=2,\: \: f(n)=2^n[/tex]
و [tex]n^{\log_b^a}=n^{\log_2^1}=n^0=1[/tex]
و رشد [tex]f(n)=2^n[/tex] بیشتر از آن است پس حالت دوم مستر رخ می دهد و [tex]T(n)\epsilon\theta(2^n)[/tex]