Appunti lezione – Capitolo 4
Strutture di dati elementari
Alberto Montresor
19 Agosto, 2014
1
Domanda: espansione di un array, meglio aumentare o raddoppiare
Doubling In the first version, the initial size is 1 and the array is doubled whenever there is no free space
left. Let’s suppose to insert n elements to the array, and let ci be the cost of the i-th insertion:
i if ∃k : i = 2k + 1
ci =
1 otherwise
In other words, the cost is normally 1; but an insertion executed immediately after an insertion that has
exhausted the array (i.e. when the current size of the array is an exact power of 2) costs i, because we have
to copy the array in the new one.
Let’s consider the total cost of the n insertion:
C(n)
=
n
X
ci
i=1
blog2 nc
≤
n+
X
2j
j=0
Note that the first component (n) is given by the n “pure” insertions, while the second is given by the cost of
doubling. Simplifying the expression we get:
C(n) ≤ n + 2blog2 nc+1 − 1
≤ n + 2n
So the total cost for n insertions is bounded by 3n, which means that the amortized cost for each insertion is
constant.
Constant increment In this version, the array size is incremented by a constant amount d whenever the
space is exhausted. This means that:
i if i = 1 mod d
ci =
1 otherwise
1
Computing the total cost:
C(n)
=
n
X
ci
i=1
bn/dc
≤
n+
X
d·j
j=1
bn/dc
=
n+d
X
j
j=1
=
≤
=
(bn/dc + 1)bn/dc
2
(n/d + 1)n
n+
2
O(n2 )
n+d
This means that the total cost is O(n2 ), while the amortized cost for each insertion is O(n).
1.1
Conclusions
The ArrayList documentation says:
The capacity is the size of the array used to store the elements in the list. It is always at
least as large as the list size. As elements are added to an ArrayList, its capacity grows
automatically. The details of the growth policy are not specified beyond the fact that adding an
element has constant amortized time cost.
This means that ArrayList grows exponentially (note that growing factors different from 2 corresponds
to constant amortized time cost, but with different multiplicative constants).
2
Domanda: Rimozione di un elemento da una sequenza realizzata
tramite vettore
La rimozione deve essere effettuata in tempo O(n), in quanto tutti gli elementi successivi all’elemento
rimosso devono essere spostati di una posizione nell’array.
3
Domanda: Rimozione di un elemento da un array non ordinato
La rimozione può essere effettuata in tempo O(1): basta scambiare l’elemento da rimuovere con l’ultimo
elemento dell’array e far arretrare l’indice che punta all’ultimo elemento dell’array.
4
Domanda: Scelta fattore carico
1
2
per le rimozioni
Supponiamo di avere un tabella di dimensione n + 1 = 2k + 1 inserimenti; questo causa k espansioni; poi
di alternare le operazioni di inserimento I e di cancellazione C in quest’ordine:
C, C, I, I, C, C, . . .
Ogni due cancellazioni ed ogni due inserimenti assistiamo ad una contrazione ed ad un’espansione, ognuna
delle quale costa n. Il costo ammortizzato totale è O(n).
2