Обчислювальна складність

Концепції комп'ютерних наук

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Класи складності

Класи складності

Анімація, що показує весь простір складності задач

Зображення, що показує простір задач P

Клас складності -->	P (поліноміальний час)
Що це означає	Розв'язується швидко й ефективно
Приклад	Сортування списку
Аналогія	«Розкласти документи за абеткою»
Головна ідея	Це «легкі» задачі в обчислювальному сенсі

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

Зображення, що показує простір задач P і NP

Клас складності -->	NP (недетермінований поліноміальний час)
Що це означає	Розв'язок легко перевірити, знайти новий важко
Приклад	Перевірити правильність судоку
Аналогія	«Знайти конкретний документ із браком відомостей»
Головна ідея	Перевірка «легка», пошук розв'язку — складний

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

Зображення, що показує простір задач P, NP і NP-повні

Клас складності -->	NP-повні
Що це означає	Найскладніші в NP; особливі тим, що зводять усі NP
Приклад	Задача комівояжера
Аналогія	«Складний пазл: легко перевірити, важко скласти»
Головна ідея	Ефективного розв'язку не відомо; якби знайшли — розв'язали б усі NP

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

Зображення, що показує простір задач P, NP, NP-повні та NP-складні

Клас складності -->	NP-складні
Що це означає	Не простіші за NP-повні, а часто складніші
Приклад	Оптимальне планування зі складними залежностями, розв'язок не перевірити
Аналогія	«Підібрати оптимальний час зустрічі з багатьма обмеженнями, швидко не перевірити»
Головна ідея	Практично може бути нерозв'язно

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

Схема з класичним дослідницьким питанням: чи P=NP?

Концепції комп'ютерних наук