- Экспоненциальная сложность
-
Экспоненциальная сложность или экспоненциальное время — в теории сложности алгоритмов, время решения задачи, ограниченное экспонентой от размерности задачи. Другими словами, если размерность задачи возрастает линейно, время её решения возрастает экспоненциально.
Различие между полиномиальными и экспоненциальными алгоритмами восходит к фон Нейману.[1]
Содержание
Определение
Алгоритмы с экспоненциальной сложностью образуют класс EXPTIME, в терминах O-нотации формально определяемый как:
Сравнение с полиномиальной сложностью
Принято считать, что алгоритмы с полиномиальной сложностью являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Однако, это предположение не совсем точное. Дело в том, что время работы алгоритма зависит от значения n (размерности задачи) и сопутствующих констант скрытых в O-нотации. В некоторых случаях для малых значений n полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений n время работы алгоритма с экспоненциальной сложностью существенно больше.
Субэкспоненциальная сложность
Существует алгоритмы, которые работают более, чем за полиномиальное время («сверх-полиномиальное»), но менее, чем за экспоненциальное время («суб-экспоненциальное»). Примером такой задачи является разложение целого числа на простые множители (факторизация). Такие алгоритмы также относятся к «медленным».
См. также
- Класс EXPTIME
- O-нотация
- Постоянное время
- Линейное время
- NP-полная задача
Примечания
- ↑ 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.
Категория:- Теория сложности вычислений
Wikimedia Foundation. 2010.