Questão de Algoritmos e Estrutura de Dados — Algoritmos — COMPERVE - UFRN 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg103840
Banca
COMPERVE - UFRN
Órgão
UFERSA
Ano
2024
Nível
Superior
Cargo
Analista de Tecnologia da Informação
A notação Big O descreve a eficiência de algoritmos em termos de tempo de execução ou de uso de memória. Com base nessa notação, analise as afirmativas abaixo.I Algoritmos com complexidade O(1) realizarão a mesma quantidade de operações independentemente da quantidade de entradas.II Algoritmos com complexidade O(n log n) são menos eficientes para grandes entradas em comparação com algoritmos O(n²).III A notação Big O tem como foco o pior caso.IV A notação Big O tem como foco o melhor caso.Das afirmativas, estão corretas
AI e III.
BI e IV.
CII e III.
DII e IV.
Revelar gabarito e comentário▾
GabaritoA — I e III.
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”.
Notação Big O: análise das afirmativas
Gabarito: letra A (afirmativas I e III corretas). A notação Big O descreve o comportamento assintótico de um algoritmo, normalmente no pior caso. A afirmativa I está correta: O(1) é constante, independente da entrada. A afirmativa III está correta: Big O foca no pior caso (limite superior). Já a afirmativa II inverte a relação de eficiência (O(n log n) é mais eficiente que O(n²) para grandes entradas) e a afirmativa IV confunde Big O com o melhor caso (que é descrito pela notação Omega).
Afirmativa
Análise
Correta?
I – O(1) é constante, independente da entrada
Algoritmos O(1) executam número fixo de operações, qualquer que seja o tamanho da entrada.
✅ Sim
II – O(n log n) é menos eficiente que O(n²) para grandes entradas
Inverte a relação: O(n log n) cresce muito mais lentamente que O(n²), sendo mais eficiente.
❌ Não
III – Big O foca no pior caso
Big O fornece limite superior assintótico, normalmente analisado para o pior cenário.
✅ Sim
IV – Big O foca no melhor caso
Confunde com a notação Ω (Omega), que descreve o melhor caso (limite inferior).
❌ Não
Notação Big O: O que descreve (Limite superior assintótico, Pior caso (✅ III)); Complexidades comuns (O(1): constante (✅ I), O(n log n): eficiente, O(n²): menos eficiente (❌ II)); Confusões comuns (Big O ≠ melhor caso (❌ IV), Ω = melhor caso, Θ = caso médio)
Afirmativa I — ✅ Correta
"Algoritmos com complexidade O(1) realizarão a mesma quantidade de operações independentemente da quantidade de entradas."
Correto. Um algoritmo O(1) executa um número fixo de operações, não importando o tamanho da entrada. Exemplos: acesso a um elemento de array por índice, inserção no topo de uma pilha.
Afirmativa II — ❌ Incorreta
"Algoritmos com complexidade O(n log n) são menos eficientes para grandes entradas em comparação com algoritmos O(n²)."
Erro: inverte a relação de eficiência. Para entradas grandes, O(n log n) cresce muito mais lentamente que O(n²). Por exemplo, para n = 1.000.000, n log n ≈ 20 milhões de operações, enquanto n² = 1 trilhão. Portanto, O(n log n) é mais eficiente (mais rápido) que O(n²).
Afirmativa III — ✅ Correta
"A notação Big O tem como foco o pior caso."
Correto. Big O fornece um limite superior assintótico, normalmente analisado para o pior cenário de entrada. É a forma mais comum de expressar complexidade em entrevistas e livros-texto.
Afirmativa IV — ❌ Incorreta
"A notação Big O tem como foco o melhor caso."
Erro: confunde com a notação Omega (Ω), que descreve o melhor caso (limite inferior). Big O é para o pior caso.
NÃO CAIA NESSA!
A questão explora duas confusões comuns: (1) inverter a eficiência entre O(n log n) e O(n²) — muitos acham que O(n log n) é pior, mas é o contrário; (2) achar que Big O mede o melhor caso, quando na verdade ele mede o pior caso (e o melhor caso é representado por Ω). Fique atento: Big O = limite superior (pior caso); Ω = limite inferior (melhor caso); Θ = limite justo (caso médio).
Conclusão: Apenas as afirmativas I e III estão corretas, correspondendo à alternativa A.