Considere o conceito de complexidade polinomial, definido c...
Ver outras questões
Usar o filtro de questões
Ano: 2024
Banca:
IBFC
Órgão:
TRF - 5ª REGIÃO
Prova:
IBFC - 2024 - TRF - 5ª REGIÃO - Analista Judiciário - Área Apoio Especializado - Especialidade: Análise de Sistemas de Informação |
Q3172921
Não definido
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:
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:
Conheça nossos planos