Disclaimer: ik ben momenteel een student in een Data Science bootcamp, en we hebben nog geen algoritmen gekregen. Dit is gewoon iets wat ik struikelde over terwijl het doen van wat onderzoek op mijn eigen tijd. Ik vond het een interessant onderwerp. Zeker nog geen pro of ervaren met algoritmes. Hopelijk ben ik dat snel.
vanuit mijn basiskennis, geloof ik dat deze termen allemaal te maken hebben met Big-O notatie voor algoritmen. Hopelijk kan ik dit op een zeer begrijpelijke manier behandelen.,
korte samenvatting, Big-O is een maat voor hoe snel een algoritme een probleem uitvoert of oplost (merk op dat het de bovengrens is van hoe lang de looptijd is).
P, NP, NP-Hard en NP-Complete zijn klassen waar elk probleem onder zou vallen of als geclassificeerd zou worden.
p (polynoom) problemen
P problemen verwijzen naar problemen waarbij een algoritme een veelterm tijd nodig heeft om op te lossen, of waar Big-O een veelterm is (o(1), O(n), O(n2), enz.). Dit zijn problemen die als ‘gemakkelijk’ op te lossen zouden worden beschouwd en dus over het algemeen geen immense draaitijden hebben.,
NP (Non-deterministic Polynomial) problemen
NP problemen waren iets moeilijker voor mij om te begrijpen, maar ik denk dat dit is wat ze zijn. In termen van het oplossen van een NP probleem, de run-time zou niet polynoom. Het zou zoiets zijn als O (n!) of iets veel groters. Echter, deze klasse van problemen kan worden gegeven een specifieke oplossing, en het controleren van de oplossing zou een veelterm run-time hebben. Een voorbeeld dat me hielp dit een beetje beter te begrijpen was een Sudoku spel.,
om deze hele puzzel op te lossen, zou het algoritme elke 3×3 matrix moeten controleren om te zien welke getallen ontbreken, dan elke rij, dan elke kolom, en dan zorg ervoor dat er geen herhalingen zijn van een cijfer van 0-9. Dit wordt complexer omdat het aantal cijfers dat ontbreekt inconsistent is in elke rij, kolom en matrix (dat wil zeggen dat de matrix linksboven 4 cijfers mist, terwijl de matrix rechtsboven 8 cijfers mist). Het oplossen van dit probleem zou geen polynoom run-time hebben., Als je deze puzzel echter zou voeden met een mogelijke oplossing, zou het veel minder complex zijn om te controleren of er herhalingen zijn in de rijen, kolommen en matrices. Dit is een eenvoudige controle die een polynoom run-time zou hebben.
in essentie hebben NP-klasseproblemen geen polynoomlooptijd om op te lossen, maar hebben ze een polynoomlooptijd om oplossingen te verifiëren (moeilijk op te lossen, gemakkelijk om een gegeven antwoord te controleren).
reductie
Ik kan dit niet echt uitleggen buiten het gebruik van voorbeelden, dus: we hebben twee problemen, A en B, en we weten dat probleem B een P klasse probleem is., Als probleem A kan worden verminderd, of omgezet in probleem B, en deze reductie duurt een veelterm tijd, dan kunnen we zeggen dat A ook een P klasse probleem is (A is reduceerbaar tot B).
dit concept is belangrijk om te begrijpen voor de andere twee klassen van problemen.
NP-Hard Problems
een probleem wordt geclassificeerd als NP-Hard wanneer een algoritme voor het oplossen ervan kan worden vertaald om een NP-probleem op te lossen. Dan kunnen we zeggen dat dit probleem minstens zo moeilijk is als elk NP-probleem, maar het kan veel moeilijker of complexer zijn.,
NP-Complete problemen
NP-Complete problemen zijn problemen die zowel in de NP-als NP-harde klassen voorkomen. Dit betekent dat NP-Complete problemen kunnen worden geverifieerd in polynoom tijd en dat elk NP probleem kan worden teruggebracht tot dit probleem in polynoom tijd.
Hieronder is een venn-diagram van de verschillende klassenruimten.,
Hopelijk kan dit verholpen dingen over dit onderwerp. Ik heb duidelijk weinig kennis. Ik vond dit interessant om over te praten en het lijkt, zelfs op een hoog niveau, nogal verwarrend.