反復関係宿題の苦闘

Question

ここに質問があります：
T（1）= theta（1）を仮定すると、T（n）の拘束を求めることで再帰を解きます。

T(n) = T(n-6) + (n-3) + n 

= T(n-9) + (n-6) + (n-3) + n 

= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n] 

= T(1) + [0 + 3 + 6 + ... + n] 

= theta(1) = 3[1 + 2 + 3 + ... + n/3] 

= theta(1) + [(n/3)(n/3 + 1)]/2 

= theta(1) + (n^2+3n)/6 

私は解決策が再発に合うかどうかを確認するために二重にチェックすると、それは動作しません：ソリューションしようとしました

T(n) = n + T(n-3) 

。

Answer 1

問題はあなたが誤った合計を得ていたことでした。 最後のT関数がT（n - （n-1））だったので、前のT関数はT（n-（n-4））だったので、0から開始しません。したがって、合計は4で始まり、nまで上昇します。

この総和を見つける方法がわからない場合は、総和式の証明の一部を見ることをお勧めします。これがソリューションの外観です。

T(n) = T(n-3) + n 

= T(n-6) + (n-3) + n 

= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n] 

= T(1) + [4 + 7 + ... + n] 

= theta(1) + (4 + n) * (n - 1)/6