В информатике , то временная сложность является вычислительной сложностью , которая описывает количество машинного времени, которое требуется для запуска алгоритма . Временная сложность обычно оценивается путем подсчета количества элементарных операций, выполняемых алгоритмом, предполагая, что каждая элементарная операция требует фиксированного количества времени для выполнения. Таким образом, количество затраченного времени и количество элементарных операций, выполняемых алгоритмом, различаются не более чем на постоянный коэффициент .
Поскольку время работы алгоритма может различаться для разных входов одного и того же размера, обычно рассматривают наихудшую временную сложность , которая представляет собой максимальное количество времени, требуемое для входов заданного размера. Менее распространенной и обычно указываемой явно является средняя сложность , которая представляет собой среднее время, затрачиваемое на вводы заданного размера (это имеет смысл, поскольку существует только конечное число возможных вводов заданного размера). В обоих случаях временная сложность обычно выражается как функция размера входных данных. [1] : 226 Так как эта функция , как правило , трудно вычислить точно, и время работы для небольших входов, как правило , не опосредованное, один обычно фокусируется на поведении сложности , когда входного размер увеличивается-то есть, асимптотическое поведение из сложность. Следовательно, временная сложность обычно выражается с использованием нотации большой буквы O , обычно, , , и т. д., где n - размер входных данных в битах, необходимых для представления входных данных.
Алгоритмические сложности классифицируются в соответствии с типом функции, обозначенной большой нотацией O. Например, алгоритм с временной сложностьюэто линейный алгоритм времени и алгоритм с временной сложностью для некоторой постоянной представляет собой алгоритм с полиномиальным временем .
Таблица общих временных сложностей
В следующей таблице приведены некоторые классы часто встречающихся временных сложностей. В таблице poly ( x ) = x O (1) , т. Е. Многочлен от x .
Имя | Класс сложности | Время работы ( T ( n )) | Примеры времени работы | Примеры алгоритмов |
---|---|---|---|---|
постоянное время | О (1) | 10 | Нахождение медианного значения в отсортированном массиве чисел Вычисляя (−1) n | |
обратное время Аккермана | О ( а ( п )) | Амортизированное время на операцию с использованием непересекающегося набора | ||
повторное логарифмическое время | O ( журнал * n ) | Распределенная раскраска циклов | ||
логарифмический | O (журнал журнал n ) | Амортизированное время на операцию с использованием очереди с ограниченным приоритетом [2] | ||
логарифмическое время | DLOGTIME | O (журнал n ) | журнал n , журнал ( n 2 ) | Бинарный поиск |
полилогарифмическое время | поли (журнал п ) | (журнал n ) 2 | ||
дробная мощность | O ( n c ), где 0 < c <1 | п 1/2 , п 2/3 | Поиск в kd-дереве | |
линейное время | О ( п ) | п , 2 п + 5 | Поиск наименьшего или наибольшего элемента в несортированном массиве , алгоритм Кадане , линейный поиск | |
"n log-star n" раз | O ( п журнал * п ) | Зайдель «s многоугольник триангуляции алгоритм. | ||
линейное время | O ( п войти п ) | п войти п , журнал п ! | Самая быстрая сортировка сравнения ; Быстрое преобразование Фурье . | |
квазилинейное время | п поли (журнал п ) | |||
квадратичное время | О ( п 2 ) | п 2 | Пузырьковая сортировка ; Вставка сортировки ; Прямая свертка | |
кубическое время | О ( п 3 ) | п 3 | Наивное умножение двух матриц размера n × n . Расчет частичной корреляции . | |
полиномиальное время | п | 2 O (журнал п ) = поли ( п ) | п 2 + п , п 10 | Алгоритм Кармаркара для линейного программирования ; Тест простоты AKS [3] [4] |
квазиполиномиальное время | QP | 2 поли (log n ) | n журнал журнал n , n журнал n | Самый известный O (log 2 n ) - алгоритм аппроксимации для задачи ориентированного дерева Штейнера . |
субэкспоненциальное время (первое определение) | СУБЭКСП | O (2 n ε ) для всех ε > 0 | Содержит BPP, если EXPTIME (см. Ниже) не равен MA . [5] | |
субэкспоненциальное время (второе определение) | 2 о ( п ) | 2 п 1/3 | Лучший известный алгоритм для целочисленной факторизации ; ранее лучший алгоритм для изоморфизма графов | |
экспоненциальное время (с линейным показателем) | E | 2 О ( п ) | 1.1 п , 10 п | Решение задачи коммивояжера с помощью динамического программирования |
экспоненциальное время | EXPTIME | 2 поли ( n ) | 2 п , 2 п 2 | Решение умножения цепочки матриц с помощью перебора |
факториальное время | О ( п !) | п ! | Решение задачи коммивояжера с помощью поиска перебора | |
двойное экспоненциальное время | 2-ВРЕМЯ | 2 2 поли ( п ) | 2 2 п | Определение истинности данного утверждения в арифметике Пресбургера |
Постоянное время
Алгоритм называется постоянным временем (также обозначаемым как время O (1) ), если значение T ( n ) ограничено значением, которое не зависит от размера ввода. Например, доступ к любому отдельному элементу в массиве занимает постоянное время, поскольку для его обнаружения требуется выполнить только одну операцию . Аналогичным образом поиск минимального значения в массиве, отсортированном по возрастанию; это первый элемент. Однако поиск минимального значения в неупорядоченном массиве не является операцией с постоянным временем, поскольку для определения минимального значения необходимо сканирование каждого элемента в массиве. Следовательно, это операция с линейным временем, занимающая время O ( n ). Однако, если количество элементов известно заранее и не меняется, можно сказать, что такой алгоритм работает в постоянное время.
Несмотря на название «постоянное время», время выполнения не обязательно должно быть независимым от размера проблемы, но верхняя граница времени выполнения должна быть ограничена независимо от размера проблемы. Например, задача «обменять значения a и b, если необходимо, так, чтобы a ≤ b » называется постоянным временем, даже если время может зависеть от того, верно ли уже, что a ≤ b . Однако существует некоторая постоянная t такая, что необходимое время всегда не превышает t .
Вот несколько примеров фрагментов кода, которые выполняются в постоянное время:
int index = 5;int item = список [индекс];если (условие истинно) то выполнить некоторую операцию, которая выполняется в постоянное времяеще выполнить некоторую другую операцию, которая выполняется в постоянное времядля i = от 1 до 100 для j = от 1 до 200 выполнить некоторую операцию, которая выполняется в постоянное время
Если 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 в словаре, может выполняться за логарифмическое время: рассмотрим, гдеобозначает функцию пола . Если, тогда все готово. В противном случае, если, продолжите поиск таким же образом в левой половине словаря, в противном случае продолжите аналогично с правой половиной словаря. Этот алгоритм похож на метод, который часто используется для поиска статьи в бумажном словаре.
Полилогарифмическое время
Говорят, что алгоритм работает за полилогарифмическое время, если его время T ( n ) равно O ((log n ) k ) для некоторой константы k . Другой способ записать это - O (log k n ) .
Например, упорядочение цепи , матрица может быть решено в полилогарифмическим время на параллельной машине с произвольным доступом , [6] , и график может быть определен , чтобы быть плоскими в полном динамическом пути в O (вход 3 н ) по времени на вставку / операция удаления . [7]
Сублинейное время
Говорят, что алгоритм работает в сублинейном времени (часто называемом сублинейным временем ), если T ( n ) = o ( n ) . В частности, это включает алгоритмы с временной сложностью, определенной выше.
Типичные алгоритмы, которые являются точными и все же выполняются в сублинейном времени, используют параллельную обработку (как вычисление определителя матрицы NC 1 ) или, альтернативно, имеют гарантированные предположения о входной структуре (как это делают двоичный поиск с логарифмическим временем и многие алгоритмы обслуживания дерева) . Однако формальные языки, такие как набор всех строк, которые имеют 1-бит в позиции, указанной первыми log ( n ) битами строки, могут зависеть от каждого бита ввода и при этом быть вычисляемыми за сублинейное время.
Конкретный термин « алгоритм сублинейного времени» обычно зарезервирован для алгоритмов, которые отличаются от приведенных выше в том, что они запускаются на классических моделях последовательных машин и не допускают предварительных предположений на входе. [8] Однако они могут быть рандомизированы и действительно должны быть рандомизированы для всех, кроме самых тривиальных задач.
Поскольку такой алгоритм должен давать ответ без чтения всего ввода, его особенности сильно зависят от доступа, разрешенного к вводу. Обычно для входа, представленного в виде двоичной строки b 1 ,…, b k, предполагается, что алгоритм может за время O (1) запросить и получить значение b i для любого i .
Алгоритмы сублинейного времени обычно рандомизированы и предоставляют только приблизительные решения. Фактически, можно легко доказать, что свойство двоичной строки, имеющей только нули (и ни одной), не разрешимо с помощью (не приближенного) алгоритма сублинейного времени. Алгоритмы сублинейного времени возникают естественным образом при исследовании тестирования свойств .
Линейное время
Говорят, что алгоритм принимает линейное время или время O ( n ) , если его временная сложность равна O ( n ) . Неформально это означает, что время работы увеличивается максимально линейно с размером входа. Точнее, это означает, что существует такая константа c , что время работы не превышает cn для каждого ввода размера n . Например, процедура, которая складывает все элементы списка, требует времени, пропорционального длине списка, если время добавления постоянное или, по крайней мере, ограничено константой.
Линейное время - это наилучшая временная сложность в ситуациях, когда алгоритм должен последовательно считывать все входные данные. Поэтому много исследований было вложено в открытие алгоритмов, показывающих линейное время или, по крайней мере, почти линейное время. Это исследование включает как программные, так и аппаратные методы. Для этого существует несколько аппаратных технологий, использующих параллелизм . Примером является память с адресацией по содержимому . Эта концепция линейного времени используется в алгоритмах строка соответствия , такие как алгоритм Бойера-Мура и алгоритм Укконена .
Квазилинейное время
Говорят, что алгоритм работает в квазилинейном времени (также называемом логлинейным временем ), если T ( n ) = O ( n log k n ) для некоторой положительной константы k ; [9] линейное время - это случай k = 1 . [10] Используя мягкую нотацию O, эти алгоритмы имеют вид Õ ( n ). Квазилинейные временные алгоритмы также O ( n 1+ ε ) для любой константы ε > 0 и, таким образом, работают быстрее, чем любой алгоритм с полиномиальным временем, чья временная граница включает член n c для любого c > 1 .
Алгоритмы, работающие в квазилинейном времени, включают:
- Сортировка слиянием на месте , O ( n log 2 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 время , если Т ( п ) = О ( п 2 ) .
Например, простые алгоритмы сортировки, основанные на сравнении, являются квадратичными (например, сортировка вставкой ), но можно найти более продвинутые алгоритмы, которые являются субквадратичными (например, сортировка по оболочке ). Никакие универсальные сортировки не выполняются за линейное время, но переход от квадратичного к субквадратичному имеет большое практическое значение.
Полиномиальное время
Алгоритм называется быть полиномиальное время , если его продолжительность будет ограничена сверху с помощью полиномиального выражения в размере входных данных для алгоритма, то есть, Т ( п ) = О ( п к ) для некоторой положительной константы к . [1] [11] Задачи, для которых существует детерминированный алгоритм с полиномиальным временем, относятся к классу сложности P , который является центральным в области теории сложности вычислений . В тезисе Кобэма говорится, что полиномиальное время является синонимом слов «послушный», «выполнимый», «эффективный» или «быстрый». [12]
Некоторые примеры алгоритмов с полиномиальным временем:
- Выбор рода алгоритм сортировки по п целых чисел выполняетоперации для некоторой константы А . Таким образом, он бежит во времени и является алгоритмом с полиномиальным временем.
- Все основные арифметические операции (сложение, вычитание, умножение, деление и сравнение) могут быть выполнены за полиномиальное время.
- Максимальные паросочетания в графах можно найти в полиномиальное время.
Сильно и слабо полиномиальное время
В некоторых контекстах, особенно в оптимизации , различают алгоритмы с сильно полиномиальным и слабо полиномиальным временем . Эти две концепции актуальны только в том случае, если входные данные алгоритмов состоят из целых чисел.
В арифметической модели вычислений определено сильно полиномиальное время. В этой модели вычислений основные арифметические операции (сложение, вычитание, умножение, деление и сравнение) выполняются за единичный временной шаг, независимо от размеров операндов. Алгоритм выполняется за строго полиномиальное время, если: [13]
- количество операций в арифметической модели вычислений ограничено полиномом от количества целых чисел во входном экземпляре; а также
- пространство, используемое алгоритмом, ограничено полиномом от размера входных данных.
Любой алгоритм с этими двумя свойствами можно преобразовать в алгоритм с полиномиальным временем, заменив арифметические операции подходящими алгоритмами для выполнения арифметических операций на машине Тьюринга . Если второе из вышеперечисленных требований не выполняется, то это уже неверно. Учитывая целое число(который занимает пространство, пропорциональное n в модели машины Тьюринга), можно вычислитьс n умножениями с использованием повторного возведения в квадрат . Однако пространство, используемое для представления пропорционально , и, следовательно, экспоненциально, а не полиномиально в пространстве, используемом для представления входных данных. Следовательно, невозможно выполнить это вычисление за полиномиальное время на машине Тьюринга, но можно вычислить его с помощью полиномиально большого числа арифметических операций.
И наоборот, есть алгоритмы, которые выполняются за несколько шагов машины Тьюринга, ограниченных полиномом от длины двоично-кодированных входных данных, но не выполняют количество арифметических операций, ограниченных полиномом от количества входных чисел. Алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел является одним из примеров. Учитывая два целых числа а также , алгоритм выполняет арифметические операции над числами с не более чем биты. В то же время количество арифметических операций не может быть ограничено количеством целых чисел на входе (которое в данном случае является константой, на входе всегда только два целых числа). Из-за последнего наблюдения алгоритм не работает за строго полиномиальное время. Его реальное время работы зависит от величины а также и не только от количества целых чисел во входных данных.
Алгоритм, работающий за полиномиальное время, но не являющийся сильно полиномиальным, называется слабо полиномиальным . [14] Хорошо известным примером проблемы, для которой известен алгоритм со слабо полиномиальным временем, но не известно, что он допускает алгоритм с сильно полиномиальным временем, является линейное программирование . Слабополиномиальное время не следует путать с псевдополиномиальным временем .
Классы сложности
Концепция полиномиального времени приводит к нескольким классам сложности в теории вычислительной сложности. Некоторые важные классы, определенные с использованием полиномиального времени, следующие.
п | Сложность класс из задач принятия решений , которые могут быть решены на детерминированной машине Тьюринга за полиномиальное время |
НП | Класс сложности задач принятия решений, которые могут быть решены на недетерминированной машине Тьюринга за полиномиальное время |
ЗПП | Класс сложности задач принятия решений, которые могут быть решены с нулевой ошибкой на вероятностной машине Тьюринга за полиномиальное время |
RP | Класс сложности задач решения, которые могут быть решены с односторонней ошибкой на вероятностной машине Тьюринга за полиномиальное время. |
BPP | Класс сложности задач принятия решений, которые могут быть решены с двусторонней ошибкой на вероятностной машине Тьюринга за полиномиальное время |
BQP | Класс сложности задач принятия решений, которые могут быть решены с двусторонней ошибкой на квантовой машине Тьюринга за полиномиальное время |
P - это наименьший класс временной сложности на детерминированной машине, устойчивый к изменениям модели машины. (Например, переход от однопленочной машины Тьюринга к многоленточной машине может привести к квадратичному ускорению, но любой алгоритм, работающий за полиномиальное время в одной модели, также делает это и в другой.) Любая данная абстрактная машина будет иметь класс сложности, соответствующий задачам, которые могут быть решены за полиномиальное время на этой машине.
Суперполиномиальное время
Говорят, что алгоритм берет суперполиномиальное время, если T ( n ) не ограничено сверху никаким многочленом. Используя краткую омега-нотацию , это время ω ( n c ) для всех констант c , где n - входной параметр, обычно количество битов во входных данных.
Например, алгоритм, который выполняется для 2 n шагов на входе размера n, требует суперполиномиального времени (точнее, экспоненциального времени).
Алгоритм, использующий экспоненциальные ресурсы, явно суперполиномиален, но некоторые алгоритмы лишь очень слабо суперполиномиальны. Например, тест простоты Адлемана – Померанса – Рамли выполняется в течение n O (log log n ) времени на n- битных входах; это растет быстрее, чем любой многочлен при достаточно большом n , но входной размер должен стать непрактично большим, прежде чем он не сможет преобладать многочленом с малой степенью.
Алгоритм , который требует суперполиномиальным время лежит за пределами класса сложности P . Тезис Кобхэма утверждает, что эти алгоритмы непрактичны, и во многих случаях это так. Поскольку проблема P и NP не решена , неизвестно, требуют ли NP-полные задачи суперполиномиального времени.
Квазиполиномиальное время
Алгоритмы квазиполиномиального времени - это алгоритмы, которые работают дольше, чем полиномиальное время, но не настолько долго, чтобы быть экспоненциальным временем. Наихудшее время работы квазиполиномиального алгоритма времени составляет для некоторых фиксированных . Для мы получаем алгоритм полиномиального времени, для мы получаем алгоритм сублинейного времени.
Квазиполиномиальные временные алгоритмы обычно возникают при редукции от NP-сложной проблемы к другой проблеме. Например, можно взять экземпляр сложной задачи NP, скажем, 3SAT , и преобразовать его в экземпляр другой проблемы B, но размер экземпляра станет равным. В таком случае эта редукция не доказывает, что задача B NP-трудна; это сокращение только показывает, что не существует алгоритма полиномиального времени для B, если нет алгоритма квазиполиномиального времени для 3SAT (и, следовательно, всего NP ). Точно так же есть некоторые проблемы, для которых мы знаем алгоритмы квазиполиномиального времени, но не известны алгоритмы полиномиального времени. Такие проблемы возникают в приближенных алгоритмах; известным примером является задача направленного дерева Штейнера , для которой существует алгоритм аппроксимации квазиполиномиального времени, обеспечивающий коэффициент аппроксимации( n - количество вершин), но показать существование такого алгоритма с полиномиальным временем - открытая проблема.
Другие вычислительные задачи с квазиполиномиальными временными решениями, но без известного полиномиального временного решения, включают задачу с установленной кликой, в которой цель состоит в том, чтобы найти большую клику в объединении клики и случайного графа . Хотя квазиполиномиально разрешима, было высказано предположение, что проблема насаждаемой клики не имеет решения за полиномиальное время; Эта гипотеза насаждаемой клики использовалась в качестве предположения о вычислительной сложности, чтобы доказать сложность ряда других проблем в теории вычислительных игр , тестировании свойств и машинном обучении . [15]
Класс сложности QP состоит из всех задач, которые имеют алгоритмы с квазиполиномиальным временем. Его можно определить в терминах DTIME следующим образом. [16]
Отношение к NP-полным задачам
В теории сложности нерешенная проблема P и NP спрашивает, все ли задачи в NP имеют алгоритмы с полиномиальным временем. Все самые известные алгоритмы для NP-полных задач, такие как 3SAT и т. Д., Требуют экспоненциального времени. В самом деле, для многих естественных NP-полных задач предполагается, что они не имеют алгоритмов с субэкспоненциальным временем. Здесь «субэкспоненциальное время» означает второе определение, представленное ниже. (С другой стороны, многие задачи о графах, представленные естественным образом матрицами смежности, разрешимы за субэкспоненциальное время просто потому, что размер входных данных равен квадрату числа вершин.) Эта гипотеза (для задачи k-SAT) известна как гипотеза экспоненциального времени . [17] Поскольку предполагается, что NP-полные задачи не имеют квазиполиномиальных временных алгоритмов, некоторые результаты о неприближаемости в области аппроксимационных алгоритмов предполагают, что NP-полные задачи не имеют квазиполиномиальных временных алгоритмов. Например, просмотрите известные результаты о несовместимости задачи о множественном покрытии .
Субэкспоненциальное время
The term sub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon,[18] and we list the two most widely used ones below.
First definition
A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every ε > 0 there exists an algorithm which solves the problem in time O(2nε). The set of all such problems is the complexity class SUBEXP which can be defined in terms of DTIME as follows.[5][19][20][21]
This notion of sub-exponential is non-uniform in terms of ε in the sense that ε is not part of the input and each ε may have its own algorithm for the problem.
Second definition
Some authors define sub-exponential time as running times in 2o(n).[17][22][23] This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the general number field sieve, which runs in time about , where the length of the input is n. Another example was the graph isomorphism problem, which the best known algorithm from 1982 to 2016 solved in . However, at STOC 2016 a quasi-polynomial time algorithm was presented.[24]
It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In parameterized complexity, this difference is made explicit by considering pairs of decision problems and parameters k. SUBEPT is the class of all parameterized problems that run in time sub-exponential in k and polynomial in the input size n:[25]
More precisely, SUBEPT is the class of all parameterized problems for which there is a computable function with and an algorithm that decides L in time .
Exponential time hypothesis
The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with n variables, cannot be solved in time 2o(n). More precisely, the hypothesis is that there is some absolute constant c > 0 such that 3SAT cannot be decided in time 2cn by any deterministic Turing machine. With m denoting the number of clauses, ETH is equivalent to the hypothesis that kSAT cannot be solved in time 2o(m) for any integer k ≥ 3.[26] The exponential time hypothesis implies P ≠ NP.
Экспоненциальное время
An algorithm is said to be exponential time, if T(n) is upper bounded by 2poly(n), where poly(n) is some polynomial in n. More formally, an algorithm is exponential time if T(n) is bounded by O(2nk) for some constant k. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as EXP.
Sometimes, exponential time is used to refer to algorithms that have T(n) = 2O(n), where the exponent is at most a linear function of n. This gives rise to the complexity class E.
Факториальное время
An example of an algorithm that runs in factorial time is bogosort, a notoriously inefficient sorting algorithm based on trial and error. Bogosort sorts a list of n items by repeatedly shuffling the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the n! orderings of the n items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the infinite monkey theorem.
Двойное экспоненциальное время
An algorithm is said to be double exponential time if T(n) is upper bounded by 22poly(n), where poly(n) is some polynomial in n. Such algorithms belong to the complexity class 2-EXPTIME.
Well-known double exponential time algorithms include:
- Decision procedures for Presburger arithmetic
- Computing a Gröbner basis (in the worst case[27])
- Quantifier elimination on real closed fields takes at least double exponential time,[28] and can be done in this time.[29]
Смотрите также
- Block swap algorithms
- L-notation
- Space complexity
Рекомендации
- ^ a b Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
- ^ Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in O(log log N) time and O(n) space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.
- ^ Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
- ^ Lenstra, Jr., H.W.; Pomerance, Carl (11 December 2016). "Primality testing with Gaussian periods" (PDF). Cite journal requires
|journal=
(help) - ^ a b Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307–318. doi:10.1007/BF01275486.
- ^ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "Efficient Matrix Chain Ordering in Polylog Time". SIAM Journal on Computing. Philadelphia: Society for Industrial and Applied Mathematics. 27 (2): 466–490. doi:10.1137/S0097539794270698. ISSN 1095-7111.
- ^ Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic Planarity Testing in Polylogarithmic Time". STOC 2020: 167–180. arXiv:1911.03449. doi:10.1145/3357713.3384249.
- ^ Kumar, Ravi; Rubinfeld, Ronitt (2003). "Sublinear time algorithms" (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103.
- ^ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "On Quasilinear Time Complexity Theory" (PDF). Theoretical Computer Science. 148 (2): 325–349. doi:10.1016/0304-3975(95)00031-q. Retrieved 23 February 2015.
- ^ Sedgewick, R. and Wayne K (2011). Algorithms, 4th Ed. p. 186. Pearson Education, Inc.
- ^ Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
- ^ Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
- ^ Grötschel, Martin; László Lovász; Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.
- ^ Schrijver, Alexander (2003). "Preliminaries on algorithms and Complexity". Combinatorial Optimization: Polyhedra and Efficiency. 1. Springer. ISBN 3-540-44389-4.
- ^ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest-k-subgraph with perfect completeness, arXiv:1504.08352, Bibcode:2015arXiv150408352B.
- ^ Complexity Zoo: Class QP: Quasipolynomial-Time
- ^ a b Impagliazzo, R.; Paturi, R. (2001). "On the complexity of k-SAT". Journal of Computer and System Sciences. Elsevier. 62 (2): 367–375. doi:10.1006/jcss.2000.1727. ISSN 1090-2724.
- ^ Aaronson, Scott (5 April 2009). "A not-quite-exponential dilemma". Shtetl-Optimized. Retrieved 2 December 2009.
- ^ Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time
- ^ Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings. Lecture Notes in Computer Science. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. doi:10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.
- ^ Miltersen, P.B. (2001). "Derandomizing Complexity Classes". Handbook of Randomized Computing. Combinatorial Optimization. Kluwer Academic Pub. 9: 843. doi:10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.
- ^ Kuperberg, Greg (2005). "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem". SIAM Journal on Computing. Philadelphia. 35 (1): 188. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345. ISSN 1095-7111.
- ^ Oded Regev (2004). "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space". arXiv:quant-ph/0406151v1.
- ^ Grohe, Martin; Neuen, Daniel (2021). "Recent Advances on the Graph Isomorphism Problem". arXiv:2011.01366. Cite journal requires
|journal=
(help) - ^ Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. p. 417. ISBN 978-3-540-29952-3.
- ^ Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "Which problems have strongly exponential complexity?". Journal of Computer and System Sciences. 63 (4): 512–530. doi:10.1006/jcss.2001.1774.
- ^ Mayr, E. & Mayer, A.: The Complexity of the Word Problem for Commutative Semi-groups and Polynomial Ideals. Adv. Math. 46(1982) pp. 305–329
- ^ J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential. J. Symbolic Comp. 5(1988) pp. 29–35.
- ^ G.E. Collins: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture Notes in Computer Science 33) pp. 134–183