Gostaria de saber qual a diferença entre a complexidade de um algoritmo e a complexidade de um problema, ou seja, quais os pontos que diferem as duas coisas
-
2Te aconselho a dar uma olhada na resposta desta pergunta : cs.stackexchange.com/questions/13669/… e também olhar este pdf : ime.usp.br/~song/mac5710/slides/01complex.pdf– Monteiro24/06/2017 às 21:38
-
Normalmente, complexidade de software normalmente tem a ver com o que o software faz, quantidade de responsabilidades, coisas assim. Veja a Lei de Zawinski– Jefferson Quesado25/06/2017 às 14:15
Adicione um comentário
|
1 Resposta
A terminologia correta é dizer que um problema pertence a uma classe de complexidade temporal.
Para saber a qual classe um problema pertence, devemos ver qual é o melhor algoritmo que resolve aquele problema (isto é, o algoritmo com a menor complexidade temporal):
- Se este algoritmo tiver complexidade polinomial, o problema pertence à classe P;
- Se este algoritmo tiver complexidade exponencial, o problema pertence à classe EXPTIME;
- etc