Ansvarsfraskrivelse: jeg er for tiden student i en Science Data bootcamp, og vi har ikke fått inn algoritmer ennå. Dette er bare noe jeg snublet over mens du gjør noen undersøkelser på min egen tid. Syntes det var et interessant tema. Definitivt IKKE en pro eller opplevd med algoritmer på alle ennå. Forhåpentligvis vil jeg bli snart.
Fra bare mine grunnleggende forståelse, tror jeg disse vilkårene alle tilbyr med Big-O notasjon for algoritmer. Forhåpentligvis kan jeg dekke dette i en veldig forståelig måte.,
Kort oppsummering, Big-O er et mål på hvor raskt en algoritme går eller løser et problem (merk at det er den øvre grense for hvor lenge kjøretid er).
P, NP, NP-Harde og NP-Komplette klasser som alle problem ville falle under eller ville bli klassifisert som.
P (Polynom) problemer
P problemer med å se på problemer der en algoritme ville ta en polynomisk tid å løse, eller hvor Store-O er et polynom (dvs. O(1) O(n) O(n2), osv). Dette er problemer som ville bli betraktet som ‘lett’ å løse, og dermed ikke generelt har enorm kjøre ganger.,
NP (Ikke-deterministisk Polynom) Problemer
NP-problemer ble litt vanskeligere for meg å forstå, men jeg tror dette er hva de er. I form av å løse et NP-problem, run-time ville ikke være polynom. Ville det være noe som O(n!) eller noe mye større. Imidlertid, denne klassen av problemer kan bli gitt en bestemt løsning, og kontrollere løsning ville ha en polynomisk kjøretid. Et eksempel som hjalp meg å forstå dette litt bedre var en Sudoku spillet.,
for å løse dette hele puslespillet, algoritmen ville ha til å sjekke hver 3×3 matrise for å se hvilke tall som mangler, så hver rad, hver kolonne, og deretter sørge for at det ikke er noen repetisjoner av noen tall fra 0-9. Dette blir mer komplisert fordi antall sifre som mangler er inkonsekvent i hver rad, kolonne, og matrise (dvs. øverste venstre matrix er manglende 4 sifre mens du øverst til høyre matrix er manglende 8 sifre). Å løse dette problemet ville ikke ha en polynomisk kjøretid., Imidlertid, hvis du var å mate dette puslespillet med en mulig løsning, vil det være mye mindre komplisert å sjekke om det er noen repetisjoner i rader, kolonner og matriser. Dette er en enkel test som ville ha en polynomisk kjøretid.
I hovedsak, NP klasse problemer ikke har en polynomisk kjøretid til å løse, men har en polynomisk kjøretid til å bekrefte løsninger (vanskelig å løse, lett å sjekke en gitt svar).
Reduksjon
jeg kan egentlig ikke forklare denne utenfor ved hjelp av eksempler, slik: vi har to problemer, A og B, og vi vet problem B er en P class problem., Hvis problemet En kan bli redusert, eller konverteres til problemet B, og denne reduksjonen tar en polynomisk tid, så kan vi si at En er også en S-klasse problemet (En er som kan reduseres til B).
Dette konseptet er viktig å forstå for de to andre klasser av problemer.
NP-Hard Problemer
Et problem er klassifisert som NP-Hard når en algoritme for å løse det kan oversettes til å løse alle NP-problem. Da kan vi si, dette problemet er minst like vanskelig som alle NP-problem, men det kan være mye vanskeligere eller mer komplekse.,
NP-Komplette Problemer
NP-Komplette problemer er problemer som bor i både NP og NP-Hard-klasser. Dette betyr at NP-Komplette problemer, kan godkjennes i polynomisk tid, og at alle NP-problemet kan reduseres til denne problem i polynomisk tid.
Nedenfor er en venn-diagram i en annen klasse mellomrom.,
Forhåpentligvis, dette kunne ha ryddet opp ting om dette emnet. Selvsagt, jeg har svært begrenset kunnskap. Jeg trodde dette var interessant å snakke om, og det virker som, selv på et høyt nivå, dette er ganske forvirrende.