۱
subtitle
ارسال: #۱
رابطه بازگشتی
سلام و وقت بخیر
روش حل این رابطه بازگشتی؟
T(n)=1/n∗∑nq=1[T(q−1)+T(n−q)]+n
ممنون
روش حل این رابطه بازگشتی؟
T(n)=1/n∗∑nq=1[T(q−1)+T(n−q)]+n
ممنون
۱
ارسال: #۲
RE: رابطه بازگشتی
(۰۷ دى ۱۳۹۵ ۰۵:۳۷ ب.ظ)Alirezaj نوشته شده توسط: سلام و وقت بخیرسلام.
روش حل این رابطه بازگشتی؟
T(n)=1/n∗∑nq=1[T(q−1)+T(n−q)]+n
ممنون
T(n)=2n∑n−1q=0T(q)+n
nT(n)=2∑n−1q=0T(q)+n2
و
(n−1)T(n−1)=2∑n−2q=0T(q)+(n−1)2
در نتیجه:
nT(n)−(n−1)T(n−1)=2∑n−1q=0T(q)+n2−2∑n−2q=0T(q)−(n−1)2
nT(n)−(n−1)T(n−1)=2∑n−2q=0T(q)+2T(n−1)+n2−2∑n−2q=0T(q)−(n−1)2
nT(n)−(n−1)T(n−1)=2T(n−1)+n2−(n−1)2
nT(n)−(n+1)T(n−1)=n2−(n−1)2
nT(n)=(n+1)T(n−1)+2n−1
سپس طرفین رو بر n(n+1) تقسیم میکنیم.nT(n)−(n−1)T(n−1)=2∑n−2q=0T(q)+2T(n−1)+n2−2∑n−2q=0T(q)−(n−1)2
nT(n)−(n−1)T(n−1)=2T(n−1)+n2−(n−1)2
nT(n)−(n+1)T(n−1)=n2−(n−1)2
nT(n)=(n+1)T(n−1)+2n−1
nT(n)n(n+1)=(n+1)T(n−1)n(n+1)+2n−1n(n+1)
T(n)(n+1)=T(n−1)n+2n−1n(n+1)
S(n)=T(n)(n+1)⟶S(n)=S(n−1)+2n−1n(n+1)
S(n)=S(n−1)+θ(1n)
S(n)=θ(lgn)
T(n)=θ((n+1)lgn)=θ(nlgn)
T(n)(n+1)=T(n−1)n+2n−1n(n+1)
S(n)=T(n)(n+1)⟶S(n)=S(n−1)+2n−1n(n+1)
S(n)=S(n−1)+θ(1n)
S(n)=θ(lgn)
T(n)=θ((n+1)lgn)=θ(nlgn)
ارسال: #۳
RE: رابطه بازگشتی
تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
بقیه راه حل کاملا مشخص .ممنون
T(n)=2n∑n−1q=0T(q)+n
ارسال: #۴
RE: رابطه بازگشتی
ارسال: #۵
RE: رابطه بازگشتی
(۰۷ دى ۱۳۹۵ ۰۸:۰۰ ب.ظ)arash691 نوشته شده توسط:(07 دى ۱۳۹۵ ۰۷:۴۵ ب.ظ)Alirezaj نوشته شده توسط: تشکر فراوان .فقط یک سوال رابطه اول چطوری تبدیل به این رابطه شد؟
بقیه راه حل کاملا مشخص .ممنون
T(n)=2n∑n−1q=0T(q)+n
همون رابطه ی خودتو بازش کنی میفهمی
دقیقا همین کارو انجام دادم (با عدد گذاری ) ولی متوجه نشدم چطوری رابطه به این صورت شده!!!؟
۲
ارسال: #۶
RE: رابطه بازگشتی
سلام.
واسه قسمت اولش :
T(n)=1n∑nq=1T(q−1)+T(n−q)=1n[T(0)+T(n−1)+T(1)+T(n−2)+...+T(n−2)+T(1)+T(n−1)+T(0)]=1n[2T(0)+2T(1)+...+2T(n−1)]=2n[T(0)+...+T(n−1)]=2n∑n−1q=0T(q)
واسه قسمت اولش :
T(n)=1n∑nq=1T(q−1)+T(n−q)=1n[T(0)+T(n−1)+T(1)+T(n−2)+...+T(n−2)+T(1)+T(n−1)+T(0)]=1n[2T(0)+2T(1)+...+2T(n−1)]=2n[T(0)+...+T(n−1)]=2n∑n−1q=0T(q)