Экспоненциальная сложность: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Maxal (обсуждение | вклад) |
Maxal (обсуждение | вклад) спекуляции и тавтология удалены, стилевые правки, оформление |
||
| Строка 1: | Строка 1: | ||
'''Экспоненциальная сложность''' или '''экспоненциальное время''' — в [[Теория сложности вычислений|теории сложности]] [[алгоритм]]ов, время решения задачи, |
'''Экспоненциальная сложность''' или '''экспоненциальное время''' — в [[Теория сложности вычислений|теории сложности]] [[алгоритм]]ов, время решения задачи, ограниченое [[Экспонента|экспонентой]] от размерности задачи. Другими словами, если размерность задачи возрастает [[Линейная функция|линейно]], время её решения возрастает экспоненциально. |
||
== Определение == |
|||
[[Математика|Математически]] говоря, существует ''k'' > 1, такое что ''m(n)'' = ''[[O-нотация|Θ(k<sup>n</sup>)]]'', и существует ''c'', такое что ''m(n)'' = ''[[O-нотация|O(c<sup>n</sup>)]]''. |
|||
{{main|Класс EXPTIME}} |
|||
Алгоритмы с экспоненциальной сложностью образуют [[класс EXPTIME]], в терминах [[O-нотация|O-нотации]] формально определяемый как: |
|||
: <math>\text{EXPTIME} = \bigcup_{k=1}^{\infty} O\left(2^{n^k}\right)</math> |
|||
== Сравнение с полиномиальной сложностью == |
|||
Принято считать, что алгоритмы с '''[[полиномиальная сложность|полиномиальной сложностью]]''' являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Это полезное предположение, но не совсем точное. На самом деле действительное время работы алгоритма зависит от значения ''n'' (размерности задачи) и сопутствующих [[Константа|констант]] (см. [[O-нотация]]). Для заданного ''n'', в некоторых случаях полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений ''n'' время работы алгоритма с экспоненциальной сложностью существенно больше. |
Принято считать, что алгоритмы с '''[[полиномиальная сложность|полиномиальной сложностью]]''' являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Это полезное предположение, но не совсем точное. На самом деле действительное время работы алгоритма зависит от значения ''n'' (размерности задачи) и сопутствующих [[Константа|констант]] (см. [[O-нотация]]). Для заданного ''n'', в некоторых случаях полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений ''n'' время работы алгоритма с экспоненциальной сложностью существенно больше. |
||
== Суб-экспоненциальная сложность == |
|||
| ⚫ | |||
| ⚫ | Существует алгоритмы, которые работают более, чем за полиномиальное время ('''«сверх-полиномиальное»'''), но менее, чем за экспоненциальное время ('''«суб-экспоненциальное»'''). Примером такой задачи является разложение [[Целое число|целого числа]] на [[Простое число|простые]] [[Множитель|множители]] ([[факторизация]]). Такие алгоритмы также относятся к «медленным». |
||
Многие люди часто ошибочно называют '''квадратичное время''' экспоненциальным. Квадратичное время — это частный случай полиномиального, где высшая степень полинома равна 2, например, ''n''². В случае с экспоненциальным временем, [[переменная]], напротив, помещается в [[Возведение в степень|степень]], например, 2<sup>''n''</sup>. Задачи, имеющие квадратичную или полиномиальную сложность достаточно «медлительны», но обычно всё ещё считаются решаемыми (хотя квадратично-сложные задачи часто работают слишком долго для [[Интерактивность|интерактивных программ]]). Задачи, имеющие экспоненциальную сложность, считаются неразрешимыми, за исключением случаев малых ''n'' (возможно, за исключением [[Квантовые вычисления|квантовых вычислений]]). |
|||
== См. также == |
== См. также == |
||
Версия от 00:04, 29 октября 2009
Экспоненциальная сложность или экспоненциальное время — в теории сложности алгоритмов, время решения задачи, ограниченое экспонентой от размерности задачи. Другими словами, если размерность задачи возрастает линейно, время её решения возрастает экспоненциально.
Определение
Алгоритмы с экспоненциальной сложностью образуют класс EXPTIME, в терминах O-нотации формально определяемый как:
Сравнение с полиномиальной сложностью
Принято считать, что алгоритмы с полиномиальной сложностью являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Это полезное предположение, но не совсем точное. На самом деле действительное время работы алгоритма зависит от значения n (размерности задачи) и сопутствующих констант (см. O-нотация). Для заданного n, в некоторых случаях полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений n время работы алгоритма с экспоненциальной сложностью существенно больше.
Суб-экспоненциальная сложность
Существует алгоритмы, которые работают более, чем за полиномиальное время («сверх-полиномиальное»), но менее, чем за экспоненциальное время («суб-экспоненциальное»). Примером такой задачи является разложение целого числа на простые множители (факторизация). Такие алгоритмы также относятся к «медленным».