۰
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