Disclaimer: jeg er i øjeblikket studerende i en Data Science bootcamp, og vi har ikke fået algoritmer endnu. Dette er bare noget, jeg snuble over, mens jeg lavede noget research på min egen tid. Troede, det var et interessant emne. Absolut ikke en pro eller oplevet med algoritmer overhovedet endnu. Forhåbentlig bliver jeg snart.fra bare min grundlæggende forståelse tror jeg, at disse vilkår alle handler om Big – O notation for algoritmer. Forhåbentlig kan jeg dække dette på en meget forståelig måde.,
kort resum., Big-O er et mål for, hvor hurtigt en algoritme kører eller løser et problem (bemærk, at det er den øvre grænse for, hvor længe køretiden er).
P, NP, NP-Hard og NP-Complete er klasser, som ethvert problem ville falde ind under eller ville blive klassificeret som.
p (polynom) problemer
p problemer henviser til problemer, hvor en algoritme ville tage et polynomium tid at løse, eller hvor Big-O er et polynomium (dvs.O(1), o(n), o(n2) osv.). Dette er problemer, der ville blive betragtet som ‘lette’ at løse, og som derfor generelt ikke har enorme løbetider.,
NP (Ikke-deterministisk Polynomium) Problemer
NP problemer var lidt sværere for mig at forstå, men jeg tror, det er, hvad de er. Med hensyn til at løse et NP-problem ville køretiden ikke være polynom. Det ville være noget som O(n!) eller noget meget større. Imidlertid kan denne klasse af problemer gives en bestemt løsning, og kontrol af løsningen ville have en polynomisk run-time. Et eksempel, der hjalp mig med at forstå dette lidt bedre, var et Sudoku-spil.,
for at løse hele dette puslespil skal algoritmen kontrollere hver 3 .3 Matri.for at se, hvilke tal der mangler, derefter hver række, derefter hver kolonne og derefter sørge for, at der ikke er gentagelser af et ciffer fra 0-9. Dette bliver mere kompliceret, da antallet af cifre, der mangler, er inkonsekvent i hver række, kolonne, og matrix (dvs top-venstre matrix mangler 4 cifre, mens øverste højre matrix mangler 8 cifre). Løsning af dette problem ville ikke have en polynomisk run-time., Men hvis du skulle fodre dette puslespil med en mulig løsning, ville det være meget mindre komplekst at kontrollere, om der er gentagelser i rækker, kolonner og matricer. Dette er en simpel check, som ville have en polynomisk run-time.
i det væsentlige har NP-klasseproblemer ikke en polynomisk køretid til at løse, men har en polynomisk køretid til at verificere løsninger (vanskeligt at løse, let at kontrollere et givet svar).
reduktion
Jeg kan ikke rigtig forklare denne uden for at bruge eksempler, så: vi har to problemer, A og B, og vi ved, at problem B er et P-klasseproblem., Hvis problem A kan reduceres eller konverteres til problem B, og denne reduktion tager et polynomium tid, så kan vi sige, at A også er et P-klasseproblem (A kan reduceres til b).
dette koncept er vigtigt at forstå for de to andre klasser af problemer.
NP-Hard problemer
et problem klassificeres som NP-Hard, når en algoritme til løsning af det kan oversættes for at løse ethvert NP-problem. Så kan vi sige, at dette problem er mindst lige så hårdt som ethvert NP-problem, men det kan være meget sværere eller mere komplekst.,
NP-komplette problemer
NP-komplette problemer er problemer, der lever i både NP og NP-Hard klasser. Dette betyder, at NP-komplette problemer kan verificeres i polynomisk tid, og at ethvert NP-problem kan reduceres til dette problem i polynomisk tid.
nedenfor er et venn-diagram over de forskellige klassepladser.,
Forhåbentlig, dette kunne have ryddet op i tingene omkring dette emne. Selvfølgelig har jeg meget begrænset viden. Jeg troede bare, at dette var interessant at tale om, og det ser ud til, selv på et højt niveau, Dette er temmelig forvirrende.