avertissement: je suis actuellement étudiant dans un camp D’entraînement en science des données, et nous ne sommes pas encore entrés dans les algorithmes. C’est juste quelque chose sur lequel je suis tombé en faisant des recherches sur mon propre temps. Pensais que c’était un sujet intéressant. Certainement pas un pro ou expérimenté avec des algorithmes du tout encore. J’espère que ce sera bientôt.
D’après ma compréhension de base, je crois que ces termes traitent tous de la notation Big-O pour les algorithmes. J’espère que je peux couvrir cela d’une manière très compréhensible.,
bref résumé, Big-O est une mesure de la rapidité avec laquelle un algorithme s’exécute ou résout un problème (notez que c’est la limite supérieure de la durée de l’exécution).
P, NP, NP-Hard et NP-Complete sont des classes dans lesquelles tout problème tomberait ou serait classé.
p (Polynomial) problems
p Les problèmes se réfèrent aux problèmes où un algorithme prendrait un temps polynomial à résoudre, ou où Big-O est un polynôme (C’est-à-dire O(1), O(n), O(n2), etc.). Ce sont des problèmes qui seraient considérés comme « faciles » à résoudre, et n’ont donc généralement pas d’immenses temps d’exécution.,
problèmes NP (polynôme non déterministe)
Les problèmes NP étaient un peu plus difficiles à comprendre pour moi, mais je pense que c’est ce qu’ils sont. En termes de résolution D’un problème NP, l’exécution ne serait pas polynomiale. Ce serait quelque chose comme O (n!) ou quelque chose de beaucoup plus grand. Cependant, cette classe de problèmes peut recevoir une solution spécifique, et la vérification de la solution aurait un temps d’exécution polynomial. Un exemple qui m’a aidé à comprendre cela un peu mieux était un jeu de Sudoku.,
afin de résoudre tout ce casse-tête, l’algorithme devrait vérifier chaque matrice 3×3 pour voir quels nombres manquent, puis chaque ligne, puis chaque colonne, puis s’assurer qu’il n’y a pas de répétitions d’un chiffre de 0-9. Cela devient plus complexe car le nombre de chiffres manquants est incohérent dans chaque ligne, colonne et matrice (c’est-à-dire que la matrice en haut à gauche manque 4 chiffres tandis que la matrice en haut à droite manque 8 chiffres). La résolution de ce problème n’aurait pas d’exécution polynomiale., Cependant, si vous deviez nourrir ce puzzle avec une solution possible, il serait beaucoup moins complexe de vérifier s’il y a des répétitions dans les lignes, les colonnes et les matrices. C’est une vérification simple qui aurait un temps d’exécution polynomial.
en substance, les problèmes de classe NP n’ont pas de temps d’exécution polynomial à résoudre, mais ont un temps d’exécution polynomial pour vérifier les solutions (difficile à résoudre, facile à vérifier une réponse donnée).
réduction
Je ne peux pas vraiment expliquer celui-ci en dehors de l’utilisation d’exemples, donc: nous avons deux problèmes, A et B, et nous savons que le problème B est un problème de classe P., Si le problème A peut être réduit ou converti en problème B, et que cette réduction prend un temps polynomial, alors nous pouvons dire que A est également un problème de classe P (A est réductible à B).
Ce concept est important à comprendre pour les deux autres classes de problèmes.
NP-Dur de Problèmes
Un problème est classé comme étant NP-Difficile quand un algorithme pour le résoudre peut être traduit pour résoudre tout problème NP. Ensuite, nous pouvons dire que ce problème est au moins aussi difficile que n’importe quel problème NP, mais il pourrait être beaucoup plus difficile ou plus complexe.,
NP-Complete Problems
Les problèmes NP-Complete sont des problèmes qui vivent à la fois dans les classes NP et NP-Hard. Cela signifie que les problèmes NP-complets peuvent être vérifiés en temps polynomial et que tout problème NP peut être réduit à ce problème en temps polynomial.
ci-dessous est un diagramme de venn des différents espaces de classe.,
Espérons-le, cela pourrait avoir de clarifier les choses sur ce sujet. Évidemment, j’ai des connaissances très limitées. J’ai juste pensé que c’était intéressant d’en parler et il semble que, même à un haut niveau, c’est assez déroutant.