(۲۶ شهریور ۱۳۹۱ ۱۲:۱۲ ب.ظ)mahtab_rafiei نوشته شده توسط: t(1)=0
t(n)=t(n-1)+n/2
دوستان اگه ممکننه حل دقیق بدین،یجا با جایگذاری حل کرده اما من متوجه نمیشم
روش جایگذاریش به این شکله:
[tex]t(n)=t(n-1) \frac{n}{2}=t(n-2) \frac{n-1}{2} \frac{n}{2}=...=t(n-(n-1)) \frac{n-(n-2)}{2} \frac{n-(n-3)}{2} ... \frac{n-1}{2} \frac{n}{2}=t(1) \frac{2}{2} \frac{3}{2} \frac{4}{2} ... \frac{n-1}{2} \frac{n}{2}=0 \frac{1}{2}(2 3 4 5 ... (n-1) n)=\frac{1}{2}(\frac{n(n 1)}{2}-1)=\frac{n(n 1)}{4}-\frac{1}{2}[/tex]
(۲۶ شهریور ۱۳۹۱ ۱۲:۱۲ ب.ظ)mahtab_rafiei نوشته شده توسط: t(1)=0
t(n)=t(n-1)+2/n
الانم که تغییر دادین روش حل زیاد فرقی با بالا نداره شکل آخرشو مینویسم:
[tex]t(n)=t(n-1) \frac{2}{n}=t(1) 2(\frac{1}{2} \frac{1}{3} ... \frac{1}{n})=0 2(1-1 \frac{1}{2} \frac{1}{3} ... \frac{1}{n})=2(1 \frac{1}{2} \frac{1}{3} ... 1/n)-2=2(lnn O(1))-2[/tex]
میدانیم سری هارمونیک برابر است با:
[tex]\sum_{i=1}^{n}\frac{1}{i}=lnn O(1)[/tex]
