۰
subtitle
ارسال: #۱
حل رابطه ی بازگشتی
سلام وقتی تو یه رابطه بازگشتی غیر خطی اعداد رادیکالی داریم چطور میتونیم حلش کنیم؟
مثلا:
[tex]T(n)=2T(\sqrt{n})+\log n[/tex]
بعضی وقتا هم اعداد فاکتوریل دار داریم اونارو چیکار کنیم؟
[tex]T(n)=2T(\frac{n}{2})+\log n![/tex]
مثلا:
[tex]T(n)=2T(\sqrt{n})+\log n[/tex]
بعضی وقتا هم اعداد فاکتوریل دار داریم اونارو چیکار کنیم؟
[tex]T(n)=2T(\frac{n}{2})+\log n![/tex]
۲
ارسال: #۲
RE: حل رابطه ی بازگشتی
سلام.راههای زیادی هست.بنظرم بهترین راه حلش تغییر متغیر هستش.
مثلا رابطه ی اول:
حال رابطه ی [tex]F(m)\: =\: 2F(\frac{m}{2})\: +\: m[/tex] رو حل می کنیم.
در مورد مثال دوم)
پس رابطه ی بازگشتی داده شده ،معادل رابطه ی بازگشتی [tex]T(n)\: =\: 2T(\frac{n}{2})\: \: +\: n\: Log\: n[/tex] هستش. که جوابش برابر میشه با:
مثلا رابطه ی اول:
[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]
ارسال: #۳
RE: حل رابطه ی بازگشتی
(۱۱ خرداد ۱۳۹۵ ۰۲:۲۶ ق.ظ)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 استفاده کردیم؟
ارسال: #۴
RE: حل رابطه ی بازگشتی
(۱۱ خرداد ۱۳۹۵ ۰۲:۳۲ ق.ظ)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 استفاده کن.باز فرقی نداره.فقط باید این رادیکال رو برداریم
ارسال: #۵
RE: حل رابطه ی بازگشتی
(۱۱ خرداد ۱۳۹۵ ۰۲:۴۱ ق.ظ)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 استفاده کن.باز فرقی نداره.فقط باید این رادیکال رو برداریم
آها اون عدد زیاد مهم نیست
من فکر میکردم اون عدد حتما باید اندازه زیر مسئله های رابطه بازگشتیمون باید باشه
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| نظر در رابطه با استاد داور | علیصا | ۰ | ۱,۷۲۶ |
۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا |
|
| درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) | Saman | ۶ | ۷,۴۴۵ |
۲۷ خرداد ۱۳۹۷ ۰۳:۲۴ ب.ظ آخرین ارسال: saeed_vahidi |
|
| رابطه n~1 | Mr.R3ZA | ۰ | ۱,۹۶۱ |
۲۰ خرداد ۱۳۹۷ ۰۱:۳۵ ق.ظ آخرین ارسال: Mr.R3ZA |
|
| توصیه های مهم در رابطه با انتخاب رشته (مهم) | Happiness.72 | ۰ | ۲,۱۳۰ |
۱۹ خرداد ۱۳۹۷ ۱۲:۳۶ ق.ظ آخرین ارسال: Happiness.72 |
|
| رابطه چند به یک | somayeh afsh | ۰ | ۱,۷۳۰ |
۰۷ خرداد ۱۳۹۷ ۱۲:۲۸ ب.ظ آخرین ارسال: somayeh afsh |
|
| رسم درخت بازگشتی برای t(n)=9t(n/3)+n | jumper | ۶ | ۶,۶۴۶ |
۱۷ دى ۱۳۹۶ ۰۶:۱۶ ب.ظ آخرین ارسال: jumper |
|
| حل رابطه جایگذاری با تکرار | rahkaransg | ۱ | ۲,۳۲۰ |
۱۷ دى ۱۳۹۶ ۱۱:۲۹ ق.ظ آخرین ارسال: rahkaransg |
|
| حل روابط بازگشتی درجه ۳ | rahkaransg | ۲ | ۳,۰۵۷ |
۱۴ دى ۱۳۹۶ ۰۵:۲۴ ب.ظ آخرین ارسال: rahkaransg |
|
| جواب رابطه های بازگشتی | rahkaransg | ۰ | ۱,۸۴۲ |
۱۴ دى ۱۳۹۶ ۱۲:۲۴ ق.ظ آخرین ارسال: rahkaransg |
|
| تقسیم در جبر رابطه ای | Ella | ۱ | ۲,۲۶۹ |
۲۸ آذر ۱۳۹۶ ۱۲:۰۰ ق.ظ آخرین ارسال: Ella |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close