Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de 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
Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de cada elemento em tempo amortizado constante por atualização. Qual a complexidade temporal assintótica em função de n?
- A) Complexidade O(n log n) devido ao uso de dicionários.
- B) A complexidade temporal é O(n!) para cada elemento.
- C) A complexidade é constante, O(1).
- D) O(n)
- E) A complexidade temporal é O(n²).
✅ Resposta correta: alternativa D
Resolução passo a passo
- O algoritmo percorre uma lista de n elementos, o que exige pelo menos n iterações, uma para cada elemento.
- Em cada iteração, a atualização do dicionário/hashtable é feita em tempo amortizado constante, ou seja, cada atualização custa O(1) em média.
- Assim, o custo total é a soma de n operações de custo constante, resultando em n * O(1) = O(n).
- A alternativa D (O(n)) está correta e coincide com o gabarito oficial.
- A alternativa A está errada, pois o log n não aparece: o custo por atualização é constante amortizado, não logarítmico como em uma árvore balanceada.
- A alternativa B está errada, pois O(n!) corresponde a enumerar todas as permutações, o que não ocorre em uma simples varredura.
- A alternativa C está errada, pois O(1) seria o custo de uma única operação, mas o algoritmo realiza n operações.
- A alternativa E está errada, pois O(n²) exigiria comparações aninhadas entre todos os pares de elementos, o que não é descrito no enunciado.
💡 Dica: Considere a relação entre o número de elementos e as operações realizadas.
Alternativa por alternativa
O aluno associa o uso de dicionários a estruturas de busca balanceadas, que trabalham com O(log n), e ignora que a hashtable tem acesso médio constante.
Por que engana: Confundir a complexidade de atualização em dicionários com a complexidade total do algoritmo, levando a uma escolha errada.
O aluno confunde a varredura de uma lista com a geração de todas as permutações dos elementos, o que cresce fatorialmente.
O aluno considera apenas o custo de uma atualização e esquece que o algoritmo repete essa operação para todos os n elementos.
Cada um dos n elementos é processado exatamente uma vez e cada atualização no dicionário leva tempo amortizado O(1), portanto o tempo total cresce linearmente com n.
O aluno supõe que há comparações aninhadas entre todos os elementos, como em um laço duplo, quando o enunciado descreve apenas uma passagem pela lista.
Raio-X da questão
complexidade temporal
avaliacao
complexidade temporal · análise de algoritmos
Revisar conceitos de complexidade de algoritmos e estruturas de dados.
Confundir a complexidade de atualização em dicionários com a complexidade total do algoritmo, levando a uma escolha errada.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Ao processar n registros e contar a frequência de um campo usando um dicionário (map) com acesso esperado O(1), qual é a…
- Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar permite remover…
- Para eliminar duplicatas de um vetor de n registros usando uma estrutura de busca baseada em hashing (conjunto), qual…
- Para detectar duplicatas em uma lista de n dados, qual abordagem tem melhor complexidade média: comparar cada par…
- Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
- Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
🔎 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