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

Экспоненциальная сложность или экспоненциальное время — в теории сложности алгоритмов, время решения задачи, ограниченное экспонентой от размерности задачи. Другими словами, если размерность задачи возрастает линейно, время её решения возрастает экспоненциально.

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

Определение

Основная статья: Класс EXPTIME

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

$\text{EXPTIME} = \bigcup_{k=1}^{\infty} O\left(2^{n^k}\right)$

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

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

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

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

См. также

• Класс EXPTIME
• O-нотация
• Постоянное время
• Линейное время
• NP-полная задача

Примечания

1. ↑ John von Neumann A certain zero-sunn two-person game equivalent to the optimal assignment problem // Contributions to the Theory of Games. — Princeton Univ. Press.