Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — FGV 2022
Algoritmos e Estrutura de Dados›Complexidade de Algoritmos
Código
fg052051
Banca
FGV
Órgão
SEAD-AP
Ano
2022
Nível
Superior
Cargo
Professor de Educação Básica - Informática
O tempo de execução de um algoritmo é importante na avaliação de problemas e soluções computacionais. Esse fator está estreitamente ligado à complexidade do algoritmo e ao número de elementos de dados que serão processados no pior caso.Numa busca num array com N elementos ordenados, assinale a complexidade algorítmica para a localização de um determinado elemento por meio da busca binária.
A2 . N
Blog N
CN
DN . log N
EN²
Revelar gabarito e comentário▾
GabaritoB — 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”.
Complexidade da busca binária
Gabarito: letra B. A busca binária, aplicada a um array ordenado, descarta metade dos elementos a cada comparação, resultando em complexidade O(log N) no pior caso.
A questão testa o conhecimento básico de análise de algoritmos. A busca binária é um exemplo clássico de algoritmo de divisão e conquista, com complexidade logarítmica.
Alternativa A — ❌ Incorreta
Afirma que a complexidade é 2·N, o que seria linear com fator constante. A busca binária é muito mais eficiente, não sendo proporcional a N.
Alternativa B — ✅ Correta ⟵ GABARITO
A complexidade da busca binária é O(log N). A cada passo, o intervalo de busca é reduzido à metade, logo o número de iterações é aproximadamente log₂ N.
Alternativa C — ❌ Incorreta
Complexidade O(N) corresponde à busca linear (sequencial), em que cada elemento é verificado um a um. Não é o caso da busca binária.
Alternativa D — ❌ Incorreta
N·log N é a complexidade de algoritmos de ordenação eficientes (como mergesort ou heapsort). A busca binária tem complexidade inferior.
Alternativa E — ❌ Incorreta
O(N²) é típico de algoritmos como ordenação por bolha (bubble sort) ou alguns algoritmos ingênuos. Não se aplica à busca binária.
PEGA ESSA DICA!
Decore as complexidades clássicas: busca linear O(N), busca binária O(log N), ordenação por seleção/bolha O(N²), mergesort O(N log N). Em provas de concurso, a FGV costuma cobrar esses conceitos de forma direta.