Вычислительная сложность: различия между версиями

Нет описания правки
'''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется '''теорией сложности вычислений'''. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа и выхода?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжера).
 
В частности, теория сложности вычислений определяет [[NP-полная задача|NP-полные задачи]], которые [[недетерминированная машина Тьюринга]] может решить за [[класс P|полиномиальное время]], тогда как для [[Детерминированная машина Тьюринга|детерминированной машины Тьюринга]] [[Равенство классов P и NP|полиномиальный алгоритм неизвестен]]. Обычно это сложные задачи оптимизации, например, [[Задача коммивояжёра|задача коммивояжёра]].
 
С [[теоретическая информатика|теоретической информатикой]] тесно связанныесвязаны стакие такими областямиобласти как [[алгоритмический анализ]] и [[теория вычислимости]]. Связующим звеном между теоретической информатикой и алгоритмическим анализом является тот факт, что их формирование посвящено анализу необходимого количества ресурсов определённых алгоритмов решения задач, тогда как более общим вопросом является возможность использования алгоритмов для подобных задач. Конкретизируясь, попытаемся классифицировать проблемы, которые могут или не могут быть решены при помощи ограниченных ресурсов. Сильное ограничение доступных ресурсов отличает вычислительнуютеорию вычислительной сложностьсложности от вычислительной теории, последняя отвечает на вопрос какие задачи, в принципе, могут быть решены алгоритмически.
 
== Временная и пространственная сложности ==
Анонимный участник