Экспоненциальная сложность: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Zemant (обсуждение | вклад) Метки: с мобильного устройства из мобильной версии через расширенный мобильный режим |
|||
| (не показано 5 промежуточных версий 4 участников) | |||
| Строка 1: | Строка 1: | ||
'''Экспоненциальная сложность''' — в теории сложности [[алгоритм]]ов, [[Вычислительная сложность|сложность]] задачи, ограниченная [[Экспонента|экспонентой]] от [[полином]]а от размерности задачи, то есть ограничена функцией <math>\exp(P(n))</math>, где <math>P</math> — некоторый многочлен, а <math>n</math> — размер задачи. В этом случае говорят, что сложность задачи растёт '''экспоненциально'''. Часто под сложностью подразумевают время выполнения алгоритма. В этом случае говорят, что алгоритм принадлежит к классу [[EXPTIME]]. Однако сложность может относиться и к памяти или другим ресурсам, нужным для работы алгоритма. |
'''Экспоненциальная сложность''' — в теории сложности [[алгоритм]]ов, [[Вычислительная сложность|сложность]] задачи, ограниченная [[Экспонента|экспонентой]] от [[полином]]а от размерности задачи, то есть ограничена функцией <math>\exp(P(n))</math>, где <math>P</math> — некоторый многочлен, а <math>n</math> — размер задачи. В этом случае говорят, что сложность задачи растёт '''экспоненциально'''. Часто под сложностью подразумевают время выполнения алгоритма. В этом случае говорят, что алгоритм принадлежит к классу [[EXPTIME]]. Однако сложность может относиться и к памяти или другим ресурсам, нужным для работы алгоритма. |
||
Различие между полиномиальными и экспоненциальными алгоритмами восходит к [[Нейман, Джон фон|фон Нейману]].<ref>{{ |
Различие между полиномиальными и экспоненциальными алгоритмами восходит к [[Нейман, Джон фон|фон Нейману]].<ref>{{книга |часть= A certain zero-sum two-person game equivalent to the optimal assignment problem |ссылка= https://books.google.com.ua/books?id=ulrGpTmQ8wQC&pg=PA1&dq=A+certain+zero-sum+two-person+game+equivalent+to+the+optimal&hl=uk&sa=X&ved=2ahUKEwjQ5Z-kyujqAhWQrIsKHfjpBR4Q6AEwAHoECAIQAg#v=onepage&q=A%20certain%20zero-sum%20two-person%20game%20equivalent%20to%20the%20optimal&f=false |заглавие=Contributions to the Theory of Games |ответственный= [[Кун, Гарольд|H. W. Kuhn]], [[Таккер, Альберт Уильям|A. W. Tucker]], Eds |издательство=[[Princeton University Press|Princeton Univ. Press]] |год = 1953 |место=Princeton, NJ |язык=en |страниц= 404 |страницы= 5-12|автор=John von Neumann}}</ref> |
||
== Временная сложность == |
== Временная сложность == |
||
| Строка 9: | Строка 9: | ||
Задачи с экспоненциальной сложностью времени работы образуют [[класс EXPTIME]], в формально определяемый как: |
Задачи с экспоненциальной сложностью времени работы образуют [[класс EXPTIME]], в формально определяемый как: |
||
: <math>\text{EXPTIME} = \bigcup_{k=1}^{\infty} TIME\left(2^{n^k}\right)</math>, |
: <math>\text{EXPTIME} = \bigcup_{k=1}^{\infty} TIME\left(2^{n^k}\right)</math>, |
||
где <math>TIME(f(n))</math> — множество задач, которые могут быть решены алгоритмами, время работы которых ограничено сверху функцией <math>f(t)</math>. |
где <math>TIME(f(n))</math> — [[многозадачность|множество задач]], которые могут быть решены алгоритмами, время работы которых ограничено сверху функцией <math>f(t)</math> . |
||
== Сравнение с полиномиальной сложностью == |
== Сравнение с полиномиальной сложностью == |
||
Текущая версия от 23:41, 14 июля 2023
Экспоненциальная сложность — в теории сложности алгоритмов, сложность задачи, ограниченная экспонентой от полинома от размерности задачи, то есть ограничена функцией , где — некоторый многочлен, а — размер задачи. В этом случае говорят, что сложность задачи растёт экспоненциально. Часто под сложностью подразумевают время выполнения алгоритма. В этом случае говорят, что алгоритм принадлежит к классу EXPTIME. Однако сложность может относиться и к памяти или другим ресурсам, нужным для работы алгоритма.
Различие между полиномиальными и экспоненциальными алгоритмами восходит к фон Нейману.[1]
Временная сложность
[править | править код]Задачи с экспоненциальной сложностью времени работы образуют класс EXPTIME, в формально определяемый как:
- ,
где — множество задач, которые могут быть решены алгоритмами, время работы которых ограничено сверху функцией .
Сравнение с полиномиальной сложностью
[править | править код]Принято считать, что алгоритмы с полиномиальной сложностью являются «быстрыми», в то время как алгоритмы, сложность которых больше полиномиальной, — «медленными». С этой точки зрения алгоритмы с экспоненциальной сложностью являются медленными. Однако, это предположение не совсем точное. Дело в том, что время работы алгоритма зависит от значения n (размерности задачи) и сопутствующих констант скрытых в O-нотации. В некоторых случаях для малых значений n полиномиальное время может превосходить экспоненциальное. Однако, для больши́х значений n время работы алгоритма с экспоненциальной сложностью существенно больше.
Субэкспоненциальная сложность
[править | править код]Существуют алгоритмы, которые работают более, чем за полиномиальное время («сверх-полиномиальное»), но менее, чем за экспоненциальное время («суб-экспоненциальное»). Примером такой задачи является разложение целого числа на простые множители (факторизация). Такие алгоритмы также относятся к «медленным».
См. также
[править | править код]Примечания
[править | править код]- ↑ John von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem // Contributions to the Theory of Games (англ.) / H. W. Kuhn, A. W. Tucker, Eds. — Princeton, NJ: Princeton Univ. Press, 1953. — P. 5-12. — 404 p.