Le lotte Homework Ricorrenza relazioni
-
27-10-2019 - |
Domanda
Ecco la domanda:
Risolvere la ricorrenza ottenendo un theta diretto a T (n) dato che T (1) = theta (1).
T(n) = n + T(n-3)
tentata soluzione:
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
Quando si fa doppio controllo per vedere se la soluzione adatta la ricorrenza, non funziona.
Soluzione
Il problema era che si stavano diventando la somma sbagliata. Esso non inizia a 0, poiché la vostra ultima funzione T è T (n - (n-1)), il che significa che quello precedente era T (N- (n-4)). Quindi la somma inizia alle 4, e va fino al n.
Se non sai come trovare la somma di questo, suggerirei si guarda ad alcune delle prove della formula sommatoria. Questo è ciò che gli sguardi soluzione come.
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
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow