Rezidivbeziehung Hausaufgabenkämpfe

Question

Hier ist die Frage:
Lösen Sie das Rezidiv, indem Sie eine Theta erhalten, die für t (n) gegründet wird, da t (1) = Theta (1).

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

Versuchslösung:

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

Wenn ich überprüfen, ob die Lösung zum Wiederauftreten passt, funktioniert sie nicht.

Answer 1

Das Problem war, dass Sie die falsche Zusammenfassung erhalten haben. Es beginnt nicht bei 0, da Ihre letzte T-Funktion T (n-(n-1)) war, was bedeutet, dass die vorherige T (n- (n-4)) war. Die Zusammenfassung beginnt also um 4 und geht bis n hoch.

Wenn Sie nicht wissen, wie Sie die Summierung davon finden, würde ich vorschlagen, einige der Beweise aus der Summationsformel anzusehen. So sieht die Lösung aus.

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