Введение

Оценка времени выполнения алгоритма

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

| Логарифмическое время | DLOGTIME | | | Бинарный поиск |
|---|---|---|---|---|
| Полилогарифмическое время | | | | |
| Дробная степень | | где | | Поиск по диапазону в kd-дереве |
| Линейное время | | | n | Поиск наименьшего или наибольшего элемента в несортированном массиве. Алгоритм Кадане. Линейный поиск |
| Время "n log*n" | | | | Алгоритм триангуляции полигона Сиделя |
| Линеари́тмическое время | | | | Наиболее быстрая возможная сортировка сравнением. Быстрое преобразование Фурье |
| Квазилинейное время | | | | Вычисление многочлена в нескольких точках |
| Квадратичное время | | | | Сортировка пузырьком, сортировка вставками, прямое свёрточное преобразование |
| Кубическое время | | | | Наивное умножение двух матриц. Вычисление частичной корреляции |
| Полиномиальное время | P | | | Алгоритм Кармаркара для линейного программирования. Тест простоты AKS |
| Квазиполиномиальное время | QP | | | Наилучший известный алгоритм аппроксимации для задачи о направленном дереве Штейнера, наилучший решатель игры четности, наилучший алгоритм изоморфизма графов |
| Субэкспоненциальное время (первое определение) | SUBEXP | для всех | | Содержит BPP, если EXPTIME (см. ниже) не равно MA, и граф можно определить как планарный динамически за время на операцию вставки/удаления. |

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

Алгоритм называется алгоритмом с линейным временем, или временем O(n), если его временная сложность равна O(n). Неформально это означает, что время выполнения увеличивается не более чем линейно с ростом размера входных данных. Более точно, это означает, что существует константа c, такая что время выполнения составляет не более c*n для любого входного размера n. Например, процедура, суммирующая все элементы списка, требует времени, пропорционального длине списка, если время сложения является константой или, по крайней мере, ограничено константой. Линейное время – это наилучшая возможная временная сложность в ситуациях, когда алгоритму необходимо последовательно прочитать все входные данные. Поэтому значительные усилия были направлены на разработку алгоритмов, демонстрирующих линейное время или, по крайней мере, почти линейное время. Эти исследования включают как программные, так и аппаратные методы. Существует несколько аппаратных технологий, использующих параллелизм для достижения этого. Примером является ассоциативная память (память с адресным доступом по содержимому). Эта концепция линейного времени используется в алгоритмах поиска подстроки, таких как алгоритм поиска строк Бойера-Мура и алгоритм Укконена.

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

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

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

Алгоритм определяется как работающий за суперполиномиальное время, если T(n) не ограничена сверху никакой полиномиальной функцией. Используя нотацию малого омега, это время ω(nc) для всех констант c, где n – входной параметр, обычно количество бит во входных данных. Например, алгоритм, выполняющийся за 2n шагов на входе размера n, требует суперполиномиального времени (в частности, экспоненциального времени). Алгоритм, использующий экспоненциальные ресурсы, очевидно является суперполиномиальным, но некоторые алгоритмы лишь очень слабо суперполиномиальны. Например, тест простоты Адлемана — Померанца — Румели выполняется за время nO(log log n) на n-битных входных данных; это растет быстрее, чем любой полином при достаточно большом n, но размер входных данных должен стать непрактично большим, прежде чем он не сможет быть превзойден полиномом малой степени. Алгоритм, требующий суперполиномиального времени, находится за пределами класса сложности P. Тезис Кобэма утверждает, что такие алгоритмы непрактичны, и во многих случаях это действительно так. Поскольку проблема P против NP остается нерешенной, неизвестно, требуют ли NP-полные задачи суперполиномиального времени.

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

Алгоритмы квазиполиномиального времени — это алгоритмы, время работы которых демонстрирует квазиполиномиальный рост, тип поведения, который может быть медленнее полиномиального времени, но при этом значительно быстрее экспоненциального времени. Наихудшее время работы квазиполиномиального алгоритма составляет для некоторого фиксированного . Когда , это даёт полиномиальное время, а когда — сублинейное время. Существуют задачи, для которых известны квазиполиномиальные алгоритмы, но полиномиальный алгоритм неизвестен. Такие задачи возникают в алгоритмах приближения; известным примером является задача о направленном дереве Штейнера, для которой существует квазиполиномиальный алгоритм приближения, достигающий коэффициента приближения (где n — число вершин), но доказательство существования такого полиномиального алгоритма остаётся открытой проблемой. Другие вычислительные задачи с квазиполиномиальными решениями, но без известных полиномиальных решений, включают задачу о посаженной клике, в которой необходимо найти большую клику в объединении клики и случайного графа. Хотя задача о посаженной клике квазиполиномиально разрешима, предполагается, что она не имеет полиномиального решения; эта гипотеза о посаженной клике используется как предположение о вычислительной сложности для доказательства трудности нескольких других задач в вычислительной теории игр, тестировании свойств и машинном обучении. Класс сложности QP состоит из всех задач, для которых существуют квазиполиномиальные алгоритмы. Его можно определить в терминах DTIME следующим образом.

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

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

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

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

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

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

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

Некоторые авторы определяют субэкспоненциальное время как время выполнения в . Это определение допускает большее время выполнения, чем первое определение субэкспоненциального времени. Примером такого субэкспоненциального алгоритма является наиболее известный классический алгоритм для факторизации целых чисел – общее решето числового поля, которое работает за время примерно , где n – длина входных данных. Другим примером является задача об изоморфизме графов, которую лучший известный алгоритм с 1982 по 2016 год решал за . Однако на STOC 2016 был представлен алгоритм квазиполиномиального времени. Важно, разрешено ли алгоритму быть субэкспоненциальным относительно размера экземпляра, числа вершин или числа ребер. В параметризованной сложности это различие явно выражается при рассмотрении пар (L, k) – задач принятия решений и параметров k. SUBEPT – это класс всех параметризованных задач, которые выполняются за время субэкспоненциальное по k и полиномиальное по размеру входных данных n:

Более точно, SUBEPT – это класс всех параметризованных задач, для которых существует вычислимая функция f с условием и алгоритм, решающий L за время .

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

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

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

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

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

Алгоритм считается факториальным по времени, если T(n) ограничена сверху факториальной функцией n!. Факториальное время является подмножеством экспоненциального времени (EXP), поскольку для всех. Однако, оно не является подмножеством E.

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