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