Некоторые сложностные классы при первой встрече с ними вызывали у меня сложность с пониманием, что они значат. С P или NP все вполне интуитивно, а вот субэкспоненциальное или квазиполиномиальное время могут ставить в тупик. Итак, шпаргалка от меня.
Внутри P
Константное время
\[O(1)\]Здесь все очевидно: сложение двух чисел, помещающихся в регистр, проверка четности числа и так далее.
Итерированное-логарифмическое
\[O(\log^{*}(n))\]Определение итерированного логарифма см. математический анализ.
Логарифмическое время = DLOGTIME
\[O(\log{n})\]Напоминание: \(DTIME(f(n))\) - множество языков разрешимых детерминированной машиной Тьюринга за время \(f(n)\).
Тогда \(DLOGTIME = DTIME(\log{(n)})\)
Примерами будет \(\log{n^3}\), бинарный поиск.
Полилогарифмическое время
Языки разрешимые на ДМТ(детерминированная машина Тьюринга) за время \(poly(\log{n})\)
Пример, \(\log^2{n}\)
Сублинейное время
\[O(n^k) \ \textit{при} \ k \in (0, 1)\]Пример: \(n^{1/2}\)
Линейное время
\[O(n)\]Это тоже всем известная штука. Линейный поиск все дела.
Полиномиальное время = PTIME
\[poly(n) = 2^{O(\log{n})}\]Важнейший сложностной класс, проблемы которого считаются “быстро” решаемыми. Слово “быстро” здесь довольно коварное, так как скрываться за ним может как линейное или квадратичное время, так и что-то вроде \(O(n^{10000})\)
Вне P
Квазиполиномиальное время
\[QP = DTIME(2^{poly(\log{n})})\]Субэкспоненциальное время
\[SUBEXPTIME = O(2^{n^{\epsilon}}) \ \forall \epsilon > 0 = 2^{\bar o(n)}\]Экспоненциальное время
\[EXPTIME = 2^{poly(n)}\]Псевдополиномиальные алгоритмы
Некоторые задачи могут иметь алгоритм решения показывающий полиномиальный рост в зависимости от условий задачи.
Например, известная задача об укладке рюкзака. Решение этой задачи динамическим программированием имеет сложность \(O(n \cdot W)\), где \(W\) - максимальный вес.
Несмотря на то, что выглядит эта сложность как полином от n, под \(W\) вообще-то может скрываться экспоненциально большое по сравнению с n число из-за чего алгоритм перестанет быть полиномиальным. В таких случаях алгоритм называют псевдополиномиальным.
Определение
Алгоритм имеет псевдополиномиальную сложность, если он работает за время полиномиальное от числового значения входа(унарной записи числа), а не за полином от длины двоичной записи входа, что как раз называется полиномиальным временем.