Disclaimer: ich bin zurzeit ein student, der in einem Data Science-bootcamp, und wir nicht bekommen haben in algorithmen noch. Dies ist nur etwas, auf das ich gestoßen bin, als ich meine eigene Zeit recherchiert habe. Dachte, es war ein Interessantes Thema. Definitiv noch KEIN Profi oder erfahren mit Algorithmen. Hoffentlich werde ich bald sein.
Aus meinem Grundverständnis heraus glaube ich, dass sich diese Begriffe alle mit der Big-O-Notation für Algorithmen befassen. Hoffentlich kann ich das auf sehr verständliche Weise abdecken.,
Kurze Zusammenfassung, Big-O ist ein Maß dafür, wie schnell ein Algorithmus läuft oder löst ein Problem (beachten Sie, es ist die obere Grenze, wie lange die Laufzeit ist).
P, NP, NP-Hard und NP-Complete sind Klassen, unter die jedes Problem fallen würde oder als die es klassifiziert würde.
P (Polynom) Probleme
P Probleme beziehen sich auf Probleme, bei denen ein Algorithmus eine Polynomzeit in Anspruch nehmen würde oder bei denen Big-O ein Polynom ist (dh O (1), O(n), O(n2) usw.). Dies sind Probleme, die als „leicht“ zu lösen gelten und daher im Allgemeinen keine immensen Laufzeiten haben.,
NP (Nicht-deterministisch Polynomial) Probleme
NP Probleme waren ein wenig schwieriger für mich zu verstehen, aber ich denke, das ist, was Sie sind. In Bezug auf die Lösung eines NP-Problems wäre die Laufzeit kein Polynom. Es wäre so etwas wie O(n!) oder etwas viel Größeres. Diese Klasse von Problemen kann jedoch eine bestimmte Lösung erhalten, und die Überprüfung der Lösung hätte eine Polynomlaufzeit. Ein Beispiel, das mir half, dies ein wenig besser zu verstehen, war ein Sudoku-Spiel.,
Um dieses gesamte Rätsel zu lösen, müsste der Algorithmus jede 3×3-Matrix überprüfen, um zu sehen, welche Zahlen fehlen, dann jede Zeile, dann jede Spalte und dann sicherstellen, dass es keine Wiederholungen gibt jede Ziffer von 0-9. Dies wird komplexer, da die Anzahl der fehlenden Ziffern in jeder Zeile, Spalte und Matrix inkonsistent ist (dh in der oberen linken Matrix fehlen 4 Ziffern, während in der oberen rechten Matrix 8 Ziffern fehlen). Die Lösung dieses Problems hätte keine Polynomlaufzeit., Wenn Sie dieses Puzzle jedoch mit einer möglichen Lösung füttern würden, wäre es viel weniger komplex zu überprüfen, ob Wiederholungen in den Zeilen, Spalten und Matrizen vorhanden sind. Dies ist eine einfache Überprüfung, die eine Polynomlaufzeit hätte.
Im Wesentlichen haben NP-Klassenprobleme keine zu lösende Polynomlaufzeit, sondern eine Polynomlaufzeit, um Lösungen zu überprüfen (schwer zu lösen, leicht zu überprüfende Antwort).
<
Ich kann dies außerhalb der Verwendung von Beispielen nicht wirklich erklären, also: Wir haben zwei Probleme, A und B, und wir wissen, dass Problem B ein P-Klassenproblem ist., Wenn Problem A reduziert oder in Problem B konvertiert werden kann und diese Reduktion viel Zeit in Anspruch nimmt, können wir sagen, dass A auch ein Problem der P-Klasse ist (A ist auf B reduzierbar).
Dieses Konzept ist wichtig für die beiden anderen Problemklassen zu verstehen.
NP-Hard-Probleme
Ein Problem wird als NP-Hard klassifiziert, wenn ein Algorithmus zur Lösung eines NP-Problems übersetzt werden kann. Dann können wir sagen, dieses Problem ist mindestens so schwer wie jedes andere Problem, aber es könnte viel schwieriger oder komplexer sein.,
NP-Vollständige Probleme
NP-Vollständige Probleme sind Probleme, die sowohl in der NP-als auch in der NP-harten Klasse auftreten. Dies bedeutet, dass NP-vollständige Probleme in polynomialer Zeit verifiziert werden können und dass jedes NP-Problem in polynomialer Zeit auf dieses Problem reduziert werden kann.
Unten ist ein Venn-Diagramm der verschiedenen Klassenräume.,
ich hoffe, dies könnte sich verzogen haben, Dinge zu diesem Thema. Offensichtlich habe ich nur sehr begrenzte Kenntnisse. Ich dachte nur, das war interessant zu reden und es scheint, selbst auf hohem Niveau, das ist ziemlich verwirrend.