Złożoność obliczeniowa

Pojęcia informatyki

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Klasy złożoności

Klasy złożoności

Animacja przedstawiająca całą przestrzeń złożoności problemów

Obraz przedstawiający przestrzeń problemów P

Klasa złożoności -->	P (Czas wielomianowy)
Znaczenie	Rozwiązywalne szybko i wydajnie
Przykład	Sortowanie listy
Analogia	"Porządkowanie dokumentów alfabetycznie"
Kluczowa informacja	Problemy „łatwe" w sensie obliczeniowym

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Obraz przedstawiający przestrzeń problemów P i NP

Klasa złożoności -->	NP (Niedeterministyczny czas wielomianowy)
Znaczenie	Rozwiązanie weryfikowalne, ale trudne do znalezienia
Przykład	Weryfikacja poprawności sudoku
Analogia	"Szukanie dokumentu z brakującymi informacjami"
Kluczowa informacja	Weryfikacja rozwiązań jest „łatwa", ale znalezienie nowych – trudne

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Obraz przedstawiający przestrzeń problemów P, NP i NP-Complete

Klasa złożoności -->	NP-Complete
Znaczenie	Najtrudniejsza w NP. Rozwiązuje wszystkie problemy NP
Przykład	Problem komiwojażera
Analogia	"Układanie trudnych puzzli – weryfikacja łatwa, rozwiązanie trudne"
Kluczowa informacja	Brak wydajnego rozwiązania, ale jego znalezienie rozwiąże wszystkie problemy NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Obraz przedstawiający przestrzeń problemów P, NP, NP-Complete i NP-Hard

Klasa złożoności -->	NP-Hard
Znaczenie	Tak trudna jak NP-Complete lub trudniejsza
Przykład	Optymalne harmonogramowanie ze złożonymi zależnościami, nieweryfikowalne
Analogia	"Planowanie optymalnego spotkania z wieloma ograniczeniami, nieweryfikowalne szybko"
Kluczowa informacja	Może być praktycznie niemożliwa do rozwiązania

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Diagram przedstawiający odwieczne pytanie badawcze: czy P=NP?

Pojęcia informatyki