Please enable JavaScript.
Coggle requires JavaScript to display documents.
Complexidade (Problemas NP (NP-Completo (B está em NP, Toda linguagem A em…
Complexidade
Problemas NP
-
-
NP-Completo
-
Toda linguagem A em NP pode ser decidida usando a solução de B usando “adaptações” polinomiais (para usar a solução de B em A)
-
-
Classe de complexidade
Seja uma função t:N→R+ (tamanho de entrada → tempo, ex: t(n) = n2). A classe de complexidade de tempo TIME(t(n)) é a coleção de todas as linguagens decidíveis por uma máquina de Turing de tempo O(t(n))
-
Problemas P
Podem ser resolvidos em tempo polinomial, ou seja, o algoritmo tem que executar um número polinomial de estágios em tempo polinomial
-
Complexidade de tempo
Complexidade de tempo relacionada com o número de passos necessários para um algoritmo dar uma resposta
Número de passos depende de parâmetros específicos do problema. Ex: tamanho da cadeia de entrada (natural no caso de linguagens) – n
Notação assintótica
Sejam f e g funções f, g: N→R+. Dizemos que f(n) = O(g(n)) se existem inteiros positivos c e n0 tais que, para todo n>= n0
-