1

質問は次のとおり
です。T（1）= theta（1）の場合、T（n）のシータ限界を取得して漸化式を解きます。

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

試みられた解決策：

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

ソリューションが再発に適合するかどうかを再確認すると、機能しません。

4

1 に答える 1

1

問題は、間違った合計を取得していたことでした。最後のT関数はT（n-（n-1））であったため、0から始まりません。つまり、前の関数はT（n-（n-4））でした。したがって、合計は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
于 2011-01-29T22:54:57.107 に答える