質問
これが質問です:
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
解決策が再発に適合するかどうかを再確認するとき、それは機能しません。
解決
問題は、あなたが間違った合計を取得していることでした。最後の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
所属していません StackOverflow