Algoritmos e Estrutura de Dados · IBFC · 2024 | Questão sqc-qg220666

Algoritmos e Estrutura de DadosConceitos Básicos e Algoritmos

Código: qg220666
Banca: IBFC
Órgão: TRF - 5ª REGIÃO
Ano: 2024
Nível: Superior

Cargo: Analista Judiciário - Área Apoio Especializado - Especialidade: Análise de Sistemas de Informação

Considere o conceito de complexidade polinomial, definido como O(p(n)), onde p(n) é um polinômio e O representa o limite superior da complexidade de um algoritmo. Algoritmos que pertencem à classe P são aqueles que possuem soluções algorítmicas cuja complexidade é limitada por um polinômio de grau k, ou seja, O(nk) para alguma constante k.Esse tipo de problema é considerado solucionável em tempo "razoável" ou eficiente. Dado esse contexto, analise as afirmativas a abaixo sobre a classe P e a complexidade polinomial.I. Algoritmos de ordenação como a ordenação por inserção têm uma complexidade polinomial de O(n 2 ), o que os coloca na classe P.II. A classe P engloba todos os problemas que podem ser resolvidos por algoritmos em tempo polinomial, independente de hardware.III. Algoritmos de pesquisa binária, embora eficientes, não são classificados como pertencentes à classe P, pois sua complexidade é logarítmica, e não polinomial.IV. Um algoritmo que possui uma complexidade de tempo O(n k ), onde k é constante, resolve o problema no pior caso em tempo polinomial e, portanto, pertence à classe P.Estão corretas as afirmativas:

AI, II e IV apenas
BII e IV apenas
CIII e IV apenas
DI e III apenas

Revelar gabarito e comentário

GabaritoA — I, II e IV apenas

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 Polinomial e Classe P

Gabarito: letra A – estão corretas as afirmativas I, II e IV (apenas).

A questão cobra o conceito de classe P, que engloba problemas solucionáveis em tempo polinomial O(nᵏ). Vamos analisar cada afirmativa.

Classe P: Definição (Tempo polinomial O(nᵏ), k constante, Independente de hardware); Exemplos (Ordenação por inserção (O(n²)), Pesquisa binária (O(log n))); Não é P (Exponencial (O(2ⁿ)), Fatorial (O(n!)))

Afirmativa I — ✅ Correta

A ordenação por inserção tem complexidade O(n²), que é polinomial (grau 2). Portanto, pertence à classe P.

Afirmativa II — ✅ Correta

A classe P é definida independentemente de hardware; considera-se a complexidade assintótica do algoritmo, e não o ambiente de execução.

Afirmativa III — ❌ Incorreta

A pesquisa binária tem complexidade O(log n). Embora logarítmica, O(log n) é limitado por O(n) (polinomial de grau 1) e, portanto, também é considerado polinomial. A afirmativa erra ao afirmar que não pertence à classe P.

Afirmativa IV — ✅ Correta

Exatamente a definição: tempo O(nᵏ) para k constante é polinomial e caracteriza a classe P.

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

NÃO CAIA NESSA!

Não confunda "polinomial" com "exponencial". Qualquer função de crescimento que seja O(nᵏ) para alguma constante k é polinomial, inclusive logaritmos (que são O(n) para n≥1).

Link permanente: /questoes/qg220666