.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Analisi ammortizzata] Tabelle dinamiche (http://www.dsy.it/forum/showthread.php?threadid=24610)

Analisi ammortizzata - tabelle dinamiche.

Qualcuno sa qual è il costo ammortizzato triplicando la tabella dinamica quando è piena? Non riesco a trovare il limite di [sommatoria da j=0 a logaritmo in base 3 di n di 3^j]... magari manco è giusto.

Non so se ti serve ancora, cmq Torelli non chiede di solito dimostrazioni matematiche, ma che si capisca cosa succede. Quindi raccontaglielo a parole:

Ogni elemento deve avere un credito per il proprio inserimento e uno per spostarsi al primo incremento della tabella.
Quindi si parte da almeno due crediti.

Poi consideri una tabella di dimensioni "unitarie" che viene raddoppiata: Quindi vecchia tabella dimensione 1 e aggiunta dimensione 1 (totale 1+1=2, raddoppiata). Così ogni elemento ogni elemento deve preoccuparsi anche di vecchia/nuova elementi precedentemente inseriti. Se raddoppio 1/1 = 1. Risultato 2 (totale prec. di base) + 1 = 3 costo ammortizzato se raddoppio.

Se triplico vecchia/nuova= 1/2 -> costo amm. 2 + 1/2=2,5
Se quadruplico 1/3 -> 2,33..
and so on...

Ciao e in bocca al lupo se devi ancora sostenerlo.

__________________
There are two ways of constructing a software design:
one way is to make it so simple that there are obviously no deficiencies;
the other way is to make it so complicated that there are no obvious deficiencies.
(C.A.R. Hoare)