سلام وقتی تو یه رابطه بازگشتی غیر خطی اعداد رادیکالی داریم چطور میتونیم حلش کنیم؟
مثلا:
[tex]T(n)=2T(\sqrt{n})+\log n[/tex]
بعضی وقتا هم اعداد فاکتوریل دار داریم اونارو چیکار کنیم؟
[tex]T(n)=2T(\frac{n}{2})+\log n![/tex]
(۱۱ خرداد ۱۳۹۵ ۰۲:۱۲ ق.ظ)samanbeigmiri نوشته شده توسط: برای حل رادیکالی ها تغییر متغیر و برای حل لگاریتیم های n فاکتوریل معمولا باید از هم ارزی nlogn استفاده کنید
کتابی که میخونید چیه دقیقا؟؟ ارجاع بدیم به یه کتاب بهتره از یه پاسخ کوتاه.مگر اینکه دانشجو باشید
بله متاسفانه دانشجو ام ولی کتابی که تدریس میشه clrs هستش( کتاب خیلی سنگینیه برا من )
تو کتابا دیدم جوابشو ولی متوجه نمیشم میخوام ببینم از روشی که خودم حل میکنم میشه حلش کرد یا نه
ما غیر خطیارو میومدیم تعداد زیر مسئله هارو a میگرفتیم اندازه زیر مسائلو b میگرفتیم بعد به جای n مقدار [tex]b^k[/tex] رو جایگذلری میکردیم تا رابطمون حل بشه
این همون روش تغییر متغیره ولی تو رادیکالی چطوری این a و b رو مشخص کنیم؟
سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:
[tex]T(n)\: =\: 2T(\sqrt{n})\: + Log\: n[/tex]
[tex]n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)[/tex]
[tex]\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)[/tex]
[tex]\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)[/tex]
حال رابطه ی [tex]F(m)\: =\: 2F(\frac{m}{2})\: +\: m[/tex] رو حل می کنیم.
[tex]F(m)=\theta(m\: lg \: m)[/tex]
[tex]T(n)=\theta\: (\lg\: n\: .\: \lg\lg n\: )[/tex]
در مورد مثال دوم)
[tex]Log\: n!\: \sim\: Log\: (n^n)\: \: \sim\: \: n\: Log\: n\: [/tex]
پس رابطه ی بازگشتی داده شده ،معادل رابطه ی بازگشتی [tex]T(n)\: =\: 2T(\frac{n}{2})\: \: +\: n\: Log\: n[/tex] هستش. که جوابش برابر میشه با:
[tex]T(n)\: =\: \theta\: (n\: Log^2n)[/tex]
(۱۱ خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)IranianWizard نوشته شده توسط: سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:
[tex]T(n)\: =\: 2T(\sqrt{n})\: + Log\: n[/tex]
[tex]n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)[/tex]
[tex]\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)[/tex]
[tex]\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)[/tex]
حال رابطه ی [tex]F(m)\: =\: 2F(\frac{m}{2})\: +\: m[/tex] رو حل می کنیم.
[tex]F(m)=\theta(m\: log \: m)[/tex]
[tex]T(n)=\theta\: (\log\: n\: .\: \log\log n\: )[/tex]
چرا ما تو تغییر متغیر از ۲ به توان m استفاده کردیم؟
(۱۱ خرداد ۱۳۹۵ ۰۲:۳۲ ق.ظ)kamal3401 نوشته شده توسط:خب پس از چی استفاده کنیم؟(11 خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)IranianWizard نوشته شده توسط: سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:
[tex]T(n)\: =\: 2T(\sqrt{n})\: + Log\: n[/tex]
[tex]n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)[/tex]
[tex]\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)[/tex]
[tex]\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)[/tex]
حال رابطه ی [tex]F(m)\: =\: 2F(\frac{m}{2})\: +\: m[/tex] رو حل می کنیم.
[tex]F(m)=\theta(m\: log \: m)[/tex]
[tex]T(n)=\theta\: (\log\: n\: .\: \log\log n\: )[/tex]
چرا ما تو تغییر متغیر از ۲ به توان m استفاده کردیم؟
باید یطوری رابطه رو ساده کنیم خب.
شما از ۳ به توان m استفاده کن.باز فرقی نداره.فقط باید این رادیکال رو برداریم
(۱۱ خرداد ۱۳۹۵ ۰۲:۴۱ ق.ظ)IranianWizard نوشته شده توسط:(11 خرداد ۱۳۹۵ ۰۲:۳۲ ق.ظ)kamal3401 نوشته شده توسط:خب پس از چی استفاده کنیم؟(11 خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)IranianWizard نوشته شده توسط: سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:
[tex]T(n)\: =\: 2T(\sqrt{n})\: + Log\: n[/tex]
[tex]n=2^m\: \: \: \: \mapsto\: \: \: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + Log\: (2^m)[/tex]
[tex]\: T(2^m)\: =\: 2T(2^{\frac{m}{2}})\: + \theta(m)[/tex]
[tex]\: T(2^m)\: =\: F(m)\: \: \: \: \mapsto\: \: \: F(m)\: =\: 2F(\frac{m}{2})\: + \theta(m)[/tex]
حال رابطه ی [tex]F(m)\: =\: 2F(\frac{m}{2})\: +\: m[/tex] رو حل می کنیم.
[tex]F(m)=\theta(m\: log \: m)[/tex]
[tex]T(n)=\theta\: (\log\: n\: .\: \log\log n\: )[/tex]
چرا ما تو تغییر متغیر از ۲ به توان m استفاده کردیم؟
باید یطوری رابطه رو ساده کنیم خب.
شما از ۳ به توان m استفاده کن.باز فرقی نداره.فقط باید این رادیکال رو برداریم
آها اون عدد زیاد مهم نیست
من فکر میکردم اون عدد حتما باید اندازه زیر مسئله های رابطه بازگشتیمون باید باشه