۰
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