Flashcard FC377479
Qual a complexidade de tempo médio para busca por chave exata em uma tabela Hash com boa função de dispersão e carga controlada?
Algoritmos e Lógica de Programação
Instituto Consulplan · 2024
Qual a complexidade de tempo médio para busca por chave exata em uma tabela Hash com boa função de dispersão e carga controlada?
Mostrar resposta e comentário
Resposta
O(1).Explicação:
A função de hash calcula o índice em tempo constante para a chave.
Com fator de carga controlado \( \alpha = n/m \) e boa dispersão, o número esperado de elementos por balde é limitado.
Técnicas de tratamento de colisões e redimensionamento preservam a expectativa de custo de busca em \(O(1)\).
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/374709
Conteúdo do catálogo FC Concursos · Atualizado em