۱
subtitle
ارسال: #۱
رابطه بازگشتی
سلام و وقت بخیر
روش حل این رابطه بازگشتی؟
[tex]T(n)=1/n*\sum_{q=1}^{n}[T(q-1)+T(n-q)]+n[/tex]
ممنون
روش حل این رابطه بازگشتی؟
[tex]T(n)=1/n*\sum_{q=1}^{n}[T(q-1)+T(n-q)]+n[/tex]
ممنون
۱
ارسال: #۲
RE: رابطه بازگشتی
(۰۷ دى ۱۳۹۵ ۰۵:۳۷ ب.ظ)Alirezaj نوشته شده توسط: سلام و وقت بخیرسلام.
روش حل این رابطه بازگشتی؟
[tex]T(n)=1/n*\sum_{q=1}^{n}[T(q-1)+T(n-q)]+n[/tex]
ممنون
[tex]T(n)\: =\frac{\: 2}{n}\sum_{q=0}^{n-1}T(q)\: +\: n[/tex]
[tex]nT(n)\: =\: 2\sum_{q=0}^{n-1}T(q)\: +\: n^2[/tex]
و
[tex](n-1)T(n-1)\: =\: 2\sum_{q=0}^{n-2}T(q)\: +\: (n-1)^2[/tex]
در نتیجه:
[tex]nT(n)\: -(n-1)T(n-1)\: =2\sum_{q=0}^{n-1}T(q)+n^2\: -\: 2\sum_{q=0}^{n-2}T(q)\: -\: (n-1)^2[/tex]
[tex]nT(n)\: -(n-1)T(n-1)\: =2\sum_{q=0}^{n-2}T(q)\: +2T(n-1)+n^2\: -\: 2\sum_{q=0}^{n-2}T(q)\: -\: (n-1)^2[/tex]
[tex]nT(n)\: -(n-1)T(n-1)\: =2T(n-1)+n^2-\: (n-1)^2[/tex]
[tex]nT(n)\: -(n+1)T(n-1)\: =n^2-\: (n-1)^2[/tex]
[tex]nT(n)\: =(n+1)T(n-1)\: +2n-1[/tex]
سپس طرفین رو بر n(n+1) تقسیم میکنیم.[tex]nT(n)\: -(n-1)T(n-1)\: =2\sum_{q=0}^{n-2}T(q)\: +2T(n-1)+n^2\: -\: 2\sum_{q=0}^{n-2}T(q)\: -\: (n-1)^2[/tex]
[tex]nT(n)\: -(n-1)T(n-1)\: =2T(n-1)+n^2-\: (n-1)^2[/tex]
[tex]nT(n)\: -(n+1)T(n-1)\: =n^2-\: (n-1)^2[/tex]
[tex]nT(n)\: =(n+1)T(n-1)\: +2n-1[/tex]
[tex]\frac{nT(n)}{n(n+1)}\: =\frac{(n+1)T(n-1)}{n(n+1)}\: +\frac{2n-1}{n(n+1)}[/tex]
[tex]\frac{T(n)}{(n+1)}\: =\frac{T(n-1)}{n}\: +\frac{2n-1}{n(n+1)}[/tex]
[tex]S(n)=\frac{T(n)}{(n+1)}\: \: \longrightarrow\: \: \: S(n)=S(n-1)\: +\frac{2n-1}{n(n+1)}[/tex]
[tex]S(n)=S(n-1)\: +\theta(\frac{1}{n})[/tex]
[tex]S(n)=\theta(\lg n)[/tex]
[tex]T(n)\: =\theta((n+1)\lg n)\: =\: \theta(nlgn)[/tex]
[tex]\frac{T(n)}{(n+1)}\: =\frac{T(n-1)}{n}\: +\frac{2n-1}{n(n+1)}[/tex]
[tex]S(n)=\frac{T(n)}{(n+1)}\: \: \longrightarrow\: \: \: S(n)=S(n-1)\: +\frac{2n-1}{n(n+1)}[/tex]
[tex]S(n)=S(n-1)\: +\theta(\frac{1}{n})[/tex]
[tex]S(n)=\theta(\lg n)[/tex]
[tex]T(n)\: =\theta((n+1)\lg n)\: =\: \theta(nlgn)[/tex]
ارسال: #۳
RE: رابطه بازگشتی
تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
بقیه راه حل کاملا مشخص .ممنون
[tex]T(n)\: =\frac{\: 2}{n}\sum_{q=0}^{n-1}T(q)\: +\: n[/tex]
ارسال: #۴
RE: رابطه بازگشتی
ارسال: #۵
RE: رابطه بازگشتی
(۰۷ دى ۱۳۹۵ ۰۸:۰۰ ب.ظ)arash691 نوشته شده توسط:(07 دى ۱۳۹۵ ۰۷:۴۵ ب.ظ)Alirezaj نوشته شده توسط: تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
[tex]T(n)\: =\frac{\: 2}{n}\sum_{q=0}^{n-1}T(q)\: +\: n[/tex]
همون رابطه ی خودتو بازش کنی میفهمی
دقیقا همین کارو انجام دادم (با عدد گذاری ) ولی متوجه نشدم چطوری رابطه به این صورت شده!!!؟
۲
ارسال: #۶
RE: رابطه بازگشتی
سلام.
واسه قسمت اولش :
[tex]T(n)=\frac{1}{n}\sum^n_{q=1}T(q-1)+T(n-q)=\frac{1}{n}[T(0)+T(n-1)+T(1)+T(n-2)+...+T(n-2)+T(1)+T(n-1)+T(0)]=\frac{1}{n}[2T(0)+2T(1)+...+2T(n-1)]=\frac{2}{n}[T(0)+...+T(n-1)]=\frac{2}{n}\sum^{n-1}_{q=0}T(q)[/tex]
واسه قسمت اولش :
[tex]T(n)=\frac{1}{n}\sum^n_{q=1}T(q-1)+T(n-q)=\frac{1}{n}[T(0)+T(n-1)+T(1)+T(n-2)+...+T(n-2)+T(1)+T(n-1)+T(0)]=\frac{1}{n}[2T(0)+2T(1)+...+2T(n-1)]=\frac{2}{n}[T(0)+...+T(n-1)]=\frac{2}{n}\sum^{n-1}_{q=0}T(q)[/tex]
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| نظر در رابطه با استاد داور | علیصا | ۰ | ۱,۴۷۵ |
۱۴ مهر ۱۴۰۰ ۰۶:۰۵ ب.ظ آخرین ارسال: علیصا |
|
| درخواست(محاسبه پیچیدگی زمانی)(بخش روابط بازگشتی) | 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