سلام و وقت بخیر
روش حل این رابطه بازگشتی؟
[tex]T(n)=1/n*\sum_{q=1}^{n}[T(q-1)+T(n-q)]+n[/tex]
ممنون
(۰۷ دى ۱۳۹۵ ۰۵:۳۷ ب.ظ)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]
تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
[tex]T(n)\: =\frac{\: 2}{n}\sum_{q=0}^{n-1}T(q)\: +\: n[/tex]
(۰۷ دى ۱۳۹۵ ۰۷:۴۵ ب.ظ)Alirezaj نوشته شده توسط: تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
[tex]T(n)\: =\frac{\: 2}{n}\sum_{q=0}^{n-1}T(q)\: +\: n[/tex]
همون رابطه ی خودتو بازش کنی میفهمی
(۰۷ دى ۱۳۹۵ ۰۸:۰۰ ب.ظ)arash691 نوشته شده توسط:(07 دى ۱۳۹۵ ۰۷:۴۵ ب.ظ)Alirezaj نوشته شده توسط: تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
[tex]T(n)\: =\frac{\: 2}{n}\sum_{q=0}^{n-1}T(q)\: +\: n[/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]
سلام .خیلی ممنون