Questão de Algoritmos e Estrutura de Dados — Algoritmos — FADESP 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg450248
Banca
FADESP
Órgão
UNIFESSPA
Ano
2025
Nível
Superior
Cargo
Analista de Tecnologia da Informação/Área Desenvolvimento de Software
Na análise de complexidade de algoritmo, uma função f(n) é Ω (t(n)) se, e somente se, a seguintecondição for satisfeita, onde c e k são constantes positivas:
A0 ≤ c .t(n) ≤ f(n) ∀ n ≥ k
B0 ≤ c .t(n) < f(n) ∀ c ≥ n
C0 < c . f(n) ≤ t(n) ∀ c ≥ n
D0 < f(n) < c .t(n) ∀ c ≥ k
E0 ≤ f(n) ≤ c .t(n) ∀ n ≥ k
Revelar gabarito e comentário▾
GabaritoA — 0 ≤ c .t(n) ≤ f(n) ∀ n ≥ k
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 Ω (Omega) em complexidade de algoritmos
Gabarito: alternativa A. A definição correta de f(n) = Ω(t(n)) é: existem constantes positivas c e k tais que 0 ≤ c·t(n) ≤ f(n) para todo n ≥ k. A alternativa A reproduz exatamente essa condição.
A banca testa o conhecimento da definição literal da notação Ω (limite inferior), que é frequentemente confundida com a notação O (limite superior). A alternativa E, por exemplo, corresponde à definição de O grande.
Notação Ω (limite inferior): Definição (0 ≤ c·t(n) ≤ f(n), ∀ n ≥ k, c, k constantes positivas); Significado (f(n) ≥ c·t(n) (a menos de constante), t(n) é limite inferior de f(n)); Confusão comum (O (limite superior): 0 ≤ f(n) ≤ c·t(n))
Alternativa A — ✅ Correta ⟵ GABARITO
A condição 0 ≤ c·t(n) ≤ f(n) para todo n ≥ k é a definição padrão de Ω. Ela estabelece que, a partir de um certo k, f(n) é sempre maior ou igual a c·t(n), indicando que t(n) é um limite inferior para f(n) (a menos de constante multiplicativa).
Alternativa B — ❌ Incorreta
Apresenta 0 ≤ c·t(n) < f(n) ∀ c ≥ n. Há dois problemas: (1) a condição é sobre n ≥ k, não sobre c ≥ n; (2) usa desigualdade estrita (<), mas a definição padrão aceita igualdade (≤). Além disso, a quantificação sobre c está trocada.
Alternativa C — ❌ Incorreta
Apresenta 0 < c·f(n) ≤ t(n) ∀ c ≥ n. Isso inverte os papéis: coloca t(n) como limitante superior de f(n) (definição de O) e ainda usa quantificação em c. Não corresponde à notação Ω.
Alternativa D — ❌ Incorreta
Apresenta 0 < f(n) < c·t(n) ∀ c ≥ k. A desigualdade estrita (<) e a ausência de ≤ no lado esquerdo fogem da definição. Além disso, a condição é muito restritiva e não é a definição canônica.
Alternativa E — ❌ Incorreta
Apresenta 0 ≤ f(n) ≤ c·t(n) ∀ n ≥ k. Esta é a definição da notação O (limite superior), não da Ω. A confusão entre Ω e O é a pegadinha clássica da questão.
NÃO CAIA NESSA!
A banca insere a definição de O grande (alternativa E) como distrator, pois muitos alunos confundem os dois. Lembre-se: Ω representa limite inferior (f(n) ≥ c·g(n)), enquanto O representa limite superior (f(n) ≤ c·g(n)).