Oi Bruno,
Quanto maior o número de elementos, mais próximo do tempo constante amortizado estaremos?
Legal você ter perguntado!
O custo amortizado é constante mesmo, não importando o número de operações add().
Considere uma sequência de operações add() em um vetor redimensionável utilizando a política de redimensionamento "encheu, dobre o vetor, copie tudo, segueg o jogo".
Vamos utilizar a metáfora contábil.
Na metáfora contábil cada $1 paga por uma quantidade constante de tempo consumido.
Cada add() tem custo amortizado de não mais do que $3.
De fato. Dê $3 a cada item inserido no vetor.
O item paga $1 ao add() pelo gasto de inseri-lo no vetor e guarda $2 para um possível futuro redimensionamento. Se esse possível redimensionamente ocorrer o item paga $1 pela sua cópia para o novo vetor e paga $1 pela cópia de um item que está na "metade inferior" do vetor e não tem dim-dim $.
A tabela abaixo "comprova" essa argumentação:
t representa o tamanho do vetor.custo é o custo real da operação.crédito é quanto o item recebe para pagar a operação.saldo é a soma dos custo até o momento menos o créditos recebidos pelos itens até o momento- relação invariante fundamental:
saldo >= 0
Da relação fundamental concluímos que o custo por n operações add() é não superior a $3n e portanto o custo médio (amortizado) de cada operação é não superior a $3.
| 1 |
1 |
1 |
$3 |
$2 |
| 2 |
2 |
1 + 1 |
$3 |
$1 |
| 3 |
4 |
1 + 2 |
$3 |
$1 |
| 4 |
4 |
1 |
$3 |
$3 |
| 5 |
8 |
1 + 4 |
$3 |
$2 |
| 6 |
8 |
1 |
$3 |
$4 |
| 7 |
8 |
1 |
$3 |
$6 |
| 8 |
8 |
1 |
$3 |
$8 |
| 9 |
16 |
1 + 8 |
$3 |
$2 |
| 10 |
16 |
1 |
$3 |
$4 |
| 11 |
16 |
1 |
$3 |
$6 |
| ... |
16 |
1 |
$3 |
$16 |
| 17 |
32 |
1 + 16 |
$3 |
$2 |
| 33 |
64 |
1 + 32 |
$3 |
$2 |