Questão de Algoritmos e Estrutura de Dados — Complexidade de Algoritmos — FGV 2017
Algoritmos e Estrutura de Dados›Complexidade de Algoritmos
Código
fg027473
Banca
FGV
Órgão
IBGE
Ano
2017
Nível
Superior
Cargo
Analista Censitário - Análise de Sistemas - Desenvolvimento de Aplicações - Web Mobile
Para projetar algoritmos eficientes um desenvolvedor deve estar preocupado com a complexidade deste algoritmo, desde sua concepção.Considere a seguinte função T(n) que mede os recursos (ex. tempo de execução) que um algoritmo necessita no pior caso para processar uma entrada qualquer de tamanho n:T(n) = O(log(n))Sabendo que O(log(n)) é a ordem da complexidade de tempo do algoritmo seguindo a notação "big O", é correto afirmar que este algoritmo tem complexidade de ordem:
Aconstante;
Bsublinear;
Clinear;
Dpolinomial;
Eexponencial.
Revelar gabarito e comentário▾
GabaritoB — sublinear;
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 de Algoritmos: Classificação Big O
Gabarito: letra B. A notação O(log n) descreve um algoritmo cujo tempo de execução cresce proporcionalmente ao logaritmo do tamanho da entrada, o que o coloca na categoria de complexidade sublinear, pois seu crescimento é mais lento que o linear O(n).
A questão testa o conhecimento das classes de complexidade comuns da notação Big O. A tabela a seguir resume as principais ordens, da mais rápida para a mais lenta:
Ordem (Big O)
Nome da classe
Exemplo típico
O(1)
Constante
Acesso direto a um elemento de array
O(log n)
Logarítmica
Busca binária
O(n)
Linear
Percorrer uma lista não ordenada
O(n log n)
Linearítmica / Quasilinear
Merge sort, heapsort
O(n²)
Quadrática
Algoritmos de ordenação ingênuos (bubble sort)
O(n^k)
Polinomial
Produto de matrizes (k>2)
O(2^n)
Exponencial
Problema do caixeiro viajante (solução força bruta)
Observe que O(log n) é uma das complexidades sublineares (junto com O(√n), por exemplo), pois seu valor é sempre menor que n para n > 1. A banca utiliza o termo "sublinear" para designar exatamente essa categoria.
Alternativa A — ❌ Incorreta
Constante seria O(1), independente do tamanho da entrada. Log n cresce com n, não é constante.
Alternativa B — ✅ Correta ⟵ GABARITO
O(log n) é sublinear, pois log n < n para todo n > 1, e a função logarítmica cresce mais lentamente que qualquer função linear. É a classificação correta conforme a nomenclatura de complexidade de tempo.
Alternativa C — ❌ Incorreta
Linear é O(n); log n é muito menor que n, não linear.
Alternativa D — ❌ Incorreta
Polinomial inclui ordens como O(n²), O(n³), etc. Log n não é um polinômio em n.
Alternativa E — ❌ Incorreta
Exponencial é O(2^n) ou O(k^n); log n cresce muito mais devagar.
NÃO CAIA NESSA!
O candidato pode confundir "constante" com "logarítmica" ou achar que log n é linear. A banca explora exatamente o fato de que log n é uma função sublinear — menos que linear, mas não constante. Memorize a hierarquia: constante < logarítmica < linear < polinomial < exponencial.