Disclaimer: obecnie jestem studentem w bootcampie z nauką o danych i jeszcze nie zajęliśmy się algorytmami. To jest coś, na co natknąłem się podczas robienia badań w moim własnym czasie. Myślałem, że to interesujący temat. Na pewno nie profesjonalista lub doświadczony z algorytmami jeszcze w ogóle. Mam nadzieję, że wkrótce będę.
z mojego podstawowego zrozumienia, wierzę, że te terminy dotyczą notacji Big-O dla algorytmów. Mam nadzieję, że mogę to opisać w bardzo zrozumiały sposób.,
krótkie podsumowanie, Big-O jest miarą tego, jak szybko algorytm działa lub rozwiązuje problem (zauważ, że jest to górna granica tego, jak długi jest czas działania).
P, NP, NP-Hard i np-Complete To klasy, do których każdy problem podlegałby lub byłby klasyfikowany.
problemy P (wielomian)
problemy P odnoszą się do problemów, w których algorytm zajęłby wielomian czasu na rozwiązanie, lub gdzie Big-O jest wielomianem(np. O(1), O(n), O (n2) itp.). Są to problemy, które można uznać za „łatwe” do rozwiązania, a zatem nie mają na ogół ogromnych czasów eksploatacji.,
problemy z np (niedeterministycznym wielomianem)
problemy z np były dla mnie trochę trudniejsze do zrozumienia, ale myślę, że takie właśnie są. Jeśli chodzi o rozwiązanie problemu NP, czas działania nie byłby wielomianowy. To byłoby coś w stylu O (n!) lub coś znacznie większego. Jednak ta klasa problemów może być podana konkretne rozwiązanie, a sprawdzenie rozwiązania będzie miało wielomian run-time. Przykładem, który pomógł mi zrozumieć to trochę lepiej była gra Sudoku.,
aby rozwiązać tę całą zagadkę, algorytm musiałby sprawdzić każdą macierz 3×3, aby zobaczyć, których liczb brakuje, następnie każdy wiersz, następnie każdą kolumnę, a następnie upewnić się, że nie ma powtórzeń żadnej cyfry od 0-9. To staje się bardziej skomplikowane, ponieważ liczba cyfr, które są brakujące jest niespójne w każdym wierszu, kolumnie i macierzy (TJ top-left macierz brakuje 4 cyfry, podczas gdy top-right macierz brakuje 8 cyfr). Rozwiązanie tego problemu nie będzie miało wielomianu run-time., Jednak, jeśli miałbyś karmić tę zagadkę z możliwym rozwiązaniem, byłoby znacznie mniej skomplikowane, aby sprawdzić, czy nie ma żadnych powtórzeń w wierszach, kolumnach i matrycach. Jest to proste sprawdzenie, które miałoby wielomian run-time.
w istocie problemy klasy NP nie mają wielomianu run-time do rozwiązania, ale mają wielomian run-time do weryfikacji rozwiązań (trudne do rozwiązania, łatwe do sprawdzenia dana odpowiedź).
redukcja
nie potrafię tego wyjaśnić poza użyciem przykładów, więc: mamy dwa problemy, A i B, i wiemy, że problem B jest problemem klasy P., Jeśli problem A może być zredukowany lub przekształcony w problem B, a redukcja ta zajmuje wielomian czasu, to możemy powiedzieć, że A jest również problemem klasy P (A jest redukowana do B).
ta koncepcja jest ważna do zrozumienia dla pozostałych dwóch klas problemów.
np-trudne problemy
problem jest klasyfikowany jako np-trudne, gdy algorytm do jego rozwiązania można przetłumaczyć, aby rozwiązać dowolny problem NP. Wtedy możemy powiedzieć, że problem ten jest co najmniej tak trudny jak każdy problem NP, ale może być znacznie trudniejszy lub bardziej złożony.,
np-Complete Problems
np-Complete problems to problemy, które występują zarówno w klasach np, jak i np-Hard. Oznacza to, że np-całkowite problemy można zweryfikować w czasie wielomianowym i że każdy problem NP można zredukować do tego problemu w czasie wielomianowym.
Poniżej znajduje się diagram Venna różnych przestrzeni klas.,
div id=”e9645738c9″>
mam nadzieję, że to mogło wyjaśnić rzeczy na ten temat. Oczywiście, mam bardzo ograniczoną wiedzę. Po prostu pomyślałem, że to interesujące rozmawiać o i wydaje się, nawet na wysokim poziomie, to jest dość mylące.