segunda-feira, 15 de julho de 2013

Comparação entre listas estáticas e dinâmicas

Estática
Vantagens
● acesso a qualquer elemento com custo O(1), porque os elementos já tem indexação direta
● melhor uso do espaço: só armazena os dados
● não usa apontadores
– implementação mais simples
– menos sujeita a erros

Desvantagens
● custo elevado para inserções e retiradas em qualquer posição: O(n) (porque para inserir numa posição que não seja a última, é preciso deslocar todos os elementos para liberá-la e para retirar, é preciso retornar todos os elementos uma posição)
● redimensionamento é difícil e caro, quando possível - a função realloc() é muito cara.

Dinâmica
Vantagens
● alterar o tamanho da lista é simples
● inserção e retirada têm custo O(1) quando é apontado o item a ser retirado
● não necessita deslocar elementos

Desvantagens 
● acesso aos elementos é apenas seqüencial
● ocupa mais espaço para armazenar o mesmo número de itens
● uso de apontadores

● implementação mais sujeita a erros

Critérios para a escolha da melhor estrutura
Acesso: como será o acesso aos elementos?
– sempre seqüencial, sempre aleatório?

Número de elementos a ser armazenado
– é conhecido? é previsível? ou não?

Inserções e retiradas
– há muitas inserções e retiradas?
– onde são: no início? no fim? posições variáveis?

Demais operações a serem realizadas
– quais são? busca? máximo ou mínimo?
– pesquisa conjugada com inserção? ordenação eventual ou freqüente?
– retornar o elemento de uma posição específica?
– o custo de todas as operações deve ser analisado em relação a sua freqüência

Espaço ocupado

– há restrições? são muitos dados? dados cabem na memória?

Nenhum comentário:

Postar um comentário