Výpočetní složitost

Koncepty v informatice

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Třídy složitosti

Třídy složitosti

Animace znázorňující celý prostor tříd výpočetní složitosti

Obrázek znázorňující prostor problémů P

Třída složitosti -->	P (Polynomiální čas)
Co znamená	Řešitelné rychle a efektivně
Příklad	Řazení seznamu
Analogie	"Abecední řazení dokumentů"
Klíčový bod	Výpočetně "snadné" problémy

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

Obrázek znázorňující prostor problémů P a NP

Třída složitosti -->	NP (Nedeterministický polynomiální čas)
Co znamená	Řešení ověřitelné, nalezení nového řešení obtížné
Příklad	Ověření správnosti sudoku
Analogie	"Hledání dokumentu s chybějícími informacemi"
Klíčový bod	Ověřování je "snadné", hledání nových řešení je obtížné

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

Obrázek znázorňující prostor problémů P, NP a NP-Complete

Třída složitosti -->	NP-Complete
Co znamená	Nejtěžší v NP. Řeší všechny NP problémy
Příklad	Problém obchodního cestujícího
Analogie	"Složité puzzle – snadno ověřitelné, těžko řešitelné"
Klíčový bod	Žádné známé efektivní řešení, ale pokud existuje, vyřeší všechny NP

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

Obrázek znázorňující prostor problémů P, NP, NP-Complete a NP-Hard

Třída složitosti -->	NP-Hard
Co znamená	Stejně těžké jako NP-Complete nebo těžší
Příklad	Optimální rozvrhování s komplexními závislostmi a bez ověřitelnosti
Analogie	"Plánování schůzky s mnoha omezeními, které nelze rychle ověřit"
Klíčový bod	Praktické řešení může být nemožné

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

Diagram znázorňující věčnou výzkumnou otázku: je P=NP?

Koncepty v informatice