Вычислительная сложность: различия между версиями

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