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

м
Удаление принудительных пробелов в формулах по ВП:РДБ.
м (Удаление принудительных пробелов в формулах по ВП:РДБ.)
'''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется '''теорией сложности вычислений'''. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[Вычислительные ресурсы|вычислительными ресурсами]]. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на [[носитель информации|носителе данных]]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в [[бит]]ах (например, в [[задача коммивояжёра|задаче коммивояжёра]] длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжера).
 
В частности, теория сложности вычислений определяет [[NP-полная задача|NP-полные задачи]], которые [[недетерминированная машина Тьюринга]] может решить за [[класс P|полиномиальное время]], тогда как для [[Детерминированная машина Тьюринга|детерминированной машины Тьюринга]] [[Равенство классов P и NP|полиномиальный алгоритм неизвестен]]. Обычно это сложные задачи оптимизации, например, [[Задача коммивояжёра|задача коммивояжёра]].
 
С [[теоретическая информатика|теоретической информатикой]] тесно связаны такие области как [[алгоритмический анализ]] и [[теория вычислимости]]. Связующим звеном между теоретической информатикой и алгоритмическим анализом является тот факт, что их формирование посвящено анализу необходимого количества ресурсов определённых алгоритмов решения задач, тогда как более общим вопросом является возможность использования алгоритмов для подобных задач. Конкретизируясь, попытаемся классифицировать проблемы, которые могут или не могут быть решены при помощи ограниченных ресурсов. Сильное ограничение доступных ресурсов отличает теорию вычислительной сложности от вычислительной теории, последняя отвечает на вопрос какие задачи, в принципе, могут быть решены алгоритмически.
 
=== Асимптотическая сложность ===
 
Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения ''элементарных операций'' (например, сложность можно измерять в количестве [[арифметика|арифметических]] операций, [[Сложность вычисления (битовая)|битовых]] операций или операций на [[машина Тьюринга|машине Тьюринга]]), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
 
|<math>\forall (C>0),\exists n_0 : \forall(n>n_0) \; |Cg(n)| < |f(n)|</math>
|-
|<math>f(n) \sim g(n)\!</math>
|<math>f</math> эквивалентна <math>g</math> асимптотически
|<math>\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1</math>
 
=== Примеры ===
 
* '''«почистить ковёр пылесосом»''' требует время, линейно зависящее от его площади (<math>\Theta(A)</math>), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объём работы увеличивается [[Пропорция (математика)|строго пропорционально]] в сто тысяч раз, и т. п.
* '''«найти имя в телефонной книге»''' требует всего лишь время, [[логарифм]]ически зависящее от количества записей (<math>O(\log_2(n))</math>), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за <math>\log_2 1000 \approx 10</math> раз (открываний книги). При увеличении объёма страниц до ста тысяч, проблема все ещё решается за <math>\log_2 100000 \approx 17</math> заходов. (См. [[Двоичный поиск]].)
 
=== Замечания ===
Поскольку <math>\log_a b = \frac{\log_c b}{\log_c a}</math>, в асимптотической оценке сложности часто пишут «логарифм» без упоминания основания — например, <math>O(n \log n)~</math>.
 
Поскольку <math>\log_a b = \frac{\log_c b}{\log_c a}</math>, в асимптотической оценке сложности часто пишут «логарифм» без упоминания основания — например, <math>O(n \log n)~</math>.
 
Необходимо подчеркнуть, что степень роста наихудшего времени выполнения — не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения:
 
== Исследователи ==
 
* [[Стивен Кук]]
* [[Ричард Карп]]
* {{статья |автор=А. А. Разборов |заглавие=О сложности вычислений |издание=[[Математическое просвещение]] |издательство=[[МЦНМО]] |серия=3-я серия |номер=3 |год=1999 |страницы=127-141 |ссылка=http://www.mccme.ru/free-books/matpros/i4127141.pdf.zip}}
 
[[Категория:Теория сложности вычислений|*]]
 
 
{{Классы сложности}}
 
[[Категория:Теория сложности вычислений|*]]
300 072

правки