Вычислительная сложность

Основы информатики

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-Complete

Класс сложности -->	NP-Complete
Что это означает	Труднейшие задачи NP; решение одной решает все NP
Пример	Задача коммивояжёра
Аналогия	«Сложный пазл: проверить легко, собрать трудно»
Ключевой момент	Эффективного решения пока нет, но если найти — решатся все задачи NP

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

Изображение пространства задач классов P, NP, NP-Complete и NP-Hard

Класс сложности -->	NP-Hard
Что это означает	Не легче NP-Complete, возможно, сложнее
Пример	Оптимальное расписание со сложными зависимостями, без возможности проверки
Аналогия	«Найти оптимальное время встречи при множестве ограничений — и проверить невозможно»
Ключевой момент	На практике может оказаться неразрешимым

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

Схема с давним исследовательским вопросом: P = NP?

Основы информатики