Sobre complexidade de algoritmos é INCORRETO
afirmar:

Question

Sobre complexidade de algoritmos é INCORRETO
afirmar: Alternativa A: Se as funções f e g dominam assintoticamente uma
a outra, não podemos discorrer sobre a equivalência dos algoritmos associados. Ou Alternativa B: Se f é uma função de complexidade para um algoritmo F, então O(f ) é considerada a complexidade
assintótica ou o comportamento assintótico do algoritmo F. Ou Alternativa C: Podemos avaliar programas comparando as funções de complexidade, negligenciando as constantes de proporcionalidade. Ou Alternativa D: Algoritmos de complexidade O(1) são ditos de
complexidade constante. Ou Alternativa E: A complexidade O(log n) é típica em algoritmos que
transformam um problema em outros menores.

Qconcursos · Accepted Answer

Alternativa [A] Se as funções f e g dominam assintoticamente uma
a outra, não podemos discorrer sobre a equivalência dos algoritmos associados. Gabarito: AFundamento decisivo: O ponto decisivo era a dominância assintótica mútua: se f domina assintoticamente g e g domina assintoticamente f, então as funções têm a mesma ordem de crescimento. Isso contraria a alternativa A, que afirma não ser possível falar em equivalência dos algoritmos associados.Tema central: equivalência assintóticaAnálise das alternativasACertaA alternativa A está errada porque dominância assintótica mútua é justamente o critério que permite afirmar equivalência assintótica entre as funções associadas. Se f ∈ O(g) e g ∈ O(f), então f e g pertencem à mesma ordem assintótica, isto é, têm a mesma taxa de crescimento até constantes multiplicativas, o que autoriza comparar os algoritmos como de mesma ordem de complexidade.BErradaEstá correta porque a notação O(f) é usada para descrever o comportamento assintótico de um algoritmo em termos de ordem de crescimento.CErradaEstá correta porque a comparação assintótica entre funções de complexidade despreza constantes de proporcionalidade, já que elas não alteram a classe de crescimento.DErradaEstá correta porque O(1) significa custo limitado por uma constante, independentemente do tamanho da entrada; por isso a denominação é complexidade constante.EErradaEstá correta porque complexidade O(log n) é típica em algoritmos que reduzem sucessivamente o tamanho do problema, produzindo número de etapas proporcional ao logaritmo da entrada.Pegadinha da questãoA confusão explorada foi tratar dominância assintótica mútua como impossibilidade de comparação, quando ela indica equivalência de ordem.Dica para questões semelhantesSe duas funções estão uma em O da outra, conclua equivalência assintótica, não incomparabilidade.Ao ler notação O, interprete como classe de crescimento assintótico, não como custo exato.Na comparação assintótica, elimine constantes multiplicativas antes de decidir qual função cresce mais.Associe O(log n) a redução iterativa do tamanho do problema, mas sem transformar isso em regra universal para toda decomposição.

🎯 Saiba o que estudar

🎯 Saiba o que estudar

Sobre complexidade de algoritmos é INCORRETO afirmar:

Gabarito comentado

Gabarito: A

Clique para visualizar este gabarito

Questões de assuntos semelhantes

Provas relacionadas