Questão de Algoritmos e Estrutura de DadosAlgoritmos, Complexidade de Algoritmos
- Banca:
- IBFC
- Órgão:
- TRF - 5ª REGIÃO
- Ano:
- 2024
- Cargo:
- Analista Judiciário - Área Apoio Especializado - Especialidade: Análise de Sistemas de Informação
- Nível:
- Superior
- Modalidade:
- Múltipla escolha
- Código:
- CFP-126609-059
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(n2), 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(nk), onde k é constante, resolve o problema no pior caso em tempo polinomial e, portanto, pertence à classe P.
Estão corretas as afirmativas:
I. Algoritmos de ordenação como a ordenação por inserção têm uma complexidade polinomial de O(n2), 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(nk), onde k é constante, resolve o problema no pior caso em tempo polinomial e, portanto, pertence à classe P.
Estão corretas as afirmativas: