Disclaimer: olen tällä hetkellä opiskelija, Data Science bootcamp, ja meillä ei ole mennyt algoritmeja vielä. Tähän törmäsin tehdessäni tutkimusta omasta ajastani. Se oli mielenkiintoinen aihe. Ehdottomasti ei ammattilainen tai kokenut algoritmeja ollenkaan vielä. Toivottavasti olen pian.
pelkästä perusymmärryksestäni uskon, että nämä termit kaikki käsittelevät algoritmien Big-O-notaatiota. Toivottavasti pystyn kattamaan tämän hyvin ymmärrettävällä tavalla.,
Lyhyt yhteenveto, Iso-O on mitata, kuinka nopeasti algoritmi toimii tai ratkaisee ongelman (huomaa, se on yläraja, kuinka pitkä ajoaika on).
P, NP, NP-Hard ja NP-Complete ovat luokkia, joihin mikä tahansa ongelma kuuluisi tai luokiteltaisiin.
P (Polynomi) ongelmia
P ongelmat viittaavat ongelmat, joissa algoritmi ottaa polynomi määrä aikaa ratkaista, tai kun Iso-O on polynomi (eli O(1), O(n), O(n2), jne.). Nämä ovat ongelmia, joita pidettäisiin ”helppoina” ratkaista, eikä niillä siten yleensä ole valtavia juoksuaikoja.,
VL (Ei-deterministinen Polynomi) Ongelmia
NP-ongelmat olivat hieman vaikeampi ymmärtää, mutta luulen, että tämä on mitä he ovat. NP-ongelman ratkaisemisen kannalta run-time ei olisi polynomi. Se olisi jotain o (n!) tai jotain paljon suurempaa. Kuitenkin tämä luokka ongelmia voidaan antaa erityinen ratkaisu,ja tarkistaminen ratkaisu olisi polynomi aikavälillä. Esimerkki, joka auttoi minua ymmärtämään tätä hieman paremmin, oli Sudoku-peli.,
jotta voitaisiin ratkaista koko palapeliä, algoritmi olisi tarkistaa kunkin 3×3 matriisi nähdä, mitkä numerot ovat puuttuu, sitten jokainen rivi, jokainen sarake, ja sitten varmista, että ei ole toistoa tahansa numero 0-9. Tämä tulee monimutkaisempi, koska numeroiden määrä, jotka puuttuvat on ristiriidassa kussakin rivissä, sarakkeessa, ja matriisi (eli top-left matrix puuttuu 4 numeroa, kun taas oikeassa yläkulmassa matriisi puuttuu 8 numeroa). Tämän ongelman ratkaisulla ei olisi polynomiajoa., Jos kuitenkin syöttäisit tämän palapelin mahdollisella ratkaisulla, olisi paljon vähemmän monimutkaista tarkistaa, onko riveissä, sarakkeissa ja matriiseissa toistoja. Tämä on yksinkertainen tarkistus, joka olisi polynomi aikavälillä.
pohjimmiltaan, luokan NP ongelmia ei ole polynomi, run-time ratkaista, mutta on polynomi run-time tarkistaa ratkaisuja (vaikea ratkaista, helppo tarkistaa annettu vastaus).
Vähentää
en osaa selittää tätä, yksi ulkopuolella, käyttäen esimerkkejä, niin: meillä on kaksi ongelmaa, A ja B, ja me tiedämme, ongelma B on P class ongelma., Jos ongelma voidaan alentaa tai muuntaa ongelma B, ja tämä vähennys otetaan polynomi aikaa, sitten voimme sanoa, että on myös P class ongelma (on pelkistettävissä B).
tämä käsite on tärkeä ymmärtää kahden muun ongelmaluokan kannalta.
NP-kovat ongelmat
ongelma luokitellaan NP-kovaksi, kun sen ratkaisemiseen käytettävä algoritmi voidaan kääntää minkä tahansa NP-ongelman ratkaisemiseksi. Sitten voimme sanoa, että tämä ongelma on vähintään yhtä vaikea kuin mikä tahansa NP-ongelma, mutta se voi olla paljon vaikeampi tai monimutkaisempi.,
NP-Täydellisiä Ongelmia
NP-Täydelliset ongelmat ovat ongelmia, jotka elävät sekä NP-ja NP-Kovaa luokkaa. Tämä tarkoittaa, että NP-Täydelliset ongelmat voidaan todentaa polynomi aikaa ja että mikä tahansa NP-ongelma voidaan pienentää tätä ongelmaa, polynomi kertaa.
Alla on venn-kaavio eri luokan tiloihin.,
Toivottavasti tämä voisi olla selvitetty asioita tästä aiheesta. Minulla on selvästikin hyvin vähän tietoa. Ajattelin, että tästä on mielenkiintoista puhua ja tuntuu, että korkeallakin tasolla tämä on aika hämmentävää.