Equazione di ricorrenza

[Darèios89]

[tex]T(n)=T(n-2)+n^2[/tex]

Come la risolvereste? Avrei pensato con l' albero ma tanto poi dovrei provarla per sostituzione, forse sarebbe meglio fare qualche sostituzione e poi applicare il telescoping.

[tex]n=2k[/tex]

Diventa:

[tex]T(2k)=T(2k-2)+(2k)^2[/tex]

[tex]\frac{T(2k)}{2k}=\frac{T(2(k-1))}{2k}+2k[/tex]

Ora dovrei fare una sostituzione in modo che la prima parte della ricorrenza diventi nella forma [tex]S(m-1)[/tex] ma non riesco, avrei pensato a:

[tex]\frac{T(2k)}{2k}=S(m)[/tex]

Ma così non ottengo ciò che voglio.

[hamming_burst]

Ciao,
qual è stato il fattore che ti ha fatto sciegliere una sostituzione di variabile di $2k$? non ne vedo vantaggi...anzi ti complichi la vita inutilmente.

Al massimo avrei sosituito con: $k=n^2\ ,\ sqrt(k) = n$ ricordandosi che lavoriamo con $ZZ^+$

prova così.

[yoshiharu]

[quote=Darèios89][tex]T(n)=T(n-2)+n^2[/tex]

Come la risolvereste?
[quote]

Quello che ho tovato io e':

Posto

[tex]T(n) = a n^3 + b n^2 + c n + d[/tex]

si ricava:

[tex]T(n) = \frac{n}{6}^3 + \frac{n}{2}^2 + \frac{n}{3} + d[/tex]

d si ricava da una qualche condizione iniziale.

bye^2, mr

[hamming_burst]

Quello che ho tovato io e':

Posto

[tex]T(n) = a n^3 + b n^2 + c n + d[/tex]

si ricava:

[tex]T(n) = \frac{n}{6}^3 + \frac{n}{2}^2 + \frac{n}{3} + d[/tex]

d si ricava da una qualche condizione iniziale.

bye^2, mr

penso che te hai risolto un'equazione di Complessità, non un'equazione di ricorrenza, con questo metodo.
Che procedimento hai adottato per dire "posto..." per curiosità

[yoshiharu]

"ham_burst":

Posto

[tex]T(n) = a n^3 + b n^2 + c n + d[/tex]

si ricava:

[tex]T(n) = \frac{n}{6}^3 + \frac{n}{2}^2 + \frac{n}{3} + d[/tex]

d si ricava da una qualche condizione iniziale.

penso che te hai risolto un'equazione di Complessità, non un'equazione di ricorrenza, con questo metodo.
Che procedimento hai adottato per dire "posto..." per curiosità

In effetti oltre alla notazione "con la O maiuscola" non so molto della Complessita'...my bad...
No, io ho risolto l'equazione di ricorrenza, nel senso di "analisi I" del termine.
Il ragionamento e' sulla forma della equazione. Ogni termine della serie si ricava dal precedente aggiungendo una funzione polinomiale (diciamo in un caso un po' piu' generale). Se scrivi per esteso i primi 2-3 termini, vedi che si tratta di somme di potenze di $N$, cioe' un polinomio in $N$, devi solo capire qual e' il termine dominante, i coefficienti si ottengono nel modo piu' semplice (sost. diretta).

Poi puo' sempre darsi che abbia sbagliato qualche conto, e che sia una minchiata, eh...

bye^2, mr