Экспоненциальная сложность: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Maxal (обсуждение | вклад) Нет описания правки |
Maxal (обсуждение | вклад) Нет описания правки |
||
Строка 1:
'''Экспоненциальная сложность''' или '''экспоненциальное время''' — в [[Теория сложности вычислений|теории сложности]] [[алгоритм]]ов, время решения задачи, ограниченное [[Экспонента|экспонентой]] от размерности задачи. Другими словами, если размерность задачи возрастает [[Линейная функция|линейно]], время её решения возрастает экспоненциально.
Различие между полиномиальными и экспоненциальными алгоритмами восходит к [[Нейман, Джон фон|фон Нейману]].<ref>{{cite book |author=John von Neumann |chapter=A certain zero-sunn two-person game equivalent to the optimal assignment problem |title=Contributions to the Theory of Games |editors=H. W. Kahn, A. W. Tucker, Eds. |publisher=Princeton Univ. Press |place=Princeton, NJ}}</ref>
== Определение ==
| |||