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: