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

Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций, битовых операций или операций на машине Тьюринга), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.

Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используются асимптотические обозначения:

Обозначение	Интуитивное объяснение	Определение
${\displaystyle f(n)\in O(g(n))}$	${\displaystyle f}$ ограничена сверху функцией ${\displaystyle g}$ (с точностью до постоянного множителя) асимптотически	${\displaystyle \exists (C>0),n_{0}:\forall (n>n_{0})\;|f(n)|\leq |Cg(n)|}$ или ${\displaystyle \exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)}$
${\displaystyle f(n)\in \Omega (g(n))}$	${\displaystyle f}$ ограничена снизу функцией ${\displaystyle g}$ (с точностью до постоянного множителя) асимптотически	${\displaystyle \exists (C>0),n_{0}:\forall (n>n_{0})\;|Cg(n)|\leq |f(n)|}$
${\displaystyle f(n)\in \Theta (g(n))}$	${\displaystyle f}$ ограничена снизу и сверху функцией ${\displaystyle g}$ асимптотически	${\displaystyle \exists (C,C'>0),n_{0}:\forall (n>n_{0})\;|Cg(n)|\leq |f(n)|\leq |C'g(n)|}$
${\displaystyle f(n)\in o(g(n))}$	${\displaystyle g}$ доминирует над ${\displaystyle f}$ асимптотически	${\displaystyle \forall (C>0),\exists n_{0}:\forall (n>n_{0})\;|f(n)|<|Cg(n)|}$
${\displaystyle f(n)\in \omega (g(n))}$	${\displaystyle f}$ доминирует над ${\displaystyle g}$ асимптотически	${\displaystyle \forall (C>0),\exists n_{0}:\forall (n>n_{0})\;|Cg(n)|<|f(n)|}$
${\displaystyle f(n)\sim g(n)}$	${\displaystyle f}$ эквивалентна ${\displaystyle g}$ асимптотически	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1}$

• «почистить ковёр пылесосом» требует время, линейно зависящее от его площади (${\displaystyle \Theta (A)}$), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз объём работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
• «найти имя в телефонной книге» требует всего лишь времени, логарифмически зависящего от количества записей (${\displaystyle O(\log _{2}(n))}$), так как, открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге объёмом в 1000 страниц любое имя находится не больше, чем за ${\displaystyle \log _{2}1000\approx 10}$ раз (открываний книги). При увеличении объёма страниц до ста тысяч проблема все ещё решается за ${\displaystyle \log _{2}100000\approx 17}$ заходов. (См. Двоичный поиск.)

Поскольку ${\displaystyle \log _{a}b={\frac {\log _{c}b}{\log _{c}a}}}$, в асимптотической оценке сложности часто пишут «логарифм» без упоминания основания — например, ${\displaystyle O(n\log n)}$.

Необходимо подчеркнуть, что степень роста наихудшего времени выполнения — не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения:

Если создаваемая программа будет использована только несколько раз, тогда стоимость написания и отладки программы будет доминировать в общей стоимости программы, то есть фактическое время выполнения не окажет существенного влияния на общую стоимость. В этом случае следует предпочесть алгоритм, наиболее простой для реализации.

Если программа будет работать только с «малыми» входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения[1]. Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения, асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов. Другой пример — фибоначчиевы кучи, несмотря на асимптотическую эффективность, с практической точки зрения программная сложность реализации и большие значения констант в формулах времени работы делают их менее привлекательными, чем обычные бинарные деревья[1].

Известны примеры, когда эффективные алгоритмы требуют таких больших объёмов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма. Таким образом, часто важна не только «сложность по времени», но и «сложность по памяти» (пространственная сложность).

В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть время решения которых полиномиально зависит от размера входа. Сюда относится сортировка, поиск в массиве, выяснение связности графов и многие другие.

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество шагов от размера входных данных. Их решение может быть проверено детерминированной машиной Тьюринга за полиномиальное количество шагов. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Поскольку детерминированная машина Тьюринга может рассматриваться как специальный случай недетерминированной машины Тьюринга, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.

Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.