Disclaimer: v současné době jsem studentem bootcampu pro vědu o datech a ještě jsme se nedostali do algoritmů. To je jen něco, na co jsem narazil, když jsem dělal nějaký výzkum ve svém vlastním čase. Myslel jsem, že je to zajímavé téma. Rozhodně ještě není profesionál nebo zkušený s algoritmy. Snad budu brzy.
z mého základního porozumění se domnívám, že tyto pojmy se zabývají notací Big-O pro algoritmy. Doufejme, že to dokážu pokrýt velmi srozumitelným způsobem.,
stručné shrnutí, Big-O je měřítkem toho, jak rychle algoritmus běží nebo řeší problém(všimněte si, že je to horní hranice toho, jak dlouhá je doba běhu).
P, NP, NP-Hard a NP-Complete jsou třídy, které by jakýkoli problém spadal nebo by byl klasifikován jako.
P (Polynom) problémy
P problémy odkazují na problémy, kde algoritmus by se polynom množství času k řešení, nebo kde je Big-O je polynomiální (tj. O(1), O(n), O(n2), atd.). Jedná se o problémy, které by byly považovány za „snadné“ vyřešit, a proto obecně nemají obrovské doby běhu.,
NP (non-deterministický polynom) problémy
NP problémy byly trochu těžší pro mě pochopit, ale myslím, že to je to, co jsou. Pokud jde o řešení problému NP, run-time by nebyl polynomiální. Bylo by to něco jako O (n!) nebo něco mnohem většího. Tato třída problémů však může mít konkrétní řešení a kontrola řešení by měla polynomiální run-time. Příkladem, který mi pomohl pochopit to trochu lépe, byla hra Sudoku.,
s cílem vyřešit celou puzzle, algoritmus by musel kontrolovat každý 3×3 matice zjistit, které čísla chybí, pak každý řádek, každý sloupec, a pak se ujistěte, že neexistují žádné opakování jakékoliv číslice od 0-9. To se stává složitějším, protože počet chybějících číslic je v každém řádku, sloupci a matici nekonzistentní (tj. matice vlevo nahoře chybí 4 číslice, zatímco matice vpravo nahoře chybí 8 číslic). Řešení tohoto problému by nemělo polynomiální run-time., Pokud byste však měli tuto hádanku nakrmit možným řešením, bylo by mnohem méně složité zkontrolovat, zda jsou v řádcích, sloupcích a matricích nějaké opakování. Jedná se o jednoduchou kontrolu, která by měla polynomiální run-time.
v podstatě problémy třídy NP nemají polynomiální run-time k řešení, ale mají polynomiální run-time k ověření řešení (obtížné vyřešit, snadno zkontrolovat danou odpověď).
redukce
nemohu to vysvětlit mimo použití příkladů, takže: máme dva problémy, A A B a víme, že problém B je problém třídy P., Pokud problém může být snížen nebo převeden na problém B, a toto snížení trvá polynom množství času, pak můžeme říci, že je také P class problém (A je redukovatelné na B).
tento koncept je důležité pochopit pro další dvě třídy problémů.
NP-tvrdé problémy
problém je klasifikován jako NP-Hard, když algoritmus pro jeho řešení může být přeložen k vyřešení jakéhokoli problému NP. Pak můžeme říci, že tento problém je přinejmenším stejně těžký jako jakýkoli problém NP, ale může to být mnohem těžší nebo složitější.,
NP-kompletní problémy
NP-kompletní problémy jsou problémy, které žijí jak v NP, tak v NP-Hard třídách. To znamená, že NP-kompletní problémy mohou být ověřeny v polynomiálním čase a že jakýkoli problém NP může být redukován na tento problém v polynomiálním čase.
níže je venn diagram různých třídních mezer.,
Doufejme, že to mohl vyjasnili o tomto tématu. Samozřejmě mám velmi omezené znalosti. Jen jsem si myslel, že je zajímavé o tom mluvit a vypadá to, že i na vysoké úrovni je to docela matoucí.