A complexidade de algoritmos é uma métrica
fundamental para avaliar a eficiência de
programas, permitindo estimar o tempo de
execução e o consumo de recursos em função do
tamanho da entrada. Diversas notações são
utilizadas para descrever o comportamento de
algoritmos em diferentes cenários, como melhor
caso, pior caso e casos médios, assim como a
complexidade de tempo, que indica o crescimento
do tempo de execução conforme a quantidade de
dados aumenta. Sobre complexidade de
algoritmos, informe se é verdadeiro (V) ou falso (F)
o que se afirma a seguir e assinale a alternativa
com a sequência correta.( ) A notação empregada para representar o
melhor caso de um determinado algoritmo é Ω
(Omega).( ) A notação empregada para representar o pior
caso em casos gerais de um determinado
algoritmo é Θ (Theta).( ) O(1) – tempo de execução constante, que não
varia conforme o tamanho da entrada do
algoritmo.( ) Quanto à complexidade de tempo, O(n) –
tempo quadrático, cresce proporcionalmente
ao tamanho da entrada.

Question

A complexidade de algoritmos é uma métrica
fundamental para avaliar a eficiência de
programas, permitindo estimar o tempo de
execução e o consumo de recursos em função do
tamanho da entrada. Diversas notações são
utilizadas para descrever o comportamento de
algoritmos em diferentes cenários, como melhor
caso, pior caso e casos médios, assim como a
complexidade de tempo, que indica o crescimento
do tempo de execução conforme a quantidade de
dados aumenta. Sobre complexidade de
algoritmos, informe se é verdadeiro (V) ou falso (F)
o que se afirma a seguir e assinale a alternativa
com a sequência correta.( ) A notação empregada para representar o
melhor caso de um determinado algoritmo é Ω
(Omega).( ) A notação empregada para representar o pior
caso em casos gerais de um determinado
algoritmo é Θ (Theta).( ) O(1) – tempo de execução constante, que não
varia conforme o tamanho da entrada do
algoritmo.( ) Quanto à complexidade de tempo, O(n) –
tempo quadrático, cresce proporcionalmente
ao tamanho da entrada.  Alternativa A: V – F – V – F.  Ou Alternativa B: F – V – V – F. Ou Alternativa C: F – V – F – V. Ou Alternativa D: V – V – F – F. Ou Alternativa E: V – F – F – V.

Qconcursos · Accepted Answer

Alternativa [A] V – F – V – F.  Gabarito: AFundamento decisivo: A decisão dependia de identificar, nas quatro assertivas, a correspondência entre notação e classe de complexidade: a questão toma Ω como melhor caso, rejeita Θ como pior caso, aceita O(1) como constante e trata O(n) como linear.Tema central: notações assintóticasAnálise das alternativasACertaA alternativa A está correta porque corresponde à valoração V–F–V–F extraída das definições usuais de análise de algoritmos adotadas na questão. A primeira assertiva é aceita como verdadeira pela convenção didática usada: Ω indica limite inferior e, nesse tratamento, aparece associado ao melhor caso. A segunda é falsa porque Θ não designa especificamente pior caso; ela expressa limite assintótico exato ou ajustado. A terceira é verdadeira porque O(1) descreve tempo constante, sem crescimento com o tamanho da entrada. A quarta é falsa porque O(n) representa crescimento linear; complexidade quadrática seria O(n²).BErradaEstá errada porque marca a primeira assertiva como falsa e a segunda como verdadeira. Isso contraria o critério adotado na questão: Ω foi tomado como associado ao melhor caso, enquanto Θ não representa pior caso, mas limite assintótico ajustado.CErradaEstá errada porque, além de inverter as duas primeiras assertivas, produz sequência incompatível com as classes básicas de tempo: O(1) é constante e O(n) é linear, o que torna a sequência incorreta.DErradaEstá errada porque trata a segunda assertiva como verdadeira e a terceira como falsa. Isso confronta diretamente as definições cobradas: Θ não é notação específica de pior caso, e O(1) é tempo constante.EErradaEstá errada porque nega a terceira assertiva e aceita a quarta. O erro concreto é duplo: O(1) realmente indica tempo constante, e O(n) não é quadrático; quadrático seria O(n²).Pegadinha da questãoA confusão explorada foi misturar cenário de análise com tipo de limite assintótico, levando o candidato a aceitar Θ como pior caso, e também trocar O(n) linear por tempo quadrático apesar da descrição 'cresce proporcionalmente ao tamanho da entrada'.Dica para questões semelhantesSepare notação assintótica de cenário de análise: Θ indica ordem ajustada, não 'pior caso' por si só.Confira se o nome da classe bate com a expressão: O(1) é constante, O(n) é linear e O(n²) é quadrática.Quando a descrição disser 'cresce proporcionalmente ao tamanho da entrada', a classificação compatível é linear, não quadrática.

🎯 Saiba o que estudar

🎯 Saiba o que estudar

A complexidade de algoritmos é uma métrica fundamental para...

Gabarito comentado

Gabarito: A

Clique para visualizar este gabarito

Questões de assuntos semelhantes

Provas relacionadas