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
- Durante uma campanha de arrecadação, uma escola receberá alimentos e produtos de higiene para montar cestas destinadas a…
- Em um exercício de preparação para períodos de chuva intensa, uma central municipal de Defesa Civil precisa localizar…
- Em ações de fiscalização ambiental no Brasil, imagens de satélite podem ser comparadas em diferentes datas para indicar…
- Uma família criou um programa para organizar as compras do mês. O programa recebe os preços, soma os produtos e…
- — Sem conexão estável no rio, o alerta precisa aparecer no próprio tablet — afirmou a técnica que acompanha sons de aves…
- Falhas em formulários digitais de serviços públicos levaram um setor de tecnologia a testar cinco programas de análise…
🔎 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