Disclaimer: I am currently a student in a Data Science bootcamp, and we have not got into algorithms yet. Isto é algo que tropecei enquanto pesquisava no meu tempo livre. Achei que era um tópico interessante. Definitivamente não é um profissional ou experiente com algoritmos ainda. Espero estar em breve.
de apenas meu entendimento básico, eu acredito que estes Termos todos lidam com notação Big-O para algoritmos. Espero conseguir cobrir isto de uma forma muito compreensível.,
resumo breve, Big-O é uma medida de quão rapidamente um algoritmo executa ou resolve um problema (note que é o limite superior de quanto tempo o tempo de execução é).
P, NP, NP-Hard e NP-Complete são classes nas quais qualquer problema pode ser classificado.
P (Polinomial) problemas
P problemas referem-se a problemas onde um algoritmo levaria um polinˆ omio quantidade de tempo para resolver, ou onde Grande-S é um polinômio (i.e. O(1), O(n), O(n2), etc.). Estes são problemas que seriam considerados “fáceis” de resolver, e, portanto, geralmente não têm tempos de execução imensos.,
NP (polinomial não-determinístico) problemas
NP problemas foram um pouco mais difíceis de entender, mas eu acho que isso é o que eles são. Em termos de resolver um problema NP, o tempo de execução não seria polinomial. Seria algo como O(n!) ou algo muito maior. No entanto, esta classe de problemas pode ser dada uma solução específica, e verificar a solução teria um tempo de execução polinomial. Um exemplo que me ajudou a entender isso um pouco melhor foi um jogo de Sudoku.,
a fim de resolver este enigma inteiro, o algoritmo teria que verificar cada matriz 3×3 para ver quais os números que estão faltando, em seguida, cada linha, cada coluna e, em seguida, certifique-se de que não há repetições de qualquer dígito de 0 a 9. Isto se torna mais complexo porque o número de dígitos que estão faltando é inconsistente em cada linha, coluna e matriz (ou seja, a matriz superior-esquerda está faltando 4 dígitos enquanto a matriz superior-direita está faltando 8 dígitos). Resolver este problema não teria um tempo de execução polinomial., No entanto, se você a alimentar este quebra-cabeça com uma solução possível, seria muito menos complexo para verificar se há repetições nas linhas, colunas e matrizes. Esta é uma verificação simples que teria um tempo de execução polinomial.
em essência, problemas de classe NP não têm um tempo de execução polinomial para resolver, mas têm um tempo de execução polinomial para verificar soluções (difícil de resolver, fácil de verificar uma dada resposta).
Reduction
I can’t really explain this one outside of using examples, so: we have two problems, a and B, and we know problem B is a P class problem., Se o problema a pode ser reduzido, ou convertido ao problema B, E esta redução leva uma quantidade polinomial de tempo, então podemos dizer que A é também um problema de classe P (A é redutível a B).este conceito é importante de entender para as outras duas classes de problemas.
NP-problemas difíceis
um problema é classificado como NP-difícil quando um algoritmo para resolvê-lo pode ser traduzido para resolver qualquer problema NP. Então podemos dizer, este problema é pelo menos tão difícil quanto qualquer problema NP, mas pode ser muito mais difícil ou mais complexo.,
NP-problemas completos
NP-problemas completos são problemas que vivem em ambas as classes NP e NP-Hard. Isto significa que os problemas NP-completos podem ser verificados em tempo polinomial e que qualquer problema NP pode ser reduzido a este problema em tempo polinomial.
abaixo está um diagrama de venn dos diferentes espaços de classe.,
Esperemos que este poderia ter limpado as coisas sobre este tópico. Obviamente, tenho conhecimentos muito limitados. Achei que era interessante falar sobre isto e parece que, mesmo a alto nível, isto é muito confuso.