Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUNCERN 2017

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq263302
Banca
FUNCERN
Órgão
IF-RN
Ano
2017
Nível
Superior
Cargo
Professor - Sistemas de Informação
Considerando a área de complexidade algoritmos, assinale a opção que apresenta a classe assintótica, na notação O, com o menor tempo de resposta dada a mesma entrada de dados n.
  1. AO(n)
  2. BO(nlog(n))
  3. CO(2n)
  4. DO(log(n))
Revelar gabarito e comentário

GabaritoD — 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”.

Complexidade de Algoritmos

Gabarito: letra D. A notação O(log n) representa a menor complexidade entre as opções, pois o tempo de execução cresce logaritmicamente com o tamanho da entrada, sendo mais eficiente que O(n), O(n log n) e O(2^n).

A questão cobra a hierarquia de crescimento das funções na notação Big-O. Para entradas grandes, a ordem de eficiência (do menor para o maior tempo) é: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Dentre as alternativas, O(log n) é a que tem menor taxa de crescimento.

  1. 1O(1) — constante
  2. 2O(log n) — logarítmico
  3. 3O(n) — linear
  4. 4O(n log n) — linearítmico
  5. 5O(n²) — quadrático
  6. 6O(2ⁿ) — exponencial
  7. 7O(n!) — fatorial
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

O(n) representa tempo linear: o tempo de execução cresce proporcionalmente ao tamanho da entrada. Embora seja eficiente, é maior que O(log n), já que n cresce mais rápido que log n.

Alternativa B — ❌ Incorreta

O(n log n) é conhecido como tempo linearítmico, comum em algoritmos de ordenação eficientes (como mergesort). É maior que O(n) e, portanto, também maior que O(log n).

Alternativa C — ❌ Incorreta

O(2ⁿ) é tempo exponencial: o tempo dobra a cada incremento na entrada. É a pior complexidade entre as listadas, inviável para grandes valores de n.

Alternativa D — ✅ Correta ⟵ GABARITO

O(log n) é tempo logarítmico. Algoritmos como busca binária e operações em árvores binárias balanceadas têm essa complexidade. O logaritmo (usualmente base 2) cresce muito lentamente, tornando essa a opção mais eficiente.

PEGA ESSA DICA!

Decore a ordem de crescimento das funções: 1 < log n < n < n log n < n² < 2ⁿ < n!. Isso ajuda a identificar rapidamente a mais eficiente em questões de notação O.

Gabarito: letra D

Link permanente: /questoes/qq263302