Contatore Binario con Increment
Sia
1101011
Increment(A)
i = 0
while (i<k) && A[i]=1 do:
A[i] = 0
i++
if (i<k) then:
A[i] = 1
Costo di un’incremento:
Anche in questo caso c’è un’analisi sovrabbondante.
Il contatore è inizialmente nullo a meno che non venga specificato altrimenti
Contatore Binario con Aggregazione
Supponiamo che esistano due operazioni:
E che il contatore sia inizialmente nullo.
Notiamo che su
cambia volte, indica il bit del pari/dispari. cambia volte, cioè una volta sì e una no. cambia volte, ogni 4 volte. cambia volte. - …
cambia volte.
Otteniamo:
Abbiamo tolto il floor ponendo la serie senza floor maggiore o uguale a quella con il floor, e sostituito k-1 con
Contatore Binario con Accantonamenti
Poniamo:
Un’operazione di
Per cui vale:
Ossia
Contatore Binario con Potenziale
Sia
Stiamo rispettando la disuguaglianza
Di nuovo, il costo ammortizzato è:
Si ha perciò:
Nota Bene:
Pertanto:
Da cui:
Contatore binario con incremento inizialmente non nullo
Poniamo come prima
Otteniamo il valore del costo reale:
Dove k è il numero di bit nel contatore.
Se
Troveremo che il numero di bit k si palesa anche utilizzando negli altri metodi, nel caso di contatore non nullo.