Questão de TI - Desenvolvimento de Sistemas — Complexidade de Algoritmos — IBFC 2024

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(n*) 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?), 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”), onde k é constante, resolve o problema no pior caso em tempo polinomial e, portanto, pertence à classe P.

Estão corretas as afirmativas: