Сложность времени - Time complexity

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

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

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

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

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

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

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

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

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

Вот несколько примеров фрагментов кода, которые выполняются в постоянное время:

int index = 5;
int item = list[index];
if (condition true) then
    perform some operation that runs in constant time
else
    perform some other operation that runs in constant time
for i = 1 to 100
    for j = 1 to 200
        perform some operation that runs in constant time

Если T ( n ) равно O ( любое постоянное значение ), это эквивалентно и указано в стандартных обозначениях как T ( n ), равное O (1).

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

Говорят, что алгоритм принимает логарифмическое время, когда T ( n ) = O (log n ) . Поскольку log _a  n и log _b  n связаны постоянным множителем , и такой множитель не имеет отношения к классификации большого O, стандартное использование алгоритмов логарифмического времени - O (log n ) независимо от основания логарифма, появляющегося в выражение Т .

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

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

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

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

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

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

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

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

Типичные алгоритмы, которые являются точными и все же выполняются в сублинейном времени, используют параллельную обработку (как это делает расчет определителя матрицы NC ¹ ) или, альтернативно, имеют гарантированные предположения о входной структуре (как это делают двоичный поиск по логарифмическому времени и многие алгоритмы обслуживания дерева) . Однако формальные языки, такие как набор всех строк, которые имеют 1-бит в позиции, указанной первыми log ( n ) битами строки, могут зависеть от каждого бита ввода и при этом быть вычисляемыми за сублинейное время.

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

Поскольку такой алгоритм должен давать ответ без чтения всего ввода, его особенности сильно зависят от доступа, разрешенного к вводу. Обычно для входа, представленного в виде двоичной строки b ₁ ,…, b _k, предполагается, что алгоритм может за время O (1) запросить и получить значение b _i для любого i .

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

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

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

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

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

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

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

• Сортировка слиянием на месте , O ( n log ² n )
• Quicksort , O ( n log n ), в его рандомизированной версии, имеет время выполнения, равное O ( n log n ) в ожидании на входе наихудшего случая. Его нерандомизированная версия имеет время работы O ( n log n ) только с учетом средней сложности случая.
• Пирамидальная сортировка , O ( п журнал п ), сортировка слияние , introsort , бинарное дерево сортировки, Плавная сортировка , терпение сортировки и т.д. в худшем случае
• Быстрые преобразования Фурье , O ( n log n )
• Расчет массива Монжа , O ( n log n )

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

Сортировка сравнений требует как минимум Ω ( n log n ) сравнений в худшем случае, потому что log ( n !) = Θ ( n log n ) по приближению Стирлинга . Они также часто возникают из рекуррентного соотношения T ( n ) = 2 T ( n / 2) + O ( n ) .

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

Алгоритм называется subquadratic время , если Т ( п ) = О ( п ² ) .

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

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

Алгоритм называется быть полиномиальное время , если его продолжительность будет ограничена сверху с помощью полиномиального выражения в размере входных данных для алгоритма, то есть, Т ( п ) = О ( п ^к ) для некоторой положительной константы к . Задачи, для которых существует детерминированный алгоритм с полиномиальным временем, относятся к классу сложности P , который является центральным в области теории сложности вычислений . В тезисе Кобэма говорится, что полиномиальное время является синонимом слов «послушный», «выполнимый», «эффективный» или «быстрый».

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

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

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

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

В арифметической модели вычислений определено сильно полиномиальное время. В этой модели вычислений основные арифметические операции (сложение, вычитание, умножение, деление и сравнение) выполняются за единичный временной шаг, независимо от размеров операндов. Алгоритм выполняется за строго полиномиальное время, если:

1. количество операций в арифметической модели вычислений ограничено полиномом от количества целых чисел во входном экземпляре; а также
2. пространство, используемое алгоритмом, ограничено полиномом от размера входных данных.

Любой алгоритм с этими двумя свойствами можно преобразовать в алгоритм с полиномиальным временем, заменив арифметические операции подходящими алгоритмами для выполнения арифметических операций на машине Тьюринга . Если второе из вышеперечисленных требований не выполняется, то это уже неверно. Учитывая целое число (которое занимает пространство, пропорциональное n в модели машины Тьюринга), можно вычислить с n умножениями, используя повторное возведение в квадрат . Однако пространство, используемое для представления , пропорционально и, следовательно, экспоненциально, а не полиномиально в пространстве, используемом для представления входных данных. Следовательно, невозможно выполнить это вычисление за полиномиальное время на машине Тьюринга, но можно вычислить его полиномиально с помощью многих арифметических операций. ${\ displaystyle 2 ^ {n}}$${\ displaystyle 2 ^ {2 ^ {n}}}$${\ displaystyle 2 ^ {2 ^ {n}}}$${\ displaystyle 2 ^ {n}}$

И наоборот, есть алгоритмы, которые выполняются на нескольких шагах машины Тьюринга, ограниченных полиномом от длины двоично-закодированного ввода, но не выполняют ряда арифметических операций, ограниченных полиномом от числа входных чисел. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Учитывая два целых числа и , алгоритм выполняет арифметические операции с числами с не более чем битами. В то же время количество арифметических операций не может быть ограничено количеством целых чисел на входе (которое в данном случае является константой, на входе всегда только два целых числа). Из-за последнего наблюдения алгоритм не работает за строго полиномиальное время. Его реальное время работы зависит от величин и не только от числа целых чисел на входе. ${\ displaystyle a}$${\ displaystyle b}$${\ Displaystyle О (\ журнал а + \ журнал б)}$${\ Displaystyle О (\ журнал а + \ журнал б)}$${\ displaystyle a}$${\ displaystyle b}$

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

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

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

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

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

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

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

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

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

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

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

Квазиполиномиальные временные алгоритмы обычно возникают при редукции от NP-сложной проблемы к другой проблеме. Например, можно взять экземпляр сложной задачи NP, скажем, 3SAT , и преобразовать его в экземпляр другой проблемы B, но размер экземпляра станет равным . В этом случае эта редукция не доказывает, что задача B NP-трудна; это сокращение только показывает, что не существует алгоритма полиномиального времени для B, если нет алгоритма квазиполиномиального времени для 3SAT (и, следовательно, всего NP ). Точно так же есть некоторые проблемы, для которых мы знаем алгоритмы квазиполиномиального времени, но не известны алгоритмы полиномиального времени. Такие проблемы возникают в приближенных алгоритмах; Известным примером является задача направленного дерева Штейнера , для которой существует квазиполиномиальный алгоритм аппроксимации по времени, обеспечивающий коэффициент аппроксимации ( n - число вершин), но демонстрация существования такого алгоритма с полиномиальным временем является открытой проблемой. ${\ Displaystyle 2 ^ {О (\ журнал ^ {с} п)}}$${\ Displaystyle О (\ журнал ^ {3} п)}$

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

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

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

Отношение к NP-полным задачам

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle {\ mbox {2-EXPTIME}} = \ bigcup _ {c \ in \ mathbb {N}} {\ mbox {DTIME}} \ left (2 ^ {2 ^ {n ^ {c}}} \ Правильно)}$

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

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

Смотрите также

• L-обозначение
• Космическая сложность

использованная литература