jogi nyilatkozat: Jelenleg egy Data Science bootcamp hallgatója vagyok, és még nem jutottunk algoritmusokba. Ez csak valami, amire megbotlottam, miközben a saját időmet kutattam. Azt hittem, ez egy érdekes téma. Határozottan még nem profi vagy tapasztalt algoritmusokkal. Remélhetőleg hamarosan.
csak az alapvető megértésem alapján úgy gondolom, hogy ezek a kifejezések az algoritmusok Big-O jelölésével foglalkoznak. Remélhetőleg, tudom fedezni ezt egy nagyon érthető módon.,
rövid összefoglaló, Big-O egy intézkedés, hogy milyen gyorsan egy algoritmus fut, vagy megoldja a problémát(Megjegyzés Ez a felső határa, hogy mennyi ideig tart a futási idő).
p, NP, NP-Hard és NP-Complete olyan osztályok, amelyekbe bármilyen probléma esne vagy besorolnánk.
P (Polinom) problémák
P problémák lásd probléma, ha egy algoritmus, egy polinom idő, hogy oldja meg, vagy ahol a Nagy-O polinom (azaz O(1) O(n), O(n2), stb.). Ezek olyan problémák, amelyeket “könnyű” megoldani, így általában nem rendelkeznek óriási futási idővel.,
NP (nem determinisztikus polinom) problémák
NP problémák voltak egy kicsit nehezebb megérteni, de azt hiszem, ez az, amit ők. Az NP-probléma megoldása szempontjából a futási idő nem lenne polinom. Olyan lenne, mint O (n!) vagy valami sokkal nagyobbat. Ennek a problémaosztálynak azonban konkrét megoldása lehet, a megoldás ellenőrzése pedig polinom futási idővel jár. Egy példa, amely segített megérteni ezt egy kicsit jobban volt egy Sudoku játék.,
az egész puzzle megoldásához az algoritmusnak ellenőriznie kell minden 3×3 mátrixot, hogy megnézze, mely számok hiányoznak, majd minden sorban, majd minden oszlopban, majd ellenőrizze, hogy nincs-e ismétlés 0-9 számjegyből. Ez bonyolultabbá válik, mivel a hiányzó számjegyek száma minden sorban, oszlopban és mátrixban következetlen (azaz a bal felső mátrix Hiányzik 4 számjegy, míg a jobb felső mátrix hiányzik 8 számjegy). A probléma megoldása nem lenne polinomiális futási idő., Ha azonban ezt a rejtvényt egy lehetséges megoldással táplálná, sokkal kevésbé lenne bonyolult ellenőrizni, hogy vannak-e ismétlések a sorokban, oszlopokban és mátrixokban. Ez egy egyszerű ellenőrzés, amelynek polinom futási ideje lenne.
lényegében az NP osztály problémáinak nincs polinom futási ideje megoldani, de polinom futási ideje van a megoldások ellenőrzésére (nehéz megoldani, könnyen ellenőrizhető egy adott válasz).
Reduction
ezt nem igazán tudom megmagyarázni a példák használatán kívül, tehát: két problémánk van, A és B, és tudjuk, hogy a B probléma egy P osztályú probléma., Ha az a probléma csökkenthető, vagy B problémává alakítható, és ez a redukció polinom időt vesz igénybe, akkor azt mondhatjuk, hogy az a szintén P osztályú probléma (A redukálható B-re).
Ez a koncepció fontos megérteni a másik két problémaosztályt.
NP-Hard problémák
a probléma NP-Hardnak minősül, ha egy megoldási algoritmus lefordítható bármilyen NP probléma megoldására. Akkor azt mondhatjuk, hogy ez a probléma legalább olyan nehéz, mint bármely NP probléma, de sokkal nehezebb vagy összetettebb lehet.,
NP-teljes problémák
NP-a teljes problémák olyan problémák, amelyek mind az NP, mind az NP-kemény osztályokban élnek. Ez azt jelenti, hogy az NP-teljes problémák polinom időben ellenőrizhetők, és hogy bármely NP-probléma polinom időben csökkenthető erre a problémára.
Az alábbiakban a különböző osztályterek venn diagramja látható.,
Remélhetőleg ezt tisztázhatta volna a dolgokat erről a témáról. Nyilvánvaló, hogy nagyon korlátozott ismereteim vannak. Csak azt gondoltam, hogy érdekes erről beszélni, és úgy tűnik, még magas szinten is, ez elég zavaró.