Экспоненциальное время

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

Математически говоря, существует k > 1, такое что m(n) = Θ(kⁿ), и существует c, такое что m(n) = O(cⁿ).

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

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

Многие люди часто ошибочно называют квадратичное время экспоненциальным. Квадратичное время — это частный случай полиномиального, где высшая степень полинома равна 2, например, n². В случае с экспоненциальным временем, переменная, напротив, помещается в степень, например, 2ⁿ. Задачи, имеющие квадратичную или полиномиальную сложность достаточно «медлительны», но обычно всё ещё считаются решаемыми (хотя квадратично-сложные задачи часто работают слишком долго для интерактивных программ). Задачи, имеющие экспоненциальную сложность, считаются неразрешимыми, за исключением случаев малых n (возможно, за исключением квантовых вычислений).

См. также

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