Porque é que a inserção na extremidade de uma matriz dinâmica ó (1) durante a inserção no meio é O (n)?

Question

De acordo com a Wikipedia em matrizes dinâmicas , inserção / supressão no final do matriz é o (1) durante a inserção / exclusão a partir do meio é o (n). Porque é exatamente isso?

também - se tenho uma matriz dinâmica com 5 elementos e inserir um novo elemento na posição 6, o funcionamento é O (n) enquanto que, se I utilizar a função de acréscimo para a extremidade da matriz é O (1) . Não é esta a mesma operação assumindo a matriz não precisa de redimensionamento em ambos os casos? Ou será que acrescentar à matriz dinâmica realmente inserir o novo elemento em algum lugar além posição 6?

Obrigado!

EDIT: Eu acho que a minha principal confusão é a diferença entre inserir no final da matriz e inserir em uma posição específica que é equivalente ao final da matriz.

Suponho que um ponteiro para o endereço de memória do fim da matriz é mantido acessível e é por isso que a operação de acréscimo é rápido. Por outro lado, se eu especificar uma posição precisa (mesmo que seja o fim do array) não vai saber que inserir nessa posição é o mesmo que usando o endereço de memória mencionada por isso tem que percorrer toda a matriz, eh?

Answer 1

A ordem de magnitude depende inteiramente de que tipo de dados estruturar a "matriz dinâmica" na verdade é ( "array dinâmico" não é uma estrutura de dados estritamente definido, é mais de um resultado desejado conseguido através do emprego de uma estrutura de dados especial ). O exemplo que você dá seria que refletem por uma matriz dinâmica alcançada pelo emprego de uma lista ligada. Somando-se o final poderia ser O (1), se a estrutura de lista mantido um ponteiro para o elemento final. Inserção (independentemente do índice) exigiria atravessando a lista ligada, o que significa uma operação por nó até o índice desejado.

Answer 2

Para inserir no final de um array, você simplesmente tem que colocar o item lá.

Para inserir no meio de uma matriz, você precisa mover os itens depois desse ponto até por um.

Para excluir a partir do final de um array, você simplesmente colocar a sua contagem por um.

Para excluir a partir do meio que você tem que fazer isso e mudar os outros itens para baixo.

É o deslocando que o transforma em O (n).

Answer 3

É muito simples:

A inserção no meio envolve mover cada elemento posterior ao longo de 1. Para inserir no final, se houver espaço adicional reservada, o item é apenas armazenados lá, mas se não for novo espaço é alocado. Assim, esta operação é feita em amortizado constante de tempo .

Answer 4

Adicionando a excelente resumo de Adam Robinson: Este não é apenas teoria. Eu vi qualquer número de situações em que uma matriz dinâmica foi construído por anexando várias vezes para o final do array. Isso funciona para o desempenho o(N**2), porque a matriz precisa repetidamente a atribuir-re, forçando cada um dos seus membros para ser copiado para a nova estrutura de matriz. A re-alocação pode acontecer apenas em 1/10 das operações Acrescentar, mas isso é ruim o suficiente, e ainda é o(N**2) em termos de performance.

Em STL, este penalidade de desempenho pode ser evitado chamando vector::reserve(N) antes de escrever para o vector; mas esse passo é muitas vezes esquecido.

Answer 5

Na verdade, não é Big-O, mas Big-Theta .