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

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

Поскольку время работы алгоритма может различаться для разных входных данных одного и того же размера, обычно рассматривают временную сложность наихудшего случая , которая представляет собой максимальное количество времени, необходимое для входных данных заданного размера. Менее распространенным и обычно указываемым явно является сложность среднего случая , которая представляет собой среднее время, затраченное на входные данные заданного размера (это имеет смысл, поскольку существует только конечное число возможных входных данных заданного размера). В обоих случаях временная сложность обычно выражается как функция размера входных данных. ^[1]^: 226 Поскольку эту функцию, как правило, трудно вычислить точно, а время выполнения для небольших входных данных обычно не имеет существенного значения, обычно основное внимание уделяется поведению сложности при увеличении размера входных данных, то есть асимптотическому поведению сложности. Поэтому временная сложность обычно выражается с использованием обозначения большого О , обычно $O(n)$ , $O(n\log n)$ , $O(n^{\alpha })$ , $O(2^{n})$ и т. д., где $n$ — размер в битах , необходимый для представления входных данных.

Алгоритмические сложности классифицируются в зависимости от типа функции, обозначаемой большой буквой О. Например, алгоритм с временной сложностью $O(n)$ это алгоритм с линейным временем и алгоритм с временной сложностью $O(n^{\alpha })$ для некоторой константы $\alpha >1$ это алгоритм с полиномиальным временем .

Таблица распространенных временных сложностей

В следующей таблице приведены некоторые классы часто встречающихся временных сложностей. В таблице поли( x ) = x ^{О (1)}, т. е. полиномиальный по x .

Имя	Класс сложности	Временная сложность ( $O (n)$ )	Примеры времени работы	Примеры алгоритмов
постоянное время		$O(1)$	10	Нахождение медианного значения в отсортированном массиве чисел. Вычисление $(-1) н$ .
Аккермана обратное время		$O{\bigl (}\alpha (n){\bigr )}$		Амортизированное время на операцию с использованием непересекающегося набора
итерированное логарифмическое время		$O(\log ^{*}n)$		Распределенная раскраска циклов
лог-логарифмический		$O(\log \log n)$		Амортизированное время на операцию с использованием очереди с ограниченным приоритетом. ^[2]
логарифмическое время	ДЛОГТАЙМ	$O(\log n)$	$\log n$ , $\log(n^{2})$	Бинарный поиск
полилогарифмическое время		${\text{poly}}(\log n)$	$(\log n)^{2}$
дробная мощность		$O(n^{c})$ где $0<c<1$	$n^{\frac {1}{2}}$ , $n^{\frac {2}{3}}$	Поиск диапазона в дереве k -d
линейное время		$O(n)$	$н$ , $2n+5$	Поиск наименьшего или наибольшего элемента в несортированном массиве . Алгоритм Кадане . Линейный поиск .
"n log-star n" время		$O(n\log ^{*}n)$		Зейделя многоугольников Алгоритм триангуляции .
линеарифмическое время		$O(n\log n)$	$n\log n$ , $\log n!$	Самая быстрая сортировка сравнения . Быстрое преобразование Фурье .
квазилинейное время		$n{\text{poly}}(\log n)$	$n\log ^{2}n$	Многоточечная полиномиальная оценка
квадратичное время		$O(n^{2})$	$n^{2}$	Пузырьковая сортировка . Сортировка вставками . Прямая свертка
кубическое время		$O(n^{3})$	$n^{3}$	Наивное умножение двух $n\times n$ матрицы. Расчет частичной корреляции .
полиномиальное время	П	$2^{O(\log n)}={\text{poly}}(n)$	$n^{2}+n$ , $n^{10}$	Алгоритм Кармаркара для линейного программирования . Тест на простоту AKS ^[3]^[4]
квазиполиномиальное время	QP	$2^{{\text{poly}}(\log n)}$	$n^{\log \log n}$ , $n^{\log n}$	Самый известный $O (журнал 2 n)$ — алгоритм аппроксимации направленной задачи дерева Штейнера , самый известный игр на четность , решатель ^[5] самый известный изоморфизма графов алгоритм
субэкспоненциальное время (первое определение)	СУБЭКСП	$O(2^{n^{\epsilon }})$ для всех $\epsilon >0$		Содержит BPP, если только EXPTIME (см. ниже) не равно MA . ^[6]
субэкспоненциальное время (второе определение)		$2^{o(n)}$	$2^{\sqrt[{3}]{n}}$	Лучший классический алгоритм факторизации целых чисел ранее лучший алгоритм изоморфизма графов
экспоненциальное время (с линейным показателем)	И	$2^{O(n)}$	$1.1^{n}$ , $10^{n}$	Решение задачи коммивояжера с помощью динамического программирования.
факториальное время		$O(n)!=2^{O(n\log n)}$	$n!,n^{n},2^{n\log n}$	Решение задачи коммивояжера методом перебора
экспоненциальное время	ВРЕМЯ ЭКСПРЕСС	$2^{{\text{poly}}(n)}$	$2^{n}$ , $2^{n^{2}}$	Решение умножения цепочки матриц методом перебора
двойное экспоненциальное время	2-ВРЕМЯ ЭКСПЛУАТАЦИИ	$2^{2^{{\text{poly}}(n)}}$	$2^{2^{n}}$	Определение истинности данного утверждения в арифметике Пресбургера

Постоянное время

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

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

Логарифмическое время

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

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

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

Пример логарифмического времени дается поиском по словарю. Рассмотрим словарь $D$ , который содержит $n$ записей, отсортированных в алфавитном порядке . Мы полагаем, что для $1\leq k\leq n$ , можно получить доступ к $k$ -й записи словаря за постоянное время. Позволять $D(k)$ обозначим эту $k-$ ю запись. Согласно этим гипотезам, проверка наличия слова $w$ в словаре может выполняться за логарифмическое время: рассмотрим $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ , где $\lfloor \;\rfloor$ обозначает функцию пола . Если $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ — то есть слово $w$ находится точно в середине словаря — и все готово. Иначе, если $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ --т.е. если слово $w$ стоит раньше в алфавитном порядке, чем среднее слово всего словаря -- продолжаем поиск таким же образом в левой (т.е. более ранней) половине словаря, а затем снова неоднократно до тех пор, пока не будет найдено правильное слово найдено. В противном случае, если оно идет после среднего слова, продолжайте аналогично с правой половиной словаря. Этот алгоритм аналогичен методу, который часто используется для поиска записи в бумажном словаре. В результате пространство поиска в словаре уменьшается по мере приближения алгоритма к целевому слову.

Полилогарифмическое время

Говорят, что алгоритм работает за полилогарифмическое время , если его время $T(n)$ является $O{\bigl (}(\log n)^{k}{\bigr )}$ для некоторой постоянной $k$ . Другой способ написать это $O(\log ^{k}n)$ .

Например, упорядочение цепочек матриц можно решить за полилогарифмическое время на параллельной машине с произвольным доступом . ^[7] и граф может быть определен как планарный способом полностью динамическим в $O(\log ^{3}n)$ время на операцию вставки/удаления. ^[8]

Сублинейное время

Говорят, что алгоритм работает в сублинейном времени (часто называемом сублинейным временем ), если $T(n)=o(n)$ . В частности, сюда входят алгоритмы с временной сложностью, определенной выше.

Конкретный термин «алгоритм сублинейного времени» обычно относится к рандомизированным алгоритмам, которые выбирают небольшую часть входных данных и эффективно обрабатывают их, чтобы приблизительно определить свойства всего экземпляра. ^[9] Этот тип алгоритма сублинейного времени тесно связан с тестированием свойств и статистикой .

Другие настройки, при которых алгоритмы могут работать в сублинейном времени, включают:

Параллельные алгоритмы , которые имеют линейную или большую общую работу (что позволяет им читать весь ввод), но сублинейную глубину .
Алгоритмы, которые имеют гарантированные предположения о структуре входных данных. Важным примером являются операции со структурами данных , например двоичный поиск в отсортированном массиве.
Алгоритмы, которые ищут локальную структуру на входе, например, находят локальный минимум в одномерном массиве (можно решить в $O(\log(n))$ время с использованием варианта двоичного поиска). Тесно связанным понятием является понятие «алгоритмы локальных вычислений» (LCA), где алгоритм получает большие входные данные и запрашивает локальную информацию о некоторых допустимых больших выходных данных. ^[10]

Линейное время

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

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

Квазилинейное время

Говорят, что алгоритм работает за квазилинейное время (также называемое лог-линейным временем ), если $T(n)=O(n\log ^{k}n)$ для некоторой положительной константы $k$ ; ^[11] линейное время - это случай $k=1$ . ^[12] Используя мягкую нотацию O, эти алгоритмы имеют вид ${\tilde {O}}(n)$ . Алгоритмы с квазилинейным временем также $O(n^{1+\varepsilon })$ для каждой константы $\varepsilon >0$ и, таким образом, работает быстрее, чем любой алгоритм с полиномиальным временем, чья временная граница включает член $n^{c}$ для любого $c>1$ .

Алгоритмы, работающие за квазилинейное время, включают:

Сортировка слиянием на месте , $O(n\log ^{2}n)$
Быстрая сортировка , $O(n\log n)$ , в своей рандомизированной версии, имеет время работы, равное $O(n\log n)$ в ожидании наихудшего входного сигнала. Его нерандомизированная версия имеет $O(n\log n)$ время работы только при рассмотрении средней сложности случая.
пирамидальная сортировка , $O(n\log n)$ , сортировка слиянием , интросортия , сортировка двоичного дерева, гладкая сортировка , терпеливная сортировка и т. д. в худшем случае
Быстрое преобразование Фурье , $O(n\log n)$
массива Монге , Расчет $O(n\log n)$

Во многих случаях $O(n\log n)$ время работы — это просто результат выполнения $\Theta (\log n)$ операцию $n$ раз (обозначения см. в разделе Обозначение Big O § Семейство обозначений Бахмана – Ландау ). Например, сортировка двоичного дерева создает двоичное дерево путем вставки каждого элемента $массива размера n$ один за другим. Поскольку операция вставки в самобалансирующееся двоичное дерево поиска занимает $O(\log n)$ времени весь алгоритм занимает $O(n\log n)$ время.

Сортировки сравнения требуют как минимум $\Omega (n\log n)$ сравнения в худшем случае, потому что $\log(n!)=\Theta (n\log n)$ , по приближению Стирлинга . Они также часто возникают из рекуррентного соотношения ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ .

Субквадратичное время

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

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

Полиномиальное время

что алгоритм имеет полиномиальное время , если время его работы ограничено сверху полиномиальным Говорят , выражением размера входных данных для алгоритма, то есть T ( n ) = O ( n ^к) для некоторой положительной константы k . ^[1]^[13] Проблемы , для которых существует детерминированный алгоритм с полиномиальным временем, относятся к классу сложности P , который является центральным в области теории сложности вычислений . В тезисе Кобэма говорится, что полиномиальное время является синонимом понятий «управляемый», «выполнимый», «эффективный» или «быстрый». ^[14]

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

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

Эти две концепции актуальны только в том случае, если входные данные алгоритмов состоят из целых чисел.

Классы сложности

Концепция полиномиального времени приводит к нескольким классам сложности в теории сложности вычислений. Ниже приведены некоторые важные классы, определенные с использованием полиномиального времени.

P : Класс сложности задач решения , которые можно решить на детерминированной машине Тьюринга за полиномиальное время.
NP : Класс сложности задач решения, которые можно решить на недетерминированной машине Тьюринга за полиномиальное время.
ZPP : Класс сложности задач решения, которые можно решить с нулевой ошибкой на вероятностной машине Тьюринга за полиномиальное время.
RP : Класс сложности задач решения, которые можно решить с односторонней ошибкой на вероятностной машине Тьюринга за полиномиальное время.
BPP : класс сложности задач решения, которые можно решить с двусторонней ошибкой на вероятностной машине Тьюринга за полиномиальное время.
BQP : класс сложности задач решения, которые можно решить с двусторонней ошибкой на квантовой машине Тьюринга за полиномиальное время.

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

Суперполиномиальное время

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

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

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

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

Квазиполиномиальное время

Алгоритмы с квазиполиномиальным временем — это алгоритмы, время работы которых демонстрирует квазиполиномиальный рост — тип поведения, который может быть медленнее, чем полиномиальное время, но при этом значительно быстрее, чем экспоненциальное время . Наихудшее время работы алгоритма с квазиполиномиальным временем составляет $2^{O(\log ^{c}n)}$ для некоторых фиксированных $c>0$ . Когда $c=1$ это дает полиномиальное время, и для $c<1$ это дает сублинейное время.

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

Другие вычислительные задачи с решениями за квазиполиномиальное время, но без известного решения за полиномиальное время, включают задачу о посещенной клике , цель которой состоит в том, чтобы найти большую клику в объединении клики и случайного графа . Несмотря на квазиполиномиальную разрешимость, было высказано предположение, что проблема посаженной клики не имеет решения за полиномиальное время; Эта гипотеза о посеваемой клике использовалась в качестве предположения о вычислительной сложности для доказательства сложности ряда других задач в вычислительной теории игр , тестировании свойств и машинном обучении . ^[15]

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

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

Связь с NP-полными задачами

В теории сложности нерешенная проблема P и NP спрашивает, все ли проблемы в NP имеют алгоритмы с полиномиальным временем. Все самые известные алгоритмы для решения NP-полных задач, такие как 3SAT и т. д., требуют экспоненциального времени. Действительно, для многих естественных NP-полных задач предполагается, что они не имеют алгоритмов с субэкспоненциальным временем. Здесь под «субэкспоненциальным временем» понимается второе определение, представленное ниже. (С другой стороны, многие задачи с графами, естественным образом представленные матрицами смежности, разрешимы за субэкспоненциальное время просто потому, что размер входных данных равен квадрату числа вершин.) Эта гипотеза (для задачи k-SAT) имеет вид известная как гипотеза экспоненциального времени . ^[17] Поскольку предполагается, что NP-полные задачи не имеют алгоритмов с квазиполиномиальным временем, некоторые результаты о неаппроксимируемости в области аппроксимационных алгоритмов предполагают, что NP-полные задачи не имеют алгоритмов с квазиполиномиальным временем. Например, см. известные результаты о неаппроксимируемости для задачи покрытия множеств .

Субэкспоненциальное время

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

Первое определение

Говорят, что задача разрешима за субэкспоненциальное время, если ее можно решить за время выполнения, логарифмы которого становятся меньше любого заданного полинома. Точнее, проблема решается за субэкспоненциальное время, если для любого ε > 0 существует алгоритм, решающий задачу за время O (2 ^{н ^е}). Набор всех таких задач представляет собой класс сложности SUBEXP , который можно определить в терминах DTIME следующим образом. ^[6]^[19]^[20]^[21]

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

Это понятие субэкспоненты неоднородно с точки зрения ε в том смысле, что ε не является частью входных данных, и каждое ε может иметь свой собственный алгоритм решения проблемы.

Второе определение

Некоторые авторы определяют субэкспоненциальное время как время работы в $2^{o(n)}$ . ^[17]^[22]^[23] Это определение допускает большее время работы, чем первое определение субэкспоненциального времени. Примером такого субэкспоненциального алгоритма времени является самый известный классический алгоритм факторизации целых чисел, решето общего числового поля , которое работает за время около $2^{{\tilde {O}}(n^{1/3})}$ , где длина ввода равна $n$ . Другим примером была проблема изоморфизма графов , которую самый известный алгоритм с 1982 по 2016 год решал в $2^{O\left({\sqrt {n\log n}}\right)}$ . Однако на STOC 2016 был представлен алгоритм квазиполиномиального времени. ^[24]

Имеет значение, разрешено ли алгоритму быть субэкспоненциальным по размеру экземпляра, количеству вершин или количеству ребер. В параметризованной сложности эта разница становится явной при рассмотрении пар $(L,k)$ и задач решения параметры k . SUBEPT — это класс всех параметризованных задач, которые выполняются во времени субэкспоненциально по k и полиномиально по входному размеру n : ^[25]

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

Точнее, SUBEPT — это класс всех параметризованных задач. $(L,k)$ для которого существует вычислимая функция $f:\mathbb {N} \to \mathbb {N}$ с $f\in o(k)$ и алгоритм, который решает L за время $2^{f(k)}\cdot {\text{poly}}(n)$ .

Гипотеза экспоненциального времени

Гипотеза экспоненциального времени ( ETH ) заключается в том, что 3SAT , проблема выполнимости булевых формул в конъюнктивной нормальной форме с не более чем тремя литералами на предложение и с n переменными, не может быть решена за время 2. ^{на )}. Точнее, гипотеза состоит в том, что существует некоторая абсолютная константа $c > 0,$ такая что 3SAT не может быть решена за время 2. ^CN любой детерминированной машиной Тьюринга. Поскольку m обозначает количество предложений, ETH эквивалентен гипотезе о том, что k SAT не может быть решено за время 2. ^{о ( м )} для любого целого числа $k \geq 3$ . ^[26] Гипотеза экспоненциального времени подразумевает P ≠ NP .

Экспоненциальное время

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

{\text{EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\text{DTIME}}\left(2^{n^{c}}\right)

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

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

Факториальное время

Алгоритм называется факториальным по времени , если T(n) ограничен сверху факториальной функцией n! . Факториальное время является подмножеством экспоненциального времени (EXP), потому что $n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)$ для всех $\epsilon >0$ . Однако это не подмножество E.

Примером алгоритма, работающего за факторное время, является bogosort , заведомо неэффективный алгоритм сортировки, основанный на методе проб и ошибок . Bogosort сортирует список из n элементов, неоднократно перемешивая список, пока не будет обнаружено, что он отсортирован. В среднем при каждом проходе алгоритма bogosort проверяется один из n ! упорядочение n предметов. Если элементы различны, сортируется только один такой порядок. Богосорт разделяет наследие теоремы о бесконечных обезьянах .

Двойное экспоненциальное время

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

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

Хорошо известные алгоритмы двойной экспоненциальной времени включают в себя:

Процедуры принятия решений для арифметики Пресбургера
Вычисление базиса Грёбнера (в худшем случае ^[27])
Устранение кванторов в реальных закрытых полях занимает как минимум двойное экспоненциальное время. ^[28] и это можно сделать за это время. ^[29]

См. также

Ссылки

↑ Перейти обратно: Перейти обратно: ^а ^б Сипсер, Майкл (2006). Введение в теорию вычислений . Курс Technology Inc. ISBN 0-619-21764-2 .
^ Мельхорн, Курт ; Нахер, Стефан (1990). «Ограниченные упорядоченные словари во $времени O (log log N)$ и $O (n)$ пространстве ». Письма об обработке информации . 35 (4): 183–189. дои : 10.1016/0020-0190(90)90022-П .
^ Тао, Теренс (2010). «1.11 Тест на простоту АКС» . Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4 . МР 2780010 .
^ Ленстра, Х.В. младший ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. дои : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 . МР 3941463 . S2CID 127807021 .
^ Калуд, Кристиан С. и Джайн, Санджай и Хусаинов, Бахадыр и Ли, Вэй и Стефан, Фрэнк (2017). «Определение игр на четность за квазиполиномиальное время» . Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . Ассоциация вычислительной техники. стр. 252–263. дои : 10.1145/3055399.3055409 . hdl : 2292/31757 . ISBN 9781450345286 . S2CID 30338402 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
↑ Перейти обратно: Перейти обратно: ^а ^б Бабай, Ласло ; На данный момент, Лэнс ; Нисан, Н. ; Вигдерсон, Ави (1993). «BPP использует субэкспоненциальное моделирование времени, если у EXPTIME нет опубликованных доказательств». Вычислительная сложность . 3 (4). Берлин, Нью-Йорк: Springer-Verlag : 307–318. дои : 10.1007/BF01275486 . S2CID 14802332 .
^ Брэдфорд, Филипп Г.; Роулинз, Грегори Дж. Э.; Шеннон, Грегори Э. (1998). «Эффективное упорядочение матричной цепочки за полилогарифмическое время». SIAM Journal по вычислительной технике . 27 (2): 466–490. дои : 10.1137/S0097539794270698 . МР 1616556 .
^ Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое тестирование планарности за полилогарифмическое время». У Макарычева Константина; Макарычев Юрий; Тулсиани, Мадхур; Камат, Гаутама; Чужой, Юлия (ред.). Материалы 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22-26 июня 2020 г. Ассоциация вычислительной техники. стр. 167–180. arXiv : 1911.03449 . дои : 10.1145/3357713.3384249 . ISBN 978-1-4503-6979-4 .
^ Кумар, Рави; Рубинфельд, Ронитт (2003). «Алгоритмы сублинейного времени» (PDF) . Новости СИГАКТ . 34 (4): 57–67. дои : 10.1145/954092.954103 . S2CID 65359 .
^ Рубинфельд, Ронитт (2019). «Алгоритмы локальных вычислений». Материалы симпозиума ACM по принципам распределенных вычислений (PODC) 2019 года . п. 3. дои : 10.1145/3293611.3331587 . ISBN 978-1-4503-6217-7 .
^ Наик, Ашиш В.; Риган, Кеннет В.; Сивакумар, Д. (1995). «О теории сложности с квазилинейным временем» (PDF) . Теоретическая информатика . 148 (2): 325–349. дои : 10.1016/0304-3975(95)00031-Q . МР 1355592 .
^ Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Пирсон Образование. п. 186.
^ Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-53082-1 .
^ Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Учеб. Логика, методология и философия науки II . Северная Голландия.
^ Браверман, Марк ; Кун-Ко, Янг; Рубинштейн, Авиад; Вайнштейн, Омри (2017). «Трудность ETH для плотнейшего $k$ -подграфа с идеальной полнотой». Кляйн, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . Общество промышленной и прикладной математики. стр. 1326–1341. arXiv : 1504.08352 . дои : 10.1137/1.9781611974782.86 . ISBN 978-1-61197-478-2 . МР 3627815 .
^ Зоопарк сложности : Класс QP: Квазиполиномиальное время
↑ Перейти обратно: Перейти обратно: ^а ^б Импальяццо, Рассел ; Патури, Рамамохан (2001). «О сложности $k$ -SAT» (PDF) . Журнал компьютерных и системных наук . 62 (2): 367–375. дои : 10.1006/jcss.2000.1727 . МР 1820597 .
^ Ааронсон, Скотт (5 апреля 2009 г.). «Не совсем экспоненциальная дилемма» . Shtetl-Оптимизированный . Проверено 2 декабря 2009 г.
^ Зоопарк сложности : Класс SUBEXP: Детерминированное субэкспоненциальное время
^ Мозер, П. (2003). «Категории Бэра на классах малой сложности». В Анджее Лингасе; Бенгт Дж. Нильссон (ред.). Основы теории вычислений: 14-й международный симпозиум, FCT 2003, Мальмё, Швеция, 12–15 августа 2003 г., Труды . Конспекты лекций по информатике . Том. 2751. Берлин, Нью-Йорк: Springer-Verlag. стр. 333–342. дои : 10.1007/978-3-540-45077-1_31 . ISBN 978-3-540-40543-6 . ISSN 0302-9743 .
^ Милтерсен, П.Б. (2001). «Дерандомизация классов сложности». Справочник по рандомизированным вычислениям . Комбинаторная оптимизация. 9 . Академический паб Kluwer: 843. doi : 10.1007/978-1-4615-0013-1_19 (неактивен 18 марта 2024 г.). ISBN 978-1-4613-4886-3 . {{cite journal}}: CS1 maint: DOI неактивен по состоянию на март 2024 г. ( ссылка )
^ Куперберг, Грег (2005). «Квантовый алгоритм субэкспоненциального времени для задачи о скрытых диэдральных подгруппах». SIAM Journal по вычислительной технике . 35 (1). Филадельфия: 188. arXiv : quant-ph/0302112 . дои : 10.1137/s0097539703436345 . ISSN 1095-7111 . S2CID 15965140 .
^ Одед Регев (2004). «Алгоритм субэкспоненциального времени для решения задачи о скрытых подгруппах диэдра с полиномиальным пространством». arXiv : Quant-ph/0406151v1 .
^ Гроэ, Мартин; Нойен, Даниэль (2021). «Последние достижения в проблеме изоморфизма графов». В Домбровском, Конрад К.; Гадуло, Максимилиан; Георгиу, Николас; Джонсон, Мэтью; Мерциос, Джордж Б.; Паулусма, Даниэль (ред.). Обзоры по комбинаторике 2021 . Серия лекций Лондонского математического общества. Том. 470. Издательство Кембриджского университета. стр. 187–234. arXiv : 2011.01366 . ISBN 978-1-009-01888-3 . МР 4273431 .
^ Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности . Спрингер. п. 417. ИСБН 978-3-540-29952-3 .
^ Импальяццо, Р. ; Патури, Р.; Зейн, Ф. (2001). «Какие проблемы имеют сильно экспоненциальную сложность?» . Журнал компьютерных и системных наук . 63 (4): 512–530. дои : 10.1006/jcss.2001.1774 .
^ Майр, Эрнст В .; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов» . Достижения в математике . 46 (3): 305–329. дои : 10.1016/0001-8708(82)90048-2 . МР 0683204 .
^ Давенпорт, Джеймс Х .; Хайнц, Йоос (1988). «Реальное устранение кванторов происходит вдвойне экспоненциально» . Журнал символических вычислений . 5 (1–2): 29–35. дои : 10.1016/S0747-7171(88)80004-X . МР 0949111 .
^ Коллинз, Джордж Э. (1975). «Устранение кванторов для вещественных замкнутых полей путем цилиндрического алгебраического разложения». В Брэкедже, Х. (ред.). Теория автоматов и формальные языки: 2-я конференция GI, Кайзерслаутерн, 20–23 мая 1975 г. Конспекты лекций по информатике. Том. 33. Спрингер. стр. 134–183. дои : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6 . МР 0403962 .

[Sipser-1] Перейти обратно: Перейти обратно: ^а ^б Сипсер, Майкл (2006). Введение в теорию вычислений . Курс Technology Inc. ISBN 0-619-21764-2 .

[2] Мельхорн, Курт ; Нахер, Стефан (1990). «Ограниченные упорядоченные словари во $времени O (log log N)$ и $O (n)$ пространстве ». Письма об обработке информации . 35 (4): 183–189. дои : 10.1016/0020-0190(90)90022-П .

[tao-aks-3] Тао, Теренс (2010). «1.11 Тест на простоту АКС» . Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4 . МР 2780010 .

[4] Ленстра, Х.В. младший ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. дои : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 . МР 3941463 . S2CID 127807021 .

[5] Калуд, Кристиан С. и Джайн, Санджай и Хусаинов, Бахадыр и Ли, Вэй и Стефан, Фрэнк (2017). «Определение игр на четность за квазиполиномиальное время» . Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . Ассоциация вычислительной техники. стр. 252–263. дои : 10.1145/3055399.3055409 . hdl : 2292/31757 . ISBN 9781450345286 . S2CID 30338402 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[bpp-6] Перейти обратно: Перейти обратно: ^а ^б Бабай, Ласло ; На данный момент, Лэнс ; Нисан, Н. ; Вигдерсон, Ави (1993). «BPP использует субэкспоненциальное моделирование времени, если у EXPTIME нет опубликованных доказательств». Вычислительная сложность . 3 (4). Берлин, Нью-Йорк: Springer-Verlag : 307–318. дои : 10.1007/BF01275486 . S2CID 14802332 .

[7] Брэдфорд, Филипп Г.; Роулинз, Грегори Дж. Э.; Шеннон, Грегори Э. (1998). «Эффективное упорядочение матричной цепочки за полилогарифмическое время». SIAM Journal по вычислительной технике . 27 (2): 466–490. дои : 10.1137/S0097539794270698 . МР 1616556 .

[8] Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое тестирование планарности за полилогарифмическое время». У Макарычева Константина; Макарычев Юрий; Тулсиани, Мадхур; Камат, Гаутама; Чужой, Юлия (ред.). Материалы 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22-26 июня 2020 г. Ассоциация вычислительной техники. стр. 167–180. arXiv : 1911.03449 . дои : 10.1145/3357713.3384249 . ISBN 978-1-4503-6979-4 .

[9] Кумар, Рави; Рубинфельд, Ронитт (2003). «Алгоритмы сублинейного времени» (PDF) . Новости СИГАКТ . 34 (4): 57–67. дои : 10.1145/954092.954103 . S2CID 65359 .

[10] Рубинфельд, Ронитт (2019). «Алгоритмы локальных вычислений». Материалы симпозиума ACM по принципам распределенных вычислений (PODC) 2019 года . п. 3. дои : 10.1145/3293611.3331587 . ISBN 978-1-4503-6217-7 .

[11] Наик, Ашиш В.; Риган, Кеннет В.; Сивакумар, Д. (1995). «О теории сложности с квазилинейным временем» (PDF) . Теоретическая информатика . 148 (2): 325–349. дои : 10.1016/0304-3975(95)00031-Q . МР 1355592 .

[12] Седжвик, Роберт; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Пирсон Образование. п. 186.

[13] Пападимитриу, Христос Х. (1994). Вычислительная сложность . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-53082-1 .

[14] Кобэм, Алан (1965). «Внутренняя вычислительная сложность функций». Учеб. Логика, методология и философия науки II . Северная Голландия.

[15] Браверман, Марк ; Кун-Ко, Янг; Рубинштейн, Авиад; Вайнштейн, Омри (2017). «Трудность ETH для плотнейшего $k$ -подграфа с идеальной полнотой». Кляйн, Филип Н. (ред.). Материалы двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . Общество промышленной и прикладной математики. стр. 1326–1341. arXiv : 1504.08352 . дои : 10.1137/1.9781611974782.86 . ISBN 978-1-61197-478-2 . МР 3627815 .

[16] Зоопарк сложности : Класс QP: Квазиполиномиальное время

[ETH-17] Перейти обратно: Перейти обратно: ^а ^б Импальяццо, Рассел ; Патури, Рамамохан (2001). «О сложности $k$ -SAT» (PDF) . Журнал компьютерных и системных наук . 62 (2): 367–375. дои : 10.1006/jcss.2000.1727 . МР 1820597 .

[18] Ааронсон, Скотт (5 апреля 2009 г.). «Не совсем экспоненциальная дилемма» . Shtetl-Оптимизированный . Проверено 2 декабря 2009 г.

[19] Зоопарк сложности : Класс SUBEXP: Детерминированное субэкспоненциальное время

[20] Мозер, П. (2003). «Категории Бэра на классах малой сложности». В Анджее Лингасе; Бенгт Дж. Нильссон (ред.). Основы теории вычислений: 14-й международный симпозиум, FCT 2003, Мальмё, Швеция, 12–15 августа 2003 г., Труды . Конспекты лекций по информатике . Том. 2751. Берлин, Нью-Йорк: Springer-Verlag. стр. 333–342. дои : 10.1007/978-3-540-45077-1_31 . ISBN 978-3-540-40543-6 . ISSN 0302-9743 .

[21] Милтерсен, П.Б. (2001). «Дерандомизация классов сложности». Справочник по рандомизированным вычислениям . Комбинаторная оптимизация. 9 . Академический паб Kluwer: 843. doi : 10.1007/978-1-4615-0013-1_19 (неактивен 18 марта 2024 г.). ISBN 978-1-4613-4886-3 . {{cite journal}}: CS1 maint: DOI неактивен по состоянию на март 2024 г. ( ссылка )

[22] Куперберг, Грег (2005). «Квантовый алгоритм субэкспоненциального времени для задачи о скрытых диэдральных подгруппах». SIAM Journal по вычислительной технике . 35 (1). Филадельфия: 188. arXiv : quant-ph/0302112 . дои : 10.1137/s0097539703436345 . ISSN 1095-7111 . S2CID 15965140 .

[23] Одед Регев (2004). «Алгоритм субэкспоненциального времени для решения задачи о скрытых подгруппах диэдра с полиномиальным пространством». arXiv : Quant-ph/0406151v1 .

[24] Гроэ, Мартин; Нойен, Даниэль (2021). «Последние достижения в проблеме изоморфизма графов». В Домбровском, Конрад К.; Гадуло, Максимилиан; Георгиу, Николас; Джонсон, Мэтью; Мерциос, Джордж Б.; Паулусма, Даниэль (ред.). Обзоры по комбинаторике 2021 . Серия лекций Лондонского математического общества. Том. 470. Издательство Кембриджского университета. стр. 187–234. arXiv : 2011.01366 . ISBN 978-1-009-01888-3 . МР 4273431 .

[25] Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности . Спрингер. п. 417. ИСБН 978-3-540-29952-3 .

[26] Импальяццо, Р. ; Патури, Р.; Зейн, Ф. (2001). «Какие проблемы имеют сильно экспоненциальную сложность?» . Журнал компьютерных и системных наук . 63 (4): 512–530. дои : 10.1006/jcss.2001.1774 .

[27] Майр, Эрнст В .; Мейер, Альберт Р. (1982). «Сложность словесных задач для коммутативных полугрупп и полиномиальных идеалов» . Достижения в математике . 46 (3): 305–329. дои : 10.1016/0001-8708(82)90048-2 . МР 0683204 .

[28] Давенпорт, Джеймс Х .; Хайнц, Йоос (1988). «Реальное устранение кванторов происходит вдвойне экспоненциально» . Журнал символических вычислений . 5 (1–2): 29–35. дои : 10.1016/S0747-7171(88)80004-X . МР 0949111 .

[29] Коллинз, Джордж Э. (1975). «Устранение кванторов для вещественных замкнутых полей путем цилиндрического алгебраического разложения». В Брэкедже, Х. (ред.). Теория автоматов и формальные языки: 2-я конференция GI, Кайзерслаутерн, 20–23 мая 1975 г. Конспекты лекций по информатике. Том. 33. Спрингер. стр. 134–183. дои : 10.1007/3-540-07407-4_17 . ISBN 978-3-540-07407-6 . МР 0403962 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]