۰
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