Para detectar duplicatas em uma lista de n dados, qual abordagem tem melhor complexidade média: comparar cada…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para detectar duplicatas em uma lista de n dados, qual abordagem tem melhor complexidade média: comparar cada par (O(n^2)) ou usar uma estrutura conjunto (hash) inserindo e verificando cada elemento?
- A) Comparar cada par é sempre mais rápido, pois evita os desafios dos conjuntos.
- B) Usar uma lista é melhor, pois é mais simples e clara para o programador.
- C) Usar um conjunto (hash) verificando presença durante inserção, com complexidade média O(n)
- D) Usar comparações em ordem crescente reduz a complexidade para O(n).
- E) Estruturas em árvore são sempre mais rápidas para verificar duplicatas que conjuntos.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Analise o problema. Temos uma lista de n elementos e queremos saber se existe algum valor repetido. A abordagem de comparar cada par testa todas as combinações de dois elementos, o que dá cerca de n(n-1)/2 comparações, ou seja, complexidade O(n^2).
- Analise a abordagem com conjunto (hash). Percorremos a lista uma vez. Para cada elemento, verificamos se ele já está no conjunto; se estiver, há duplicata; se não estiver, inserimos. Cada verificação e inserção em uma tabela hash tem custo médio constante, O(1), e como são n elementos, o custo médio total é O(n).
- Conclua. A alternativa C está correta, pois descreve exatamente essa estratégia, com complexidade média O(n), que é melhor que O(n^2) para listas grandes.
- Por que as outras estão erradas. A afirma que comparar pares é sempre mais rápido, o que é falso, pois o custo quadrático cresce muito mais rápido. B afirma que listas são melhores, mas a busca em lista é linear, o que mantém a complexidade quadrática. D afirma que ordenar reduz a complexidade para O(n), mas ordenar custa O(n log n) e a checagem depois disso exige mais passos. E afirma que árvores são sempre mais rápidas que conjuntos, o que é falso, pois a busca em hash tem custo médio O(1) enquanto a árvore balanceada tem O(log n).
💡 Dica: Compare as complexidades médias das abordagens apresentadas.
Alternativa por alternativa
Acredita que a simplicidade de comparar todos os pares compensa o custo, confundindo rapidez com ausência de estruturas auxiliares.
Por que engana: Confundir a complexidade de comparação de pares com a inserção em estruturas de conjunto, subestimando a eficiência do hash.
Supõe que a clareza do código de uma lista justifica o uso, sem perceber que a busca linear em lista mantém o custo quadrático.
Comparação par a par requer O(n^2). Um conjunto (hash) permite verificar/inserir cada elemento em tempo médio O(1), resultando em O(n) no total.
Imagina que ordenar ou comparar em ordem crescente elimina trabalho, sem considerar que a ordenação custa O(n log n) e que a comparação ainda precisa de n(n-1)/2 testes.
Confunde a ideia de estrutura hierárquica com desempenho, achando que árvores sempre superam conjuntos, quando a busca em hash é média O(1) e a árvore é O(log n).
Raio-X da questão
complexidade de algoritmos
avaliacao
complexidade de algoritmos · estruturas de dados
Revisar conceitos de complexidade de algoritmos e estruturas de dados.
Confundir a complexidade de comparação de pares com a inserção em estruturas de conjunto, subestimando a eficiência do hash.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para eliminar duplicatas de um vetor de n registros usando uma estrutura de busca baseada em hashing (conjunto), qual…
- Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar permite remover…
- Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
- Em um algoritmo que processa uma lista de alunos como dados e precisa evitar registros duplicados, qual estrutura de…
- Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
- Para detectar duplicatas em uma matriz de registros 'dados' onde cada registro tem uma chave 'id', qual estrutura de…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog