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

АЛГОРИТМА СЛОЖНОСТЬ, числовая характеристика алгоритма, измеряющая либо сложность его описания, либо сложность вычисления с помощью этого алгоритма. Ниже рассматривается только алгоритма сложность вычисления, которая характеризует его эффективность в том или ином смысле. Алгоритма сложность, как правило, является функцией не только самого алгоритма, но и исходных данных (например, слов).

Многие варианты алгоритмов сложности являются монотонными функциями на множестве натуральных чисел (длин слов). Самым распространённым вариантом алгоритма сложности является алгоритма сложность в наихудшем случае, определяемая как максимальная сложность алгоритма по всем исходным данным, длина которых не превосходит некоторого натурального числа n, рассматриваемого как параметр. Обычно ставится вопрос об асимптотическом (при n →∞) поведении алгоритма сложности в наихудшем случае.

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

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

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

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

Лит.: Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., 1982; Papadimitriou С. Н. Computational complexity. Roading (Mass.), 1994.