João está trabalhando com uma base de dados que contém centenas de milhares de registros de pessoas, na qual a chave de busca é o CPF. Nesse contexto, o algoritmo/método de busca que, corretamente empregado, oferece a melhor complexidade é:
- A)Árvore B;
Árvore B é eficiente em bases grandes, mas é mais indicada para armazenamento em disco e não supera a tabela hash em busca por chave em memória.
- B)Bitmap;
Bitmap serve para representar conjuntos de bits e não é a estrutura adequada para buscar registros por CPF em uma base cadastral.
- C)Busca binária;
Busca binária é rápida, mas depende de dados ordenados e ainda tem complexidade O(log n), pior que o acesso médio de uma hash.
- D)Lista encadeada;
Lista encadeada é a pior opção aqui, porque a busca normalmente é linear, com complexidade O(n).
- E)Tabela Hash.
Tabela hash é a melhor escolha para busca por chave única como CPF, com tempo médio O(1) quando bem implementada.
Gabarito: E
Quando a base tem centenas de milhares de registros e a chave de busca é um identificador bem definido, como o CPF, você quer um método que transforme a busca em algo muito rápido. A ideia é simples: em vez de “procurar olhando um por um”, o algoritmo usa uma estrutura que organiza o acesso pela própria chave, reduzindo bastante o tempo médio de pesquisa. Na prática, isso faz enorme diferença quando o volume de dados cresce. A tabela hash faz exatamente esse papel. Ela usa uma função de espalhamento para converter a chave do CPF em um índice, permitindo acesso, em média, em tempo constante, isto é, O(1). É por isso que, corretamente empregada, ela costuma ser a melhor escolha quando o objetivo principal é buscar pelo valor da chave, e não manter os dados ordenados. As outras opções parecem “sofisticadas”, mas não vencem nesse cenário. Árvore B é ótima para armazenamento em disco e bancos de dados, busca binária exige dados ordenados e ainda fica em O(log n), lista encadeada é lenta para busca e bitmap não é a estrutura adequada para localizar registros por CPF em uma base desse tipo. Aqui, a banca quer que você perceba o foco em busca rápida por chave única. Em termos doutrinários de estrutura de dados, a tabela hash é clássica para consultas por chave com alta eficiência média. O detalhe importante é esse: “corretamente empregado” significa também lidar bem com colisões e escolher uma boa função hash, porque sem isso o desempenho pode piorar bastante.