Para eliminar duplicatas de um vetor de n registros usando uma estrutura de busca baseada em hashing…

Questão

Para eliminar duplicatas de um vetor de n registros usando uma estrutura de busca baseada em hashing (conjunto), qual complexidade média se espera para o processo?

1. A) O(1) — sempre serão necessárias operações mínimas para eliminar duplicatas.
2. B) O(log n) — a complexidade é proporcional ao logaritmo do número de registros.
3. C) O(n log n) — precisamos ordenar o vetor antes de eliminar duplicatas.
4. D) O(n) em média — cada inserção/verificação é amortizada O(1).
5. E) O(n²) — como cada elemento deve ser comparado com todos os outros.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. Um conjunto baseado em hashing (tabela hash) permite verificar se um registro já existe e inseri-lo em tempo médio constante, ou seja, O(1) por operação.
2. Como o vetor tem n registros, percorremos cada um uma única vez, fazendo uma verificação e possivelmente uma inserção no conjunto para cada um.
3. Logo, o custo total médio é n vezes O(1), resultando em O(n) em média. Isso corresponde à alternativa D, que é também o gabarito oficial.
4. A alternativa A está errada porque O(1) é o custo de uma única operação, não do processo inteiro, que envolve n registros.
5. A alternativa B está errada porque O(log n) é típico de estruturas como árvores balanceadas, não de tabelas hash com acesso médio constante.
6. A alternativa C está errada porque ordenar antes exigiria O(n log n), mas o uso de hashing dispensa a ordenação.
7. A alternativa E está errada porque comparar cada elemento com todos os outros seria a abordagem ingênua, que o hashing evita.
8. Observação: a complexidade média assume boa distribuição das chaves e função hash adequada; no pior caso, colisões podem degradar a operação para O(n) por inserção, levando a O(n²) no total, mas isso não é o caso médio esperado.

💡 Dica: Considere as propriedades de estruturas de dados e suas complexidades.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Para detectar duplicatas em uma lista de n dados, qual abordagem tem melhor complexidade média: comparar cada par…
• Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar permite remover…
• Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
• Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de cada elemento em…
• Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
• Em um algoritmo que deve verificar rapidamente se um código de estudante já existe em uma grande coleção de dados, qual…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.