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

 

== Определение ==

Принято считать, что алгоритмы с [[полиномиальная сложность|полиномиальной сложностью]] являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Однако, это предположение не совсем точное. Дело в том, что время работы алгоритма зависит от значения ''n'' (размерности задачи) и сопутствующих [[Константа|констант]] скрытых в [[O-нотация|O-нотации]]. В некоторых случаях для малых значений ''n'' полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений ''n'' время работы алгоритма с экспоненциальной сложностью существенно больше.

 

 

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