Metodo dell'iterazione - Eq ricorrenza

[hamming_burst]

Salve,
vorrei chiedere se potreste controllare i passaggi che ho fatto per risolvere un'equazione di ricorrenza.
E' di un semplice algoritmo che ho creato, ma che devo allegare anche i calcoli di analisi, perciò è meglio che siano corretti.
Non capisco perchè con il Metodo dell'iterazione (sostituzioni successive) torna una limitazione superiore sbagliata, che invece con l'induzione è minore.

Equazione:

$T(n) = \{(O(1) if n=1),(O(1) if n=2),(T(n-2) + d if n>2):}$

con il metodo per tentativi si dimostra che che $T(n) in O(n)$ con le condizioni fissate.
Con l'iterazione, lasciando un attimo da parte le condizioni:

$T(n) = T(n-2) + d $
$= T(n-4) + 2d = T(n-6) + 3d = ..... = T(n-2k) + kd$ con $k=n/2$
$=T(0) + kd$


perciò generalizzando con le condizioni:

$sum_{k=1)^((n/2)-2) n-2k = (sum_{k=1)^{((n/2)-2)} n) - 2*(sum_{k=1)^{(n/2)-2} k) = n^2/2 - 2n - n^2/4 - 3n/2 + 2 = n^2/2 -7/2 n + 2 + kd$

Si può dimostrare che $n^2/2 -7/2 n + kd in O(n^2)$ ma che è sbagliato, o che ho lasciato da parte qualcosa, qualcuno potrebbe controllare i passaggi della ricorsione e dirmi se sono corretti.
I calcoli della sommatoria dovrebbero essere corretti, solo l'iterazione non so se è corretta.

Ringrazio chi aiuta

[Deckard1]

A me pare tu abbia commesso un errore nella fase "generalizzando le condizioni": perchè sommi $n-2k$?
È come se tu sommassi $n/2$ volte la dimensione dell'input, invece devi sommare solamente il tempo impiegato ad ogni chiamata ricorsiva che è $d$.

[hamming_burst]

Ah è li problema?
Pensavo fosse nell'applicazione della ricorsione, cioè che bisognasse arrivarea T(2) che è O(1) (secondo l'equazione), e non a T(0).

Perciò, la sommatoria come viene? se non sommo su $k$ cosa sommo su $d$?

cioè:

$sum_{k=1}^{(n/2)-2} d = ((n/2)-2)*d$

ma non mi torna qualcosa però anche se torna complessità corretta.

[Deckard1]

"ham_burst":Ah è li problema?
Pensavo fosse nell'applicazione della ricorsione, cioè che bisognasse arrivarea T(2) che è O(1) (secondo l'equazione), e non a T(0).

Non preoccuparti mai dei T(1), T(2) o T(0): sono solo delle costanti che possono essere aggiunte o sottratte senza mutare la complessità dell'algoritmo. Infatti si può benissimo dire che $d>=T(2), d>=T(1)$ e utilizzare d senza più stare a considerare T(2) o T(1) (se vogliamo essere proprio puntigliosi si prende un'altra costante d' e la si pone maggiore di d e di T(1) e T(2) e si usa quella e amen). Ciò non si può fare in combinatoria, dove per esempio se definiamo nella successione di Fibonacci $F(1)=3$, beh, non abbiamo più la serie di Fibonacci. Ma nel nostro caso non è così. Quindi mai dare la colpa agli "estremi" della ricorsione, perchè loro non vanno mai ad impattare la complessità finale.

Perciò, la sommatoria come viene? se non sommo su $k$ cosa sommo su $d$?

Sì, perchè tu ad ogni chiamata ricorsiva esegui delle operazioni che ti costano un tempo d. Ne fai circa $n/2$ di queste operazioni e quindi la complessità è $(n/2)*d$ e quindi $O(n)$.

[hamming_burst]

grandiso, mi hai fatto notare pure una cosa che non mi era mai tanto chiara di questo metodo, che ho praticamente sempre evitato per la parte finale con T(1) ecc.

Adesso, con questa sommatoria, torna anche il significato dell'algoritmo.

ah, ultima cosa, per scrivere bene l'iterazione, k rimane?

al passo ultimo, viene così:

$T(2) = O(1) + kd$

o

$T(2) = O(1) + d$

[Deckard1]

Lieto di esserti stato d'aiuto.
Ora capisco perchè leggendo i tuoi interventi sul forum ti vedevo sempre imbatterti in noiose dimostrazioni per induzione*

*il principio d'induzione mi piace, sia chiaro, ma quando bisogna stare a considerare 5 costanti per risolvere un'eq. che con altri metodi può essere risolta banalmente, beh, non ne vale la pena imho.

"ham_burst":ah, ultima cosa, per scrivere bene l'iterazione, k rimane?

al passo ultimo, viene così:

$T(2) = O(1) + kd$

o

$T(2) = O(1) + d$

Mmm.. k di certo non rimane, è solo un indice nella serie, ma il tempo di calcolo per ogni chiamata è sempre costante, non dipende dal n° di chiamate precedentemente eseguite quindi k non considerarlo proprio.
Però non ho capito perchè porre $T(2) = O(1) + d$ che è ancora uguale a $O(1)$ dopotutto. Piuttosto metti $T(2)<=d$ e sommi anche lui nella tua serie, però sono cose semplicemente irrilevanti.

[hamming_burst]

"Deckard":
Mmm.. k di certo non rimane, è solo un indice nella serie, ma il tempo di calcolo per ogni chiamata è sempre costante, non dipende dal n° di chiamate precedentemente eseguite quindi k non considerarlo proprio.
Però non ho capito perchè porre $T(2) = O(1) + d$ che è ancora uguale a $O(1)$ dopotutto. Piuttosto metti $T(2)<=d$ e sommi anche lui nella tua serie, però sono cose semplicemente irrilevanti.

perfetto, è solo che cerco di essere formalmente corretto. Grazie.

"Deckard":Lieto di esserti stato d'aiuto.
Ora capisco perchè leggendo i tuoi interventi sul forum ti vedevo sempre imbatterti in noiose dimostrazioni per induzione*

*il principio d'induzione mi piace, sia chiaro, ma quando bisogna stare a considerare 5 costanti per risolvere un'eq. che con altri metodi può essere risolta banalmente, beh, non ne vale la pena imho.

è hai detto bene
bisogna adattarsi in qualche modo con quello che si impara, l'iterazione ciò provato più volte, ma non mi torna sempre.
Tipo se invece che una costante ci fosse $f(n)$ io vado di albero di ricorsione (che alla fine è lo stesso metodo), è qualcosa che mi fa ragionare meglio, e alla fine una belle induzione per dimostrare il tutto

Sai che c'è una vecchia storiella: "che gli informatici, sono dei matematici che sanno dimostrare solo per induzione. Questo non è vero, sanno anche dimostrare per assurdo"

comunque grazie