O tempo amortizado é a forma de expressar a complexidade de tempo quando um algoritmo tem a muito má complexidade de tempo apenas de vez em quando, além da complexidade de tempo que acontece na maior parte do tempo. Um bom exemplo seria uma ArrayList que é uma estrutura de dados que contém um array e pode ser estendida. Outra definição do Stack Overflow é o tempo médio gasto por operação, se você fizer muitas operações.
Quando o ArrayList atinge a capacidade do array nele, então ele cria um novo array com o tamanho dobrado do array antigo e copia todos os itens do array antigo para o novo array. No ArrayList, existem duas complexidades de tempo; uma é O(1) e a outra é O(n).
Quando o array nele não atingiu sua capacidade e ainda tem espaço suficiente para inserir itens
Para inserir um item no array neste caso, nós só precisamos colocar o item após o último item. Ainda temos espaço para inserir itens.
Quando o array nele tiver atingido sua capacidade e precisar se recriar com o dobro do tamanho
O array atingiu a capacidade e não temos slots disponíveis. Então precisamos de criar um novo array com o tamanho dobrado. E depois copiar os itens do antigo para o novo, que leva O(n) onde n é a capacidade do antigo array e o pior caso.
Para expressar estas duas complexidades de tempo, o tempo amortizado está aqui. O que ele faz é nos deixar descrever o pior caso que acontece de vez em quando cada vez que a matriz interna atinge sua capacidade.
Mas um caso que acontece, não acontecerá novamente por tanto tempo que o custo seja “amortizado”. (Cracking the Coding Interview 6th edition 43)
So como descrevemos as duas complexidades?
No caso da ArrayList, podemos dizer que
A inserção leva O(n) quando a capacidade foi atingida, e o tempo amortizado para cada inserção é O(1).
But let’s be accurate for the worst time complexity without simplifying this time. Se a capacidade da matriz interna começa com 1, então as capacidades serão 1, 2, 4, 8, 16… X quando atingir a capacidade e for duplicada. É preciso 1, 2, 4, 8, 16… X itens para copiar para o novo array, dependendo da capacidade que foi atingida. Então a complexidade de tempo será 1 + 2 + 4 + 8 + 16 +… X. Se você pensar de X, este será X + X/2 + X/4 + X/8… + 1 = 2X aproximadamente. Então em outras palavras com precisão,
A inserção leva O(2X) quando a capacidade de X foi alcançada, e o tempo amortizado para cada inserção é O(1).
