Compreender e Calcular o Custo Amortizado das Operações de Array Dinâmico

Arrays dinâmicos são estruturas de dados que automaticamente redimensionam quando atingem a capacidade. Compreender seu custo amortizado ajuda a avaliar sua eficiência em várias operações.

O que é Custo Amortizado?

O custo amortizado é o custo médio por operação em uma sequência de operações. Alivia os altos custos de redimensionamento ocasional, distribuindo-os em muitas operações baratas.

Operações de Array Dinâmico

Operações comuns em arrays dinâmicos incluem inserção, exclusão e redimensionamento. A inserção no final é tipicamente a operação mais frequente, que pode desencadear redimensionamento quando a capacidade é excedida.

Calculando o Custo Amortizado

Ao inserir elementos, o array duplica em tamanho quando cheio. O custo de redimensionamento envolve copiar todos os elementos existentes para o novo array. Embora redimensionar seja caro, ocorre pouco frequentemente.

Por exemplo, se um array começa com capacidade 1, a sequência de redimensionamento de custos sobre múltiplas inserções pode ser resumida como:

• Inserir 1 elemento: custo 1
• Inserir 2o elemento: redimensionar (custo 1), custo total 2
• Inserir o terceiro elemento: redimensionar (custo 2), custo total 3
• Inserir o 4o elemento: redimensionar (custo 4), custo total 4

O custo total sobre n inserções é proporcional a 2n, tornando o custo amortizado por inserção aproximadamente O(1).