GabaritoA — O(1).
Gabarito: letra A. Em uma tabela hash com função hash uniforme e carga balanceada, o tempo médio de busca é constante, ou seja, O(1). Isso ocorre porque a função hash mapeia a chave diretamente para um índice, e o fator de carga controla o número médio de colisões, mantendo a operação com custo fixo no caso médio.
A banca testa o conhecimento básico da estrutura de dados hash, contrastando-a com outros algoritmos de busca. Vamos analisar cada alternativa:
O(1) é a complexidade média da busca em uma tabela hash bem projetada. Mesmo com colisões, o tratamento adequado (como encadeamento ou endereçamento aberto) mantém a operação constante em média, desde que o fator de carga seja baixo e a função hash distribua bem as chaves.
O(n) corresponde à busca linear em uma lista ou vetor não ordenado, ou ao pior caso de uma tabela hash (quando todas as chaves colidem). Não é a complexidade média da hash bem construída.
O(log n) é a complexidade de busca binária em um vetor ordenado ou de operações em árvores balanceadas (como AVL ou Rubro-Negra). Não representa a busca em hash, que não depende de ordenação.
O(n log n) é típico de algoritmos de ordenação eficientes (merge sort, heap sort) ou de operações em algumas estruturas de dados avançadas. Não se aplica à busca em tabela hash.
A alternativa C (O(log n)) pode confundir candidatos que associam busca apenas a árvores balanceadas. Lembre-se: hash resolve em tempo constante médio – a compensação é que não há ordem entre os elementos.
Gabarito: letra A.
Link permanente: /questoes/qg303887