Вычислительная сложность: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Нет описания правки |
Ping08 (обсуждение | вклад) м откат правок 46.242.60.14 (обс.) к версии InternetArchiveBot Метка: откат |
||
Строка 1:
'''Вычисли́тельная сло́жность''' — понятие в [[информатика|информатике]] и [[теория алгоритмов|теории алгоритмов]], обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется '''теорией сложности вычислений'''. Объём работы обычно измеряется [[абстракция|абстрактными]] понятиями времени и пространства, называемыми [[
В частности, теория сложности вычислений определяет [[NP-полная задача|NP-полные задачи]], которые [[недетерминированная машина Тьюринга]] может решить за [[класс P|полиномиальное время]], тогда как для [[Детерминированная машина Тьюринга|детерминированной машины Тьюринга]] [[Равенство классов P и NP|полиномиальный алгоритм неизвестен]]. Обычно это сложные задачи оптимизации, например, [[задача коммивояжёра]].
|