Экспоненциальная сложность: различия между версиями

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

 

 

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