Tabella Dinamica

Tabelle Dinamiche

Si tratta di tabelle soggette a riallocazione, per evitare overflow. Sia una tabella, poniamo: 

Definizioni Preliminari:

• Dimensione della tabella
• Numero degli elementi in T

(: Fattore di Carico) 

Skippiamo lo pseudocodice di e .

Analisi grossolana

Analisi di inserimenti su una tabella inizialmente nulla.

Abbiamo inserimenti. 

Il costo dell’inserimento   Perciò, il costo di un inserimento è , e il costo di inserimenti è

Con Metodo dell’Aggregazione

Inserimento	Costo Copia	Costo Inserimento
1	/	1
2	1()	1
3	2()	1
4	/	1
5	4()	1
6	/	1
7	/	1
8	/	1
9	8()	1
10	/	1
…	…	…

#todo , è improbabile siano presenti alla prima prova in itinere.