Экспоненциальная сложность

Экспоненциальная сложность — в теории сложности алгоритмов, сложность задачи, ограниченная экспонентой от полинома от размерности задачи, то есть ограничена функцией exp ⁡ ( P ( n ) ) {displaystyle exp(P(n))} , где P {displaystyle P} — некоторый многочлен, а n {displaystyle n} — размер задачи. В этом случае говорят, что сложность задачи растёт экспоненциально. Часто под сложностью подразумевают время выполнения алгоритма. В этом случае говорят, что алгоритм принадлежит к классу EXPTIME. Однако сложность может относиться и к памяти или другим ресурсам, нужным для работы алгоритма.

Различие между полиномиальными и экспоненциальными алгоритмами восходит к фон Нейману.

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

Задачи с экспоненциальной сложностью времени работы образуют класс EXPTIME, в формально определяемый как:

EXPTIME = ⋃ k = 1 ∞ T I M E ( 2 n k ) {displaystyle { ext{EXPTIME}}=igcup _{k=1}^{infty }TIMEleft(2^{n^{k}} ight)} ,

где T I M E ( f ( n ) ) {displaystyle TIME(f(n))} — множество задач, которые могут быть решены алгоритмами, время работы которых ограничено сверху функцией f ( t ) {displaystyle f(t)} .

Сравнение с полиномиальной сложностью

Принято считать, что алгоритмы с полиномиальной сложностью являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Однако, это предположение не совсем точное. Дело в том, что время работы алгоритма зависит от значения n (размерности задачи) и сопутствующих констант скрытых в O-нотации. В некоторых случаях для малых значений n полиномиальное время может превосходить экспоненциальное. Однако, для больших значений n время работы алгоритма с экспоненциальной сложностью существенно больше.

Субэкспоненциальная сложность

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