Questões de Complexidade de Algoritmos

Explore questões resolvidas de Complexidade de Algoritmos. Acesse respostas e explicações detalhadas para estudar e evoluir.

95% confiança
Problemas decidíveis, porém difíceis, para os quais possivelmente não existe algoritmo que os resolvam em tempo polinomial, é denominado de:
complexidade-de-algoritmos computacao teoria-da-computacao
88% confiança
A solução para dado problema pode ser obtida por meio da descrição de um algoritmo que o resolva. Para isso, no entanto, é fundamental que se analise a computabilidade do problema. Sobre o conceito de computabilidade, leia as assertivas a seguir. I. Se um problema em um cenário prático é dito computável, então qualquer algoritmo que o resolva pode ser empregado. II. Um algoritmo de complexidade O(cn) é dito intratável, já que o seu tempo de resposta é inviável para um problema prático. III. Algoritmos que resolvem problemas incomputáveis têm complexidade de tempo inviável para situações práticas. IV. Um algoritmo com complexidade O(n!) é menos eficiente do que qualquer algoritmo para problemas tratáveis. Quais estão corretas?
complexidade-de-algoritmos computabilidade computacao