Disclaimer: sunt în prezent un student într-o știință de date bootcamp, și nu am ajuns în algoritmi încă. Acesta este doar ceva ce am dat peste în timp ce făceam niște cercetări în timpul meu liber. Am crezut că e un subiect interesant. Cu siguranță nu este încă un profesionist sau experimentat cu algoritmi. Să sperăm că voi fi în curând.
Din înțelegerea mea de bază, cred că toți acești termeni se ocupă de notația Big-O pentru algoritmi. Să sperăm că pot acoperi acest lucru într-un mod foarte ușor de înțeles.,
scurt rezumat, Big-O este o măsură a cât de repede rulează un algoritm sau rezolvă o problemă (rețineți că este limita superioară a duratei timpului de rulare).
P, NP, NP-Hard și NP-Complete sunt clase care orice problemă ar cădea sub sau ar fi clasificate ca.
p (polinom) probleme
P probleme se referă la probleme în cazul în care un algoritm ar lua o cantitate polinomial de timp pentru a rezolva, sau în cazul în care Big-O este un polinom (adică o(1), O(n), o(n2), etc). Acestea sunt probleme care ar fi considerate „ușor” de rezolvat și, prin urmare, nu au, în general, timpi de rulare imensi.,
NP (Non-determinist polinom) probleme
probleme NP au fost un pic mai greu pentru mine să înțeleagă, dar cred că acest lucru este ceea ce sunt. În ceea ce privește rezolvarea unei probleme NP, timpul de rulare nu ar fi polinom. Ar fi ceva de genul O (n!) sau ceva mult mai mare. Cu toate acestea, această clasă de probleme poate primi o soluție specifică, iar verificarea soluției ar avea un timp de rulare polinomial. Un exemplu care m-a ajutat să înțeleg mai bine acest lucru a fost un joc Sudoku.,pentru a rezolva întregul puzzle, algoritmul ar trebui să verifice fiecare matrice 3×3 pentru a vedea ce numere lipsesc, apoi fiecare rând, apoi fiecare coloană și apoi să se asigure că nu există repetări ale niciunei cifre de la 0-9. Acest lucru devine mai complex, deoarece numărul de cifre care lipsesc este inconsistent în fiecare rând, coloană și matrice (adică matricea din stânga sus lipsește 4 cifre, în timp ce matricea din dreapta sus lipsește 8 cifre). Rezolvarea acestei probleme nu ar avea un timp de rulare polinomial., Cu toate acestea, dacă ar fi să alimentați acest puzzle cu o posibilă soluție, ar fi mult mai puțin complex să verificați dacă există repetări în rânduri, coloane și matrice. Aceasta este o verificare simplă, care ar avea un polinom run-time.
în esență, problemele clasei NP nu au un timp de rulare polinomial de rezolvat, ci au un timp de rulare polinomial pentru a verifica soluțiile (dificil de rezolvat, ușor de verificat un răspuns dat).
reducere
nu pot explica cu adevărat acest lucru în afara utilizării exemplelor, deci: avem două probleme, A și B, și știm că problema B este o problemă a clasei P., Dacă problema A poate fi redusă sau convertită în problema B, iar această reducere durează o perioadă polinomială de timp, atunci putem spune că A este și o problemă a clasei P (A este reductibilă la B).acest concept este important de înțeles pentru celelalte două clase de probleme.
probleme NP-Hard
o problemă este clasificată ca NP-Hard atunci când un algoritm de rezolvare poate fi tradus pentru a rezolva orice problemă NP. Atunci putem spune că această problemă este cel puțin la fel de grea ca orice problemă NP, dar ar putea fi mult mai dificilă sau mai complexă.,
NP-probleme Complete
NP-probleme Complete sunt probleme care trăiesc în ambele clase NP și NP-Hard. Aceasta înseamnă că problemele NP-Complete pot fi verificate în timp polinomial și că orice problemă NP poate fi redusă la această problemă în timp polinomial.
mai jos este o diagramă venn a diferitelor spații de clasă.,
să Sperăm că, acest lucru ar putea fi clarificat lucrurile despre acest subiect. Evident, am cunoștințe foarte limitate. Am crezut că acest lucru a fost interesant pentru a vorbi despre și se pare ca, chiar și la un nivel înalt, acest lucru este destul de confuz.