Сложность алгоритма

Сло́жность алгори́тма, числовая характеристика алгоритма, измеряющая либо сложность его описания, либо сложность вычисления с помощью этого алгоритма. Ниже рассматривается только сложность алгоритма вычисления, которая характеризует его эффективность в том или ином смысле. Сложность алгоритма, как правило, является функцией не только самого алгоритма, но и исходных данных (например, слов). Многие варианты сложности алгоритма являются монотонными функциями на множестве натуральных чисел (длин слов). Самым распространённым вариантом сложности алгоритма является сложность алгоритма в наихудшем случае, определяемая как максимальная сложность алгоритма по всем исходным данным, длина которых не превосходит некоторого натурального числа ${\displaystyle n}$, рассматриваемого как параметр. Обычно ставится вопрос об асимптотическом ${\displaystyle (}$при ${\displaystyle n\rightarrow \infty )}$ поведении сложности алгоритма в наихудшем случае.

Наиболее важным примером сложности алгоритма является время его работы, измеряемое числом элементарных шагов (операций), совершаемых алгоритмом при переходе от исходных данных к результату работы. Алгоритмы, время работы которых в наихудшем случае ограничено некоторым полиномом от длины исходных данных, называются полиномиальными. Расширенный тезис Чёрча утверждает, что все разумные, в широком интуитивном смысле, уточнения понятия алгоритма приводят к одному и тому же классу полиномиальных алгоритмов и что этот класс совпадает с классом алгоритмов, фактически реализуемых на практике. Обе части этого тезиса не являются настолько бесспорными, как изначальный тезис Чёрча (см. в статье Алгоритмическая проблема).

Теория сложности алгоритма как самостоятельная научная дисциплина начала развиваться в 1960-х гг. одновременно с развитием компьютерных технологий. В это время, в частности, сформировались основные концепции теории сложности алгоритма. В начале 1970-х гг. была построена теория переборных задач и сформулирована центральная в этой области проблема перебора (см. Теория алгоритмов). Было также введено важнейшее понятие сводимости, связанное с возможностью из эффективных алгоритмов, построенных для решения одной задачи, получать эффективные алгоритмы для решения других задач.

Современная теория сложности алгоритма имеет дело как с вычислительными алгоритмами в прямом смысле этого слова, так и с более общими процессами алгоритмического характера. Помимо времени работы, часто изучаются и другие виды сложности алгоритма, например, объём необходимой памяти или количество переданной информации.

Проблематика теории сложности алгоритма включает как построение и анализ эффективных алгоритмов, так и доказательство того, что в ряде случаев такие алгоритмы невозможны (т. н. проблема нижних оценок). В то время как в первом направлении достигнут существенный прогресс, проблема нижних оценок оказалась крайне сложной.