Ao processar n registros e contar a frequência de um campo usando um dicionário (map) com acesso esperado…
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
Ao processar n registros e contar a frequência de um campo usando um dicionário (map) com acesso esperado O(1), qual é a complexidade temporal esperada do algoritmo de contagem em função de n?
- A) Complexidade O(n log n) devido ao custo de atualizar o dicionário.
- B) Tempo linear esperado: O(n).
- C) Complexidade O(1) (tempo constante independentemente de n).
- D) Complexidade O(n^2) por causa de comparações entre registros.
- E) Complexidade O(log n) pois cada busca no dicionário é logarítmica.
✅ Resposta correta: alternativa B
Resolução passo a passo
- O algoritmo percorre cada um dos n registros uma única vez. Para cada registro, lê o valor do campo e atualiza a contagem no dicionário.
- Como o acesso (busca e atualização) ao dicionário é O(1) em média, cada atualização custa tempo constante, independentemente do tamanho do dicionário.
- Assim, o custo total é a soma de n operações de custo constante, ou seja, O(n) em tempo esperado, que é tempo linear.
- A alternativa A está errada, pois o log n só apareceria em estruturas de árvore balanceada, não em um dicionário com acesso O(1).
- A alternativa C está errada, pois o tempo não é constante, já que cresce com a quantidade de registros que precisam ser processados.
- A alternativa D está errada, pois não há comparações entre pares de registros; cada registro é processado independentemente.
- A alternativa E está errada, pois a busca em tabela hash com acesso O(1) não é logarítmica; o log n apareceria apenas em buscas binárias ou árvores.
- Conclusão: o gabarito B está correto, pois a complexidade temporal esperada é O(n).
💡 Dica: Considere uma atualização de custo esperado O(1) para cada um dos n registros.
Alternativa por alternativa
O aluno acredita que toda atualização em estrutura de dados custa O(log n), misturando o dicionário com árvores balanceadas ou com ordenação.
Cada um dos n registros é lido uma vez e realiza-se uma operação de leitura/atualização no dicionário em tempo constante esperado; portanto o custo total cresce linearmente com n.
O aluno confunde o custo de uma única operação no dicionário, que é O(1), com o custo total do algoritmo, que precisa processar todos os n registros.
O aluno imagina que contar frequências exige comparar cada registro com todos os outros, como em algoritmos de busca de pares, e não percebe que o dicionário evita essas comparações.
O aluno associa qualquer estrutura de busca ao tempo logarítmico, esquecendo que tabelas hash têm acesso médio constante.
Por que engana: Confundir o custo esperado O(1) de cada acesso ao dicionário com a complexidade total, ou supor que a contagem exige ordenar ou comparar todos os registros entre si.
Raio-X da questão
Complexidade temporal de contagem
avaliacao
Notação assintótica Big O · Operações em dicionários hash
Revise análise de complexidade e o custo esperado de operações em tabelas hash.
Confundir o custo esperado O(1) de cada acesso ao dicionário com a complexidade total, ou supor que a contagem exige ordenar ou comparar todos os registros entre si.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de cada elemento em…
- Para eliminar duplicatas de um vetor de n registros usando uma estrutura de busca baseada em hashing (conjunto), qual…
- Considere o pseudocódigo: for i from 1 to n: for j from 1 to n: if A[i] == A[j] then count ? count + 1. Qual é a…
- Se uma matriz n × n contém registros e um algoritmo compara cada par distinto de elementos para detectar duplicidade de…
- Em um programa que conta a frequência de palavras em um texto, qual estrutura de dados é mais adequada para associar…
- Ao projetar um algoritmo que conta ocorrências de palavras em um texto grande, qual estrutura de dados é mais eficiente…
🔎 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