Questão de Algoritmos e Estrutura de Dados — Algoritmos — Gama Consult 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg202006
Banca
Gama Consult
Órgão
Câmara de Alto Paraíso - RO
Ano
2024
Nível
Superior
Cargo
Gestor de Tecnologia da Informação
Na área de Análise de Algoritmos, a notação assintótica é fundamental para descrever a complexidade de algoritmos. Considere as seguintes definições e propriedades da notação assintótica: O-notation (O grande), Ω-notation (Ômega grande), e Θ-notation (Theta grande). Qual das afirmativas a seguir é a mais correta em relação à análise assintótica de algoritmos?
AO-notation descreve o limite superior exato do tempo de execução de um algoritmo.
BΩ-notation descreve o limite inferior exato do tempo de execução de um algoritmo.
CUm algoritmo com complexidade O(n^2) é sempre mais eficiente do que um algoritmo com complexidade Ω(n).
DΘ-notation descreve tanto o limite superior quanto o inferior do tempo de execução de um algoritmo.
Revelar gabarito e comentário▾
GabaritoD — Θ-notation descreve tanto o limite superior quanto o inferior do tempo de execução de um algoritmo.
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”.
Análise Assintótica de Algoritmos: O, Ω e Θ
Gabarito: letra D. A notação Θ (Theta) representa o limite assintótico justo, ou seja, tanto o limite superior quanto o inferior do tempo de execução de um algoritmo. As notações O e Ω descrevem apenas limites superiores e inferiores, respectivamente, sem garantia de que sejam justos. A definição clássica é:
O(g(n)) = { f(n) | existem constantes positivas c e n₀ tais que 0 ≤ f(n) ≤ c·g(n) para todo n ≥ n₀ }.
Ω(g(n)) = { f(n) | existem constantes positivas c e n₀ tais que 0 ≤ c·g(n) ≤ f(n) para todo n ≥ n₀ }.
Θ(g(n)) = { f(n) | existem constantes positivas c₁, c₂ e n₀ tais que 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) para todo n ≥ n₀ }.
A seguir, analisamos cada alternativa:
Notação assintótica: O (O grande) (Limite superior, Não necessariamente justo); Ω (Ômega grande) (Limite inferior, Não necessariamente justo); Θ (Theta) (Limite superior e inferior, Justo (tight bound))
Alternativa A — ❌ Incorreta
Afirma que O-notation descreve o "limite superior exato". O correto é que O-notation fornece um limite superior assintótico, mas não necessariamente justo (exato). Por exemplo, se f(n) = n, então f(n) = O(n²), mas n² não é um limite justo. O termo "exato" é próprio da notação Θ.
Alternativa B — ❌ Incorreta
Afirma que Ω-notation descreve o "limite inferior exato". Da mesma forma, Ω é um limite inferior assintótico, podendo não ser justo. Exemplo: f(n) = n² é Ω(n), mas n não é um limite inferior justo.
Alternativa C — ❌ Incorreta
Diz que um algoritmo O(n²) é sempre mais eficiente que um algoritmo Ω(n). Isso é falso. Um algoritmo O(n²) pode ter complexidade exata Θ(n²); um algoritmo Ω(n) pode ter complexidade exata Θ(n) (mais rápido) ou Θ(n²) (igual). Não é possível comparar eficiência apenas com limites superior e inferior diferentes. A comparação correta exige que ambos estejam na mesma notação ou que se conheça o comportamento assintótico exato.
Alternativa D — ✅ Correta ⟵ GABARITO
A notação Θ descreve tanto o limite superior quanto o inferior do tempo de execução, caracterizando o crescimento assintótico exato a menos de constantes. É a definição formal de limite justo (tight bound).
NÃO CAIA NESSA!
Para não confundir, lembre-se da hierarquia: O = teto (cota superior), Ω = piso (cota inferior), Θ = justo (ambos). Na prova, desconfie de alternativas que usam "exato" para O ou Ω; o termo correto é Θ.