Disclaimer: attualmente sono uno studente in un bootcamp di scienza dei dati e non abbiamo ancora ottenuto gli algoritmi. Questo è solo qualcosa che mi sono imbattuto mentre facevo qualche ricerca nel mio tempo libero. Ho pensato che fosse un argomento interessante. Sicuramente NON è ancora un professionista o esperto di algoritmi. Spero di essere presto.
Dalla mia comprensione di base, credo che questi termini si occupino tutti di notazione Big-O per algoritmi. Spero di poter coprire questo in un modo molto comprensibile.,
Breve riassunto, Big-O è una misura di quanto velocemente un algoritmo viene eseguito o risolve un problema (nota che è il limite superiore di quanto tempo è il tempo di esecuzione).
P, NP, NP-Hard e NP-Complete sono classi che qualsiasi problema rientrerebbe o sarebbe classificato come.
Problemi P (polinomiali)
I problemi P si riferiscono a problemi in cui un algoritmo impiegherebbe una quantità polinomiale di tempo per risolvere, o dove Big-O è un polinomio (cioè O(1), O(n), O(n2), ecc.). Questi sono problemi che sarebbero considerati “facili” da risolvere e quindi non hanno generalmente tempi di esecuzione immensi.,
Problemi NP (polinomiali non deterministici)
I problemi NP sono stati un po ‘ più difficili da capire per me, ma penso che questo sia quello che sono. In termini di risoluzione di un problema NP, il tempo di esecuzione non sarebbe polinomiale. Sarebbe qualcosa come O (n!) o qualcosa di molto più grande. Tuttavia, a questa classe di problemi può essere data una soluzione specifica e il controllo della soluzione avrebbe un runtime polinomiale. Un esempio che mi ha aiutato a capire questo un po ‘ meglio è stato un gioco di Sudoku.,
Per risolvere l’intero puzzle, l’algoritmo dovrebbe controllare ogni matrice 3×3 per vedere quali numeri mancano, quindi ogni riga, quindi ogni colonna, e quindi assicurarsi che non ci siano ripetizioni di nessuna cifra da 0-9. Questo diventa più complesso perché il numero di cifre mancanti è incoerente in ogni riga, colonna e matrice (cioè la matrice in alto a sinistra manca di 4 cifre mentre la matrice in alto a destra manca di 8 cifre). Risolvere questo problema non avrebbe un runtime polinomiale., Tuttavia, se si dovesse alimentare questo puzzle con una possibile soluzione, sarebbe molto meno complesso verificare se ci sono ripetizioni nelle righe, nelle colonne e nelle matrici. Questo è un semplice controllo che avrebbe un runtime polinomiale.
In sostanza, i problemi di classe NP non hanno un runtime polinomiale da risolvere, ma hanno un runtime polinomiale per verificare le soluzioni (difficile da risolvere, facile da controllare una data risposta).
Riduzione
Non riesco davvero a spiegarlo al di fuori dell’uso degli esempi, quindi: abbiamo due problemi, A e B, e sappiamo che il problema B è un problema di classe P., Se il problema A può essere ridotto o convertito in problema B, e questa riduzione richiede una quantità di tempo polinomiale, allora possiamo dire che A è anche un problema di classe P (A è riducibile a B).
Questo concetto è importante da capire per le altre due classi di problemi.
Problemi NP-Hard
Un problema è classificato come NP-Hard quando un algoritmo per risolverlo può essere tradotto per risolvere qualsiasi problema NP. Quindi possiamo dire che questo problema è almeno duro come qualsiasi problema NP, ma potrebbe essere molto più difficile o più complesso.,
Problemi NP-Completi
I problemi NP-Completi sono problemi che vivono sia nelle classi NP che NP-Hard. Ciò significa che i problemi NP-Completi possono essere verificati in tempo polinomiale e che qualsiasi problema NP può essere ridotto a questo problema in tempo polinomiale.
Di seguito è riportato un diagramma di venn dei diversi spazi di classe.,
Speriamo che ciò potrebbe avere cancellato le cose su questo argomento. Ovviamente, ho una conoscenza molto limitata. Ho solo pensato che fosse interessante parlare e sembra che, anche ad alto livello, questo sia piuttosto confuso.