Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — FGV 2021
Algoritmos e Estrutura de Dados›Complexidade de Algoritmos
Código
fg046243
Banca
FGV
Órgão
Banestes
Ano
2021
Nível
Superior
João pretende armazenar uma coleção de dados referentes a cerca de um milhão de pessoas. Cada pessoa tem como chave de acesso um número inteiro sequencial, que não se repete.Empregando uma estrutura de Tabela Hash, João conseguiria obter, praticamente, acesso com complexidade:
AO(1)
BO(log N)
CO(N)
DO(N log N)
EO(N²)
Revelar gabarito e comentário▾
GabaritoA — O(1)
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Tabela Hash e complexidade de acesso
Gabarito: letra A (O(1)). Em uma tabela hash bem projetada, a operação de busca (acesso) tem complexidade média constante O(1), independentemente do número de elementos N. Isso é possível porque a função hash mapeia diretamente a chave a um índice do vetor subjacente, permitindo acesso imediato ao elemento.
A banca testa o conhecimento sobre a eficiência típica da tabela hash, contrastando com outras estruturas. O termo “praticamente” indica que estamos considerando o caso médio, não o pior caso (que poderia ser O(N) em caso de muitas colisões).
Alternativa A — ✅ Correta ⟵ GABARITO
A complexidade O(1) (tempo constante) é a característica marcante das tabelas hash quando a função hash é bem distribuída e as colisões são resolvidas de forma eficiente (ex.: encadeamento ou endereçamento aberto com boa dispersão). A cada consulta, a posição do elemento é calculada pela chave, exigindo apenas um número fixo de operações.
Alternativa B — ❌ Incorreta
O(log N) é a complexidade típica de buscas em árvores balanceadas (ex.: árvore AVL, árvore rubro-negra) e em buscas binárias em vetor ordenado. Não corresponde ao comportamento de uma tabela hash.
Alternativa C — ❌ Incorreta
O(N) (linear) seria o desempenho de uma busca sequencial em uma lista ou vetor não ordenado. Em tabela hash, O(N) ocorre apenas no pior caso (todas as chaves colidindo), mas a questão fala em “praticamente”, que é o caso esperado.
Alternativa D — ❌ Incorreta
O(N log N) é comum em algoritmos de ordenação eficientes (mergesort, heapsort) ou em buscas combinadas com ordenação. Não se aplica à operação de acesso em hash.
Alternativa E — ❌ Incorreta
O(N²) é típico de algoritmos de ordenação quadráticos (bubblesort) ou de loops aninhados. Totalmente fora do contexto de uma tabela hash.
PEGA ESSA DICA!
Grave as complexidades típicas das principais estruturas de dados: