Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg101721
Banca
FGV
Órgão
TRF - 1ª REGIÃO
Ano
2024
Nível
Superior
Cargo
Técnico Judiciário - Área Administrativa - Especialidade: Desenvolvimento de Sistemas de Informação
O analista Jon está ministrando um treinamento sobre algoritmos de busca e, durante a explicação sobre a busca binária em uma lista ordenada de n elementos, ele discute a eficiência desse algoritmo.A complexidade de tempo correta que Jon deve apresentar para a busca binária é a de:
AO(n);
BO(n log n);
CO(log n);
DO(n^2);
EO(1).
Revelar gabarito e comentário▾
GabaritoC — 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 Binária – Complexidade de Tempo
Gabarito: letra C. A busca binária, aplicada a uma lista ordenada de elementos, possui complexidade de tempo O(log n) no pior caso. Isso ocorre porque a cada comparação o algoritmo descarta metade dos elementos restantes, reduzindo o espaço de busca exponencialmente. O número de iterações necessárias é proporcional a , o que caracteriza a complexidade logarítmica.
A questão é direta e exige apenas o conhecimento da complexidade clássica desse algoritmo. Vamos analisar cada alternativa:
Alternativa A — O(n) — ❌ Incorreta
O(n) é a complexidade da busca linear (ou sequencial), que percorre todos os elementos um a um. A busca binária é mais eficiente e não tem complexidade linear.
Alternativa B — O(n log n) — ❌ Incorreta
O(n log n) é a complexidade típica de algoritmos de ordenação eficientes, como o merge sort e o heapsort. Não corresponde à busca binária.
Alternativa C — O(log n) — ✅ Correta ⟵ GABARITO
A cada passo, a busca binária divide o espaço de busca pela metade, resultando em uma quantidade de passos igual a no pior caso, o que é O(log n). É a complexidade correta.
Alternativa D — O(n²) — ❌ Incorreta
O(n²) é típico de algoritmos mais lentos, como bubble sort ou selection sort no pior caso. Não se aplica à busca binária.
Alternativa E — O(1) — ❌ Incorreta
O(1) é complexidade constante, como no acesso direto a um índice de um array. A busca binária precisa de um número de comparações que cresce com o tamanho da entrada, portanto não é constante.
PEGA ESSA DICA!
Decore as complexidades clássicas: busca linear O(n), busca binária O(log n), ordenação simples O(n²), ordenação eficiente O(n log n). Esse conhecimento é básico e cai com frequência em concursos.