Questão de Algoritmos e Estrutura de Dados — Algoritmos — IFB 2017
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq283600
Banca
IFB
Órgão
IFB
Ano
2017
Nível
Superior
Cargo
Professor - Informática
Leia as afirmativas a seguir a respeito das principais classes de comportamento assintótico.I) A complexidade logarítmica é típica de algoritmos que resolvem problemas, transformando-os em problemas menores e depois agrupando as soluções dos problemas menores.II) A complexidade quadrática é típica de algoritmos onde os dados são processados ao pares muitas vezes com um anel dentro de outro.III) Um algoritmo com complexidade exponencial é mais rápido que um algoritmo linear.IV) Um algoritmo com complexidade n! (n fatorial) apresenta um comportamento pior que um algoritmo com complexidade 2n .V) A complexidade do algoritmo de pesquisa binária é logarítmica.Assinale a alternativa que apresenta somente as afirmativas CORRETAS.
AI, II, IV, V.
BI, II, III, IV.
CI, II, III, V.
DII, III, IV, V.
EII, IV, V.
Revelar gabarito e comentário▾
GabaritoE — II, IV, V.
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 Assintótica de Algoritmos
Gabarito: letra E. As afirmativas corretas são II, IV e V. A questão cobra o conhecimento das principais classes de complexidade (logarítmica, quadrática, exponencial, fatorial) e exemplos clássicos como a pesquisa binária.
Afirmativa
Descrição
Complexidade Associada
Correção
Motivo
I
"Transforma problemas em menores e agrupa soluções"
O(n log n) ou O(n²) (divisão e conquista)
❌ Incorreto
Descrição corresponde a divisão e conquista, não a logarítmica (O(log n))
II
"Processa dados aos pares com anel dentro de outro"
O(n²) (quadrática)
✅ Correto
Padrão típico de dois laços aninhados
III
"Exponencial é mais rápido que linear"
O(2ⁿ) vs O(n)
❌ Incorreto
Exponencial cresce muito mais rápido que linear
IV
"n! é pior que 2ⁿ"
O(n!) vs O(2ⁿ)
✅ Correto
n! cresce mais rápido que 2ⁿ para n ≥ 4
V
"Pesquisa binária é logarítmica"
O(log n)
✅ Correto
Reduz espaço pela metade a cada passo
Complexidade assintótica: Logarítmica O(log n) (Pesquisa binária, Divisão e conquista (O(n log n))); Quadrática O(n²) (Dois laços aninhados, Ex.: bubble sort); Exponencial O(2ⁿ) (Mais lento que linear); Fatorial O(n!) (Pior que exponencial, Ex.: caixeiro-viajante)
Item I — ❌ Incorreto
Afirma que complexidade logarítmica é típica de algoritmos que transformam problemas em menores e depois agrupam soluções. Essa descrição corresponde à estratégia divisão e conquista, que geralmente resulta em complexidades como O(n log n) (ex.: merge sort) ou O(n²) (ex.: quicksort no pior caso), não necessariamente logarítmica. A complexidade logarítmica (O(log n)) ocorre quando o problema é reduzido por um fator constante a cada passo, como na pesquisa binária, sem necessidade de agrupar soluções. Portanto, o item é falso.
Item II — ✅ Correto
A complexidade quadrática (O(n²)) é típica de algoritmos com dois laços aninhados que percorrem os dados, processando pares de elementos. A descrição "processados ao pares muitas vezes com um anel dentro de outro" corresponde exatamente a esse padrão. Exemplo: ordenação por bolha (bubble sort). Item correto.
Item III — ❌ Incorreto
Afirma que complexidade exponencial é mais rápida que linear. Na verdade, para entradas grandes, algoritmos exponenciais (O(2ⁿ)) tornam-se extremamente lentos, enquanto lineares (O(n)) são muito mais eficientes. Exponencial cresce muito mais rápido que linear, portanto a afirmação está invertida. Item falso.
Item IV — ✅ Correto
A complexidade fatorial (O(n!)) é de fato pior que a exponencial (O(2ⁿ)) para n ≥ 4, pois n! cresce mais rapidamente. Exemplo: problema do caixeiro-viajante por força bruta. A afirmação está correta.
Item V — ✅ Correto
A pesquisa binária tem complexidade O(log n). A cada passo, o espaço de busca é reduzido pela metade, caracterizando comportamento logarítmico. Item correto.
NÃO CAIA NESSA!
O item III inverte a relação de crescimento: exponencial é mais lento, não mais rápido. O item I confunde logarítmica com divisão e conquista. Na prova, desconfie de afirmações que trocam o sinal da comparação ou atribuem características erradas às classes de complexidade.
Conclusão: Estão corretos os itens II, IV e V, que correspondem à alternativa E.