Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — FGV 2026
Algoritmos e Estrutura de Dados›Complexidade de Algoritmos
Código
fg129174
Banca
FGV
Órgão
AMAZUL
Ano
2026
Nível
Superior
Cargo
Engenheiro de Computação
Um desenvolvedor precisa implementar um algoritmo de busca em uma estrutura de dados que armazena 1 milhão de registros ordenados. O requisito é encontrar um registro específico com o menor número de comparações possível.O algoritmo e a complexidade de tempo mais adequados são
Abusca linear com complexidade O(n)
Bbusca por saltos (Jump Search) com complexidade O(√n)
Cbusca por interpolação com complexidade O(1)
Dbusca em largura (BFS) com complexidade O(log n)
Ebusca binária com complexidade O(log n)
Revelar gabarito e comentário▾
GabaritoE — busca binária com complexidade O(log n)
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”.
Busca em dados ordenados: algoritmo e complexidade
Gabarito: letra E. Para uma estrutura de dados ordenada com 1 milhão de registros, o algoritmo de busca binária apresenta complexidade de tempo O(log n), sendo o mais eficiente entre os listados, pois reduz o espaço de busca pela metade a cada comparação. A busca linear (O(n)) é ineficiente para grandes volumes; jump search (O(√n)) é pior que a binária; interpolação tem caso médio O(log log n) mas pior caso O(n) e exige distribuição uniforme; BFS não se aplica a vetores ordenados.
A questão cobra o conhecimento das complexidades dos principais algoritmos de busca e a escolha do mais adequado para dados ordenados. A busca binária é o padrão-ouro nesse cenário, exigindo apenas log₂(10⁶) ≈ 20 comparações no pior caso.
Busca em dados ordenados: Busca linear (O(n), Ineficiente para grandes volumes); Jump Search (O(√n), Pior que binária); Busca por interpolação (O(log log n) médio, O(n) pior caso, Exige distribuição uniforme); BFS (Não se aplica a vetores); Busca binária (O(log n), Padrão-ouro, ~20 comparações para 10⁶)
Alternativa A — ❌ Incorreta
A busca linear percorre os elementos um a um, resultando em O(n). Para 1 milhão de registros, seriam necessárias até 1 milhão de comparações, o que contradiz o requisito de "menor número de comparações possível". É adequada apenas para dados não ordenados ou conjuntos muito pequenos.
Alternativa B — ❌ Incorreta
O Jump Search (busca por saltos) tem complexidade O(√n). Para n = 10⁶, √n = 1000, exigindo até 1000 comparações no pior caso. Embora melhor que a linear, ainda é superior às ~20 comparações da busca binária, portanto não é a mais eficiente.
Alternativa C — ❌ Incorreta
A busca por interpolação tem complexidade média O(log log n), podendo chegar a O(1) em casos ideais, mas no pior caso (dados não uniformemente distribuídos) degrada para O(n). Além disso, a afirmação de complexidade O(1) é genérica e enganosa – não é garantida para todos os casos. Não é a mais adequada para garantir desempenho consistente.
Alternativa D — ❌ Incorreta
O algoritmo BFS (Busca em Largura) é usado para percorrer grafos, não para busca em vetores ordenados. Sua complexidade é O(V+E) em grafos, não O(log n). Não se aplica ao problema.
Alternativa E — ✅ Correta ⟵ GABARITO
A busca binária opera em O(log n), reduzindo o espaço de busca pela metade a cada iteração. Para 1 milhão de elementos, o número máximo de comparações é log₂(10⁶) ≈ 20. É o algoritmo clássico e mais eficiente para vetores ordenados, atendendo perfeitamente ao requisito de minimizar comparações.
NÃO CAIA NESSA!
A banca explora o conhecimento das complexidades, colocando alternativas com valores tentadores (O(√n) parece bom, O(1) parece ótimo). Mas a busca binária O(log n) é a única que combina eficiência comprovada e aplicabilidade direta a dados ordenados. Cuidado: interpolação não é O(1) garantido; jump search é inferior; BFS é para grafos.