Alguém pode me avisar se minha compreensão do tempo de execução amortizado em uma lista de matriz dinâmica está correta?

Question

Estou bem no meu entendimento para o tempo amortizado para a inserção em uma lista de matriz dinâmica? (Meios dinâmicos Criar uma cópia dobrar seu tamanho e copiar elementos existentes para novo quando chegamos ao limite de tamanho atual). Por favor, valide minha explicação / compreensão.

Se inserirmos os elementos X em uma matriz do tamanho inicial 0, ele executará a operação dupla / cópia somente no número de inserção 1,2,4,8,16 ,.., X onde cada operação custa uma função de x f1 (x), f2 (x), etc.

Todas as outras operações de inserção, como 3,5,6,7,9,10,11, etc são O (1).

A função de X que eu mencionei acima é porque f1 (x) + f2 (x) + .. + fi (x)= 2x. onde eu é o número de inserções duplas / cópias.

Portanto, o tempo total de execução é O (2x + J.O (1)) onde J é o número de operações fáceis. (3,5,6,7, etc) Esta é a parte que eu quero verificar se o meu entendimento é certo ou não

Portanto, o tempo total é O (2x)= O (x)

Mas, como estamos procurando o tempo de inserir apenas um elemento, é O (x) / x= O (1)

Portanto, o tempo amortizado é O (1)

Última pergunta: por que é chamado amortizado? Onde eu durmo alguma coisa?

Obrigado !!

Answer 1

O custo de adicionar um item no final da matriz do tamanho N pode ser tão grande quanto o (n), mas geralmente é muito mais rápido. É por isso que usamos o termo "tempo amortizado". O trabalho que você fez para adicionar item # 512 paga de volta para itens 513 a 1023. É "amortizado".

O custo amortizado por itens é O (1), uma vez que o custo de adicionar n itens individualmente é O (n).

Existem várias razões pelas quais você precisa ser cuidadosamente com o custo amortizado: se você tiver um sistema em tempo real, onde tomar O (n) para adicionar um único item em casos raros, não é aceitável. Por exemplo, um sistema controlando os freios do seu carro que tem um custo amortizado de 0,001 segundos para usar os freios uma vez, mas cada 10.000 vezes leva 10 segundos vai te matar.

Há também uma diferença entre as operações individuais e combinando operações K. Se você tiver uma matriz classificada de n itens, e adicionar um item aleatório, mantendo o array classificado, que leva O (n). No entanto, se você quiser adicionar k itens todos de uma só vez, mantendo a matriz classificada, que leva o (n + k log k) (classificando os itens K primeiro, depois inserindo-os de uma só vez). É muitas vezes que as operações K podem ser feitas mais rapidamente do que fazer uma operação K Times.