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

В частности, теория сложности вычислений определяет [[NP-полная задача|NP-полные задачи]], которые [[недетерминированная машина Тьюринга]] может решить за [[класс P|полиномиальное время]], тогда как для [[Детерминированная машина Тьюринга|детерминированной машины Тьюринга]] [[Равенство классов P и NP|полиномиальный алгоритм неизвестен]]. Обычно это сложные задачи оптимизации, например, [[задача коммивояжёра]].
 
С [[теоретическая информатика|теоретической информатикой]] тесно связаны такие области как [[алгоритмический анализ алгоритмов]] и [[теория вычислимости]]. Связующим звеном между теоретической информатикой и алгоритмическим анализом является тот факт, что их формирование посвящено анализу необходимого количества ресурсов определённых алгоритмов решения задач, тогда как более общим вопросом является возможность использования алгоритмов для подобных задач. Конкретизируясь, попытаемся классифицировать проблемы, которые могут или не могут быть решены при помощи ограниченных ресурсов. Сильное ограничение доступных ресурсов отличает теорию вычислительной сложности от вычислительной теории, последняя отвечает на вопрос какие задачи, в принципе, могут быть решены алгоритмически.
 
== Временная и пространственная сложности ==
Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма [[сортировка вставками|сортировки вставками]] значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма ''в худшем случае''.
 
''[[Временная сложность алгоритма]]'' (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.
 
Аналогично понятию ''временной сложности в худшем случае'' определяется понятие ''временная сложность алгоритма в наилучшем случае''. Также рассматривают понятие ''среднее время работы алгоритма'', то есть [[математическое ожидание]] времени работы алгоритма. Иногда говорят просто: «''Временная сложность алгоритма''» или «''Время работы алгоритма''», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).
* Юрий Лифшиц ''«[http://yury.name/modern.html Современные задачи теоретической информатики]»''. Курс лекций по алгоритмам для NP-трудных задач.
* {{статья |автор=А. А. Разборов |заглавие=Theoretical Computer Science: взгляд математика |издание=[[Компьютерра]] |номер=2 |год=2001 |ссылка=http://old.computerra.ru/print/offline/2001/379/6782/}} ([http://www.mi.ras.ru/~razborov/computerra.ps альтернативная ссылка])
* {{статья |автор=А. А. Разборов |заглавие=О сложности вычислений |издание=[[Математическое просвещение]] |издательство=[[МЦНМО]] |серия=3-я серия |номер=3 |год=1999 |страницы=127-141127—141 |ссылка=http://www.mccme.ru/free-books/matpros/i4127141.pdf.zip}}
 
 
 
{{Классы сложности}}