Временная сложность алгоритма

Следующая таблица обобщает наиболее часто встречающиеся классы сложности. В таблице ${\displaystyle poly(x)}$ обозначает произвольный многочлен от ${\displaystyle x}$, то есть ${\displaystyle poly(x)=x^{O(1)}}$.

Название	Класс сложности	Время работы, ${\displaystyle T(n)}$	Примеры времени работы	Примеры алгоритмов
константное время		${\displaystyle O(1)}$	${\displaystyle 10}$	Определение чётности целого числа (представленного в двоичном виде)
обратная функция Аккермана		${\displaystyle O(\alpha (n))}$		Амортизационный анализ на одну операцию с использованием непересекающихся множеств
итерированно логарифмическое время		${\displaystyle O(\log ^{*}n)}$		Распределённые раскраски циклов
дважды логарифмическое		${\displaystyle O(\log \log n)}$		Время амортизации на одну операцию при использовании ограниченной очереди с приоритетами[2]
логарифмическое время	DLOGTIME	${\displaystyle O(\log n)}$	${\displaystyle \log n}$, ${\displaystyle \log n^{2}}$	Двоичный поиск
полилогарифмическое время		${\displaystyle poly(\log n)}$	${\displaystyle (\log n)^{2}}$
сублинейное время		${\displaystyle O(n^{c})}$ при ${\displaystyle 0<c<1}$	${\displaystyle n^{1/2}}$, ${\displaystyle n^{2/3}}$	Поиск в k-мерном дереве
линейное время		${\displaystyle O(n)}$	${\displaystyle n}$	Поиск наименьшего или наибольшего элемента в неотсортированном массиве
«n log-звёздочка n»		${\displaystyle O(n\log ^{*}n)}$		Алгоритм триангуляции многоугольника Зайделя.
линейно-логарифмическое время		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$, ${\displaystyle \log n!}$	Самая быстрая сортировка сравнением
квадратичное время		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	Сортировка пузырьком, сортировка вставками, прямая свёртка
кубическое время		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	Обычное умножение двух ${\displaystyle n\times n}$ матриц. Вычисление частичной корреляции.
полиномиальное время	P	${\displaystyle 2^{O(\log n)}=poly(n)}$	${\displaystyle n}$, ${\displaystyle n\log n}$, ${\displaystyle n^{10}}$	Алгоритм Кармаркара для линейного программирования, АКС-тест простоты
квазиполиномиальное время	QP	${\displaystyle 2^{poly(\log n)}}$	${\displaystyle n^{\log \log n}}$, ${\displaystyle n^{\log n}}$	Самый быстрый известный ${\displaystyle O(\log ^{2}n)}$ — аппроксимационный алгоритм для ориентированной задачи Штейнера.
субэкспоненциальное время (первое определение)	SUBEXP	${\displaystyle O(2^{n^{\varepsilon }})}$ для всех ${\displaystyle \varepsilon >0}$	${\displaystyle 2^{\log n^{\log \log n}}}$	Если принять теоретические гипотезы, BPP содержится в SUBEXP.[3]
субэкспоненциальное время (второе определение)		${\displaystyle 2^{o(n)}}$	${\displaystyle 2^{n^{1/3}}}$	Самые быстрые известные алгоритмы разложения на множители целых чисел и проверки изоморфизма графов
экспоненциальное время (с линейной экспонентой)	E	${\displaystyle 2^{O(n)}}$	${\displaystyle 1.1^{n}}$, ${\displaystyle 10^{n}}$	Решение задачи коммивояжёра с помощью динамического программирования
экспоненциальное время	EXPTIME	${\displaystyle 2^{poly(n)}}$	${\displaystyle 2^{n}}$, ${\displaystyle 2^{n^{2}}}$	Решение задачи о порядке перемножения матриц с помощью полного перебора
факториальное время		${\displaystyle O(n!)}$	${\displaystyle n!}$	Решение задачи коммивояжёра полным перебором
дважды экспоненциальное время	2-EXPTIME	${\displaystyle 2^{2^{poly(n)}}}$	${\displaystyle 2^{2^{n}}}$	Проверка верности заданного утверждения в арифметике Пресбургера

Говорят, что алгоритм является алгоритмом константного времени (записывается как время ${\displaystyle O(1)}$), если значение ${\displaystyle T(n)}$ ограничено значением, не зависящим от размера входа. Например, получение одного элемента в массиве занимает константное время, поскольку выполняется единственная команда для его обнаружения. Однако нахождение минимального значения в неотсортированном массиве не является операцией с константным временем, поскольку мы должны просмотреть каждый элемент массива. Таким образом, эта операция занимает линейное время, ${\displaystyle O(n)}$. Если число элементов известно заранее и не меняется, о таком алгоритме можно говорить как об алгоритме константного времени.

Несмотря на название «константное время», время работы не обязательно должно быть независимым от размеров задачи, но верхняя граница времени работы должна. Например, задача «обменять значения ${\displaystyle a}$ и ${\displaystyle b}$, если необходимо, чтобы в результате получили ${\displaystyle a\leq b}$», считается задачей константного времени, хотя время работы алгоритма может зависеть от того, выполняется ли уже неравенство ${\displaystyle a\leq b}$ или нет. Однако существует некая константа ${\displaystyle t}$, для которой время выполнения задачи всегда не превосходит ${\displaystyle t}$.

Ниже приведен пример кода, работающего за постоянное время:

int index = 5;
int item = list[index];
if (условие верно) then
   выполнить некоторые операции с постоянным временем работы
else
   выполнить некоторые операции с постоянным временем работы
for i = 1 to 100
   for j = 1 to 200
      выполнить некоторые операции с постоянным временем работы

Если ${\displaystyle T(n)}$ равно ${\displaystyle O(\alpha )}$, где ${\displaystyle \alpha }$ — константа, то это эквивалентно тому, что ${\displaystyle T(n)}$ равно ${\displaystyle O(1)}$.

Говорят, что алгоритм выполняется за логарифмическое время, если ${\displaystyle T(n)=O(\log n)}$. Поскольку в компьютерах принята двоичная система счисления, в качестве основания логарифма используется ${\displaystyle 2}$ (то есть ${\displaystyle \log _{2}n}$). Однако при замене основания логарифма ${\displaystyle \log _{a}n}$ и ${\displaystyle \log _{b}n}$ отличаются лишь на постоянный множитель ${\displaystyle \log _{b}a}$, который в записи O-большое отбрасывается. Таким образом, ${\displaystyle O(\log n)}$ является стандартной записью для алгоритмов логарифмического времени независимо от основания логарифма.

Алгоритмы, работающие за логарифмическое время, обычно встречаются при операциях с двоичными деревьями или при использовании двоичного поиска.

${\displaystyle O(\log n)}$ алгоритмы для работы с массивами данных размера ${\displaystyle n}$ считаются высокоэффективными, поскольку отношение времени выполнения одной операции к размеру массива уменьшается с увеличением этого размера.

Очень простой пример такого алгоритма — поиск слов в словаре. Рассмотрим словарь ${\displaystyle D}$, в котором записаны ${\displaystyle n}$ слов, отсортированных по алфавиту. При этом считаем, что все слова имеют длину ${\displaystyle O(1)}$ и что мы можем за константное время получить доступ к любому элементу словаря по индексу. Пусть ${\displaystyle D(k)}$ — это ${\displaystyle k}$-й элемент словаря, тогда можно проверить, лежит ли слово ${\displaystyle \omega }$ в словаре за ${\displaystyle O(\log n)}$. Для этого нужно рассмотреть элемент словаря ${\displaystyle D(\lfloor n/2\rfloor )}$, где ${\displaystyle \lfloor ~\rfloor }$ обозначает округление числа вниз. Если ${\displaystyle D(\lfloor n/2\rfloor )<\omega }$, то нам стоит перейти в правую половину массива, иначе — в левую. В конце мы получим индекс первого слова, который равен или лексикографически больше, чем ${\displaystyle \omega }$.

int find(vector<string> &D, string w) {
    int n = D.size();
    int l = -1, r = n;
    while(r - l > 1) {
        int m = (l + r) / 2;
        if(D[m] < w) {
            l = m;
        } else {
            r = m;
        }
    }
    return r;
}

Говорят, что алгоритм работает за полилогарифмическое время, если ${\displaystyle T(n)=O(\log ^{k}n)}$ для некоторого ${\displaystyle k}$. Например, задача о порядке перемножения матриц может быть решена за такое время на параллельной РАМ-машине[4].

Говорят, что алгоритм выполняется за сублинейное время, если ${\displaystyle T(n)=o(n)}$. В частности, сюда включаются алгоритмы, чья временная сложность соответствует указанным выше, а также, например, поиск Гровера со сложностью ${\displaystyle O(n^{1/2})}$.

Обычно алгоритмы, которые, являясь точными, всё же работают за сублинейное время, используют распараллеливание процессов (как это делает алгоритм NC₁ вычисления определителя матрицы), неклассические вычисления (как в поиске Гровера) или имеют гарантированное предположение о структуре входа (как алгоритмы двоичного поиска и многие алгоритмы обработки деревьев). Однако такие формальные языки как язык слов, имеющих единичный бит в позиции, определяемой первыми ${\displaystyle \log n}$ битами слова, могут быть разрешимыми за сублинейное время даже не смотря на то, что любой бит может быть важен для определения принадлежности слова языку.

Термин алгоритм с сублинейным временем работы обычно используется для алгоритмов, которые, в отличие от приведённых выше примеров, работают на обычных последовательных моделях машин и не предполагают априорных знаний о структуре входа[5]. Однако для них допускается применение вероятностных методов и даже более того, зачастую они должны быть рандомизированными для любой нетривиальной задачи.

Так как такой алгоритм обязан давать ответ без полного чтения входных данных, он в очень сильной степени зависит от способов доступа, разрешённых во входном потоке. Обычно для потока, представляющего собой битовую строку ${\displaystyle b_{1},\dots ,b_{k}}$, предполагается, что алгоритм может за время ${\displaystyle O(1)}$ запросить значение ${\displaystyle b_{i}}$ для любого ${\displaystyle i}$.

Алгоритмы сублинейного времени, как правило, вероятностны и дают лишь аппроксимированное решение. Алгоритмы сублинейного времени выполнения возникают естественным образом при исследовании проверки свойств.

Говорят, что алгоритм работает за линейное время, или за время ${\displaystyle O(n)}$, если его сложность равна ${\displaystyle O(n)}$. Неформально, это означает, что для достаточно большого размера входных данных время работы увеличивается линейно от размера входа. Например, процедура, суммирующая все элементы списка, требует время, пропорциональное длине списка. Это описание не вполне точно, поскольку время работы может существенно отличаться от точной пропорциональности, особенно для малых значений ${\displaystyle n}$.

Линейное время часто рассматривается как желательный атрибут алгоритма[6]. Было проведено много исследований для создания алгоритмов с (почти) линейным или лучшим временем работы. Эти исследования включали как программные, так и аппаратные подходы. В случае аппаратного исполнения некоторые алгоритмы, которые, с математической точки зрения, никогда не могут достичь линейного времени исполнения в стандартных моделях вычислений, могут работать за линейное время. Существуют некоторые аппаратные технологии, которые используют параллельность для достижения такой цели. Примером служит ассоциативная память. Эта концепция линейного времени используется в задачах сопоставления с образцом, таких как алгоритм Бойера — Мура и алгоритм Укконена.

Говорят, что алгоритм работает за квазилинейное время, если ${\displaystyle T(n)=O(n\log ^{k}n)}$ для некоторой константы ${\displaystyle k}$. При ${\displaystyle k=1}$ говорят о линейно-логарифмическом времени[7]. В терминах soft-O такое время работы записывается как ${\displaystyle {\tilde {O}}(n)}$. Для алгоритмов с квазилинейным временем работы также верна оценка ${\displaystyle T(n)\in o(n^{1+\varepsilon })}$ для любого ${\displaystyle \varepsilon >0}$. Таким образом, эти алгоритмы работают быстрее любого полинома от ${\displaystyle n}$, степень которого больше ${\displaystyle 1}$.

Алгоритмы, работающие за квазилинейное время, вдобавок к линейно-логарифмическим алгоритмам, упомянутым выше, включают:

• Сортировка слиянием на месте: ${\displaystyle O(n\log ^{2}n)}$;
• Быстрая сортировка: математическое ожидание времени работы вероятностной версии алгоритма лежит в ${\displaystyle O(n\log n)}$ на любом входе, для детерминированной же версии эта оценка верна только в среднем по всем входам;
• Сортировка кучей, сортировка слиянием, introsort, сортировка с помощью бинарного дерева, плавная сортировка, пасьянсная сортировка, и другие: ${\displaystyle O(n\log n)}$ в худшем случае;
• Быстрое преобразование Фурье: ${\displaystyle O(n\log n)}$;
• Алгоритмы на матрицах Монжа: ${\displaystyle O(n\log n)}$.

Говорят, что алгоритм выполняется за субквадратичное время, если ${\displaystyle T(n)=o(n^{2})}$.

Например, простые алгоритмы сортировки, основанные на сравнениях (такие как сортировка вставками), квадратичны. В то же время можно найти более продвинутые алгоритмы, которые имеют субквадратичное время выполнения (например, сортировка Шелла). Никакие сортировки общего вида не работают за линейное время, но переход от квадратичного к субквадратичному времени имеет большую практическую важность.

Говорят, что алгоритм работает за полиномиальное время, если время работы ограничено сверху многочленом от размера входа алгоритма, то есть ${\displaystyle T(n)=O(n^{k})}$ для некоторой константы ${\displaystyle k}$[1][9]. Задачи, для которых алгоритмы с детерминированным полиномиальным временем существуют, составляют класс сложности P, который является центральным в теории вычислительной сложности. Тезис Кобэма утверждает, что полиномиальное время является синонимом понятий «легко поддающийся обработке», «выполнимый», «эффективный» или «быстрый»[10].

Некоторые примеры полиномиальных алгоритмов:

• Алгоритм быстрой сортировки ${\displaystyle n}$ целых чисел делает максимум ${\displaystyle An^{2}}$ операций для некоторой константы ${\displaystyle A}$. Таким образом, он работает за ${\displaystyle O(n^{2})}$ и является полиномиальным алгоритмом.
• Все базовые арифметические операции (сложение, вычитание, умножение, деление и сравнение) могут быть выполнены за полиномиальное время.
• Максимальное паросочетание в графах может быть найдено за полиномиальное время.

Говорят, что алгоритм работает за суперполиномиальное время, если T(n) не ограничен сверху полиномом. Это время равно ω(n^c) для всех констант c, где n — входной параметр, обычно — число бит входа.

Например, алгоритм, осуществляющий 2ⁿ шагов, для входа размера n требует суперполиномиального времени (конкретнее, экспоненциального времени).

Ясно, что алгоритм, использующий экспоненциальные ресурсы, суперполиномиален, но некоторые алгоритмы очень слабо суперполиномиальны. Например, тест простоты Адлемана — Померанса — Румели работает за время n^{O(log log n)} на n-битном входе. Это растёт быстрее, чем любой полином, для достаточно большого n, но размер входа должен стать очень большим, чтобы он не доминировался полиномом малой степени.

Алгоритм, требующий суперполиномиального времени, лежит вне класса сложности P. Тезис Кобэма утверждает, что эти алгоритмы непрактичны, и во многих случаях это так. Поскольку задача равенства классов P и NP не решена, никаких алгоритмов для решения NP-полных задач за полиномиальное время в настоящее время не известно.

Алгоритмы квазиполиномиального времени — это алгоритмы, работающие медленнее, чем за полиномиальное время, но не столь медленно, как алгоритмы экспоненциального времени. Время работы в худшем случае для квазиполиномиального алгоритма равно ${\displaystyle 2^{O((\log n)^{c})}}$ для некоторого фиксированного c. Хорошо известный классический алгоритм разложения целого числа на множители, общий метод решета числового поля, который работает за время около ${\displaystyle 2^{{\tilde {O}}(n^{1/3})}}$, не является квазиполиномиальным, поскольку время работы нельзя представить как ${\displaystyle 2^{O((\log n)^{c})}}$ для некоторого фиксированного c. Если константа «c» в определении алгоритма квазиполиномиального времени равна 1, мы получаем алгоритм полиномиального времени, а если она меньше 1, мы получаем алгоритм сублинейного времени.

Алгоритмы квазиполиномиального времени обычно возникают при сведении NP-трудной задачи к другой задаче. Например, можно взять NP-трудную задачу, скажем, 3SAT, и свести её к другой задаче B, но размер задачи станет равным ${\displaystyle 2^{O((\log n)^{c})}}$. В этом случае сведение не доказывает, что задача B NP-трудна, такое сведение лишь показывает, что не существует полиномиального алгоритма для B, если только не существует квазиполиномиального алгоритма для 3SAT (а тогда и для всех NP-задач). Подобным образом — существуют некоторые задачи, для которых мы знаем алгоритмы с квазиполиномиальным временем, но для которых алгоритмы с полиномиальным временем неизвестны. Такие задачи появляются в аппроксимационых алгоритмах. Знаменитый пример — ориентированная задача Штайнера, для которой существует аппроксимационный квазиполиномиальный алгоритм с аппроксимационным коэффициентом ${\displaystyle O(\log ^{3}n)}$ (где n — число вершин), но существование алгоритма с полиномиальным временем является открытой проблемой.

Класс сложности QP состоит из всех задач, имеющих алгоритмы квазиполиномиального времени. Его можно определить в терминах DTIME следующим образом[13]:

${\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})}$

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

Говорят, что алгоритм работает за экспоненциальное время, если T(n) ограничено сверху значением 2^poly(n), где poly(n) — некий многочлен от n. Более формально, алгоритм работает за экспоненциальное время, если T(n) ограничено O(2^nk) с некоторой константой k. Задачи, которые выполняются за экспоненциальное время на детерминированных машинах Тьюринга, образуют класс сложности EXP.

${\displaystyle {\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)}$

Иногда термин экспоненциальное время используется для алгоритмов, для которых T(n) = 2^O(n), где показатель является не более чем линейной функцией от n. Это приводит к классу сложности E.

${\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)}$

Говорят, что алгоритм выполняется за дважды экспоненциальное время, если T(n) ограничено сверху значением 2^2poly(n), где poly(n) — некоторый многочлен от n. Такие алгоритмы принадлежат классу сложности 2-EXPTIME.

${\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{2^{n^{c}}})}$

К хорошо известным дважды экспоненциальным алгоритмам принадлежат:

• Процедура вычисления для арифметики Пресбургера
• Вычисление базиса Грёбнера (в худшем случае[23])
• Элиминация кванторов в вещественно замкнутых полях требует как минимум дважды экспоненциальное время выполнения[24] и может быть выполнена за это время[25].

• L-нотация
• Сложность по памяти