Вычислительная сложность

Описание	Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Область знаний	Информатика
Авторы
Поясняющее видео
Близкие понятия
Среды и средства для освоения понятия	Scratch, Snap!, Python

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжёра длина входа почти пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (наилучшего маршрута в задаче коммивояжёра).

Примеры

• «почистить ковёр пылесосом» требует время, линейно зависящее от его площади ([math]\displaystyle{ \Theta(A) }[/math]), то есть на ковёр, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз объём работы увеличивается строго пропорционально в сто тысяч раз, и т. п.
• «найти имя в телефонной книге» требует всего лишь времени, логарифмически зависящего от количества записей ([math]\displaystyle{ O(\log_2(n)) }[/math]), так как, открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге объёмом в 1000 страниц любое имя находится не больше, чем за [math]\displaystyle{ \log_2 1000 \approx 10 }[/math] раз (открываний книги). При увеличении объёма страниц до ста тысяч проблема все ещё решается за [math]\displaystyle{ \log_2 100000 \approx 17 }[/math] заходов. (См. Двоичный поиск.)