Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

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.

puntozip

User info:

Registered: Jan 2003
Posts: 332 (0.04 al dì)
Location: milano
Corso: Ticom
Anno: 1
Time Online: 10 Days, 4:57:16 [...]
Status: Offline

Post actions:

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)