30

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 7keyboard_arrow_downkeyboard_arrow_up

Uma tabela dinâmica é uma tabela que continuamente muda seu tamanho quando necessário. Quando inserimos novos valores na tabela, a tabela aumenta de tamanho para abrigar o novo valor e quando deletamos algum valor a tabela diminui, liberando esse espaço. A mudança de tamanho da tabela é limitada a um certo valor, que é o valor de carga da tabela.

Passo 2 de 7keyboard_arrow_downkeyboard_arrow_up

Fator de carga em uma tabela é a razão entre o número de elementos na tabela dinâmica e o tamanho da tabela. Uma tabela hash é uma estrutura de dados usada para armazenar, inserir, deletar e verificar certos elementos nela contidos. Aqui, a usaremos para implementar uma tabela dinâmica.

Passo 3 de 7keyboard_arrow_downkeyboard_arrow_up

A implementação de uma tabela dinâmica utilizando uma tabela hash de endereçamento aberto é feita da seguinte maneira: quando um novo elemento está para ser inserido, ele é primeiramente verificado para saber se já está presente na tabela ou se existe espaço vazio para inseri-lo. O custo real de uma operação é o custo da operação isoladamente, e o custo amortizado é o custo médio para realizar todas as operações. Nossa preocupação é como fazer o custo amortizado ser .

Passo 4 de 7keyboard_arrow_downkeyboard_arrow_up

Tabelas hash devem ter um fator de carga estritamente menor do que 1 ou menor do que 100%, pois na medida que esse fator aumenta a complexidade também aumenta, e assim a tabela hash fica mais lenta. Nessa condição a busca e várias operações feitas na tabela correm o risco de falharem.

Passo 5 de 7keyboard_arrow_downkeyboard_arrow_up

A inserção acontece juntamente com uma função de busca. Esta operação é feita em tempo em média de , já que é uma busca linear. Mas essas operações devem ter um custo amortizado associado. Usando análise amortizada, vemos que o custo amortizado para inserir e deletar é somente , apesar do custo real da operação ser maior quando inicia uma expansão ou contração. Assim, o custo real é presumido ; e esse é o valor esperado por inserção.

Passo 6 de 7keyboard_arrow_downkeyboard_arrow_up

O espaço que não é usado em uma tabela dinâmica nunca excede uma fração constante do espaço total. O custo médio por instrução não é , pois a busca pode verificar todos os elementos da tabela hash para encontrar a resposta correta.

Passo 7 de 7keyboard_arrow_downkeyboard_arrow_up

Portanto, o custo real por instrução não é necessariamente pois a busca pode ter que verificar todos os elementos na tabela.

Navegar por capítulo

O passo a passo dos exercícios mais difíceis

12xR$ 29,90 /mêsCancele quando quiser, sem multa

E mais

  • check Videoaulas objetivas
  • check Resumos por tópicos
  • check Salve para ver depois
  • check Disciplinas ilimitadas
  • check Filtros exclusivos de busca