Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUNDATEC 2026

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg685509
Banca
FUNDATEC
Órgão
IFC-SC
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Computação
Sobre análise de complexidade e algoritmos de ordenação, analise as assertivas a seguir:I. A notação O (big-O) define um limite superior assintótico: f(n) = O(g(n)) se, e somente se, existem constantes c > 0 e n₀ ≥ 1 tais que 0 ≤ f(n) ≤ c·g(n) para todo n ≥ n₀.II. O Merge Sort apresenta complexidade Θ(n log n) no pior, no melhor e no caso médio, mantendo esse desempenho independentemente da distribuição de entrada.III. O algoritmo Quick Sort com estratégia de pivô aleatório (randomized quicksort) possui complexidade Θ(n log n) no pior caso, eliminando completamente a possibilidade de comportamento quadrático.IV. Se um algoritmo tem complexidade O(n²), então ele também tem complexidade O(n³), pois toda função limitada superiormente por c·n² também é limitada superiormente por c·n³ para n suficientemente grande.Quais estão corretas?
  1. AApenas I e II.
  2. BApenas II e III.
  3. CApenas II e IV.
  4. DApenas I, II e IV.
  5. EApenas I, III e IV
Revelar gabarito e comentário

GabaritoD — Apenas I, II e IV.

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 e Algoritmos de Ordenação

Gabarito: letra D (corretas I, II e IV). A assertiva I está correta pois define a notação Big-O como limite superior assintótico. A assertiva II está correta: o Merge Sort possui complexidade Θ(n log n) nos três casos. A assertiva IV está correta: O(n²) implica O(n³) por ser uma cota superior relaxada. A assertiva III é falsa: o Quick Sort aleatório não elimina o pior caso Θ(n²), apenas reduz sua probabilidade — a afirmação de "eliminação completa" é uma generalização indevida.

Assertiva

Definição/Descrição

Complexidade (Big-O/Θ)

Correção

I

Big-O como limite superior assintótico: f(n) = O(g(n)) se ∃ c>0, n₀≥1 com 0 ≤ f(n) ≤ c·g(n) para n ≥ n₀

—

✅ Correta

II

Merge Sort: desempenho independente da distribuição de entrada

Θ(n log n) no pior, melhor e caso médio

✅ Correta

III

Quick Sort com pivô aleatório: elimina completamente o pior caso quadrático

Θ(n²) no pior caso (não eliminado)

❌ Incorreta

IV

Se O(n²), então também O(n³) (cota superior relaxada)

O(n²) ⇒ O(n³)

✅ Correta

Assertiva I — ✅ Correta

A definição padrão de Big-O é exatamente a apresentada: f(n) = O(g(n)) se existem constantes c > 0 e n₀ ≥ 1 tais que 0 ≤ f(n) ≤ c·g(n) para todo n ≥ n₀. Portanto, a afirmativa está correta.

Assertiva II — ✅ Correta

O Merge Sort divide a lista em metades recursivamente (log n níveis) e realiza a intercalação em tempo linear O(n) em cada nível, resultando em Θ(n log n) para qualquer distribuição de entrada. Assim, o desempenho é o mesmo no pior, melhor e caso médio.

Assertiva III — ❌ Incorreta

Embora o Quick Sort com pivô aleatório tenha tempo esperado O(n log n), o pior caso continua sendo Θ(n²) (por exemplo, quando a aleatoriedade produz sempre partições desbalanceadas). A aleatorização torna o pior caso extremamente improvável, mas não o elimina. Portanto, a afirmação é falsa.

Assertiva IV — ✅ Correta

Se f(n) = O(n²), então para n grande, f(n) ≤ c·n². Como n² ≤ n³ para n ≥ 1, temos f(n) ≤ c·n³, logo f(n) = O(n³). A notação O é uma cota superior que pode ser relaxada. A assertiva está correta.

Conclusão: Corretas apenas I, II e IV → alternativa D.

Link permanente: /questoes/qg685509