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

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

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

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

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

{\text{EXPTIME}}=\bigcup _{k=1}^{\infty }TIME\left(2^{n^{k}}\right)

,

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

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

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

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

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

См. также

Примечания

John von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem // (англ.) / H. W. Kuhn , A. W. Tucker , Eds. — Princeton, NJ: Princeton Univ. Press , 1953. — P. 5-12. — 404 p.