Введение. Исследование сложности алгоритма помогает понять степень его практической приемлемости

Исследование сложности алгоритма помогает понять степень его практической приемлемости. Сравнительный анализ сложности нес­кольких алгоритмов решения одной и той же задачи позволяет делать обоснованный выбор лучшего из них. Например, если для решения задачи предлагается новый алгоритм, то необходимы доводы, гово­рящие о его преимуществах в сравнении с известными ранее алго­ритмами, и анализ сложности может предоставить такие доводы.

Слово «сложность» в этом контексте является математическим термином, а не общим обозначением препятствия к выполнению за­мысла. С понятием сложности связываются затраты времени или па­мяти, соответствующие худшему случаю, либо затраты в среднем; при этом, чтобы обсуждать худший или «средний» случай, нужно, прежде всего, договориться, как определяется размер входа (размер входных данных) алгоритма и в чем измеряются затраты при работе алгоритма над фиксированным входом.

Часто размер входа определяют как общее число символов в пред­ставлении входа, но возможны и другие пути. В задачах сортировки и поиска размер входа — это, как правило, количество элементов n входного массива, в задачах на графах —число вершин | V | или чис­ло ребер | E | входного графа G = (V, E), но, с другой стороны, | V | и | E | могут рассматриваться и совместно как два параметра раз­мера входа. В арифметических задачах размером входа может быть, например, максимум абсолютных величин входных целых чисел, или количество цифр в двоичной записи этого максимума, или же, как уже говорилось, суммарное количество двоичных цифр всех входных чисел и т.д.—выбор делается в зависимости от характера задачи.

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

Введение

как альтернатива, лишь наиболее дорогих операций (например, муль­типликативных—умножений и делений); более тщательный анализ требует рассмотрения количества битовых операций. Если алгоритм является рандомизированным (содержит обращения к генератору слу­чайных чисел с известным распределением), то затраты, вообще го­воря, не определяются однозначно входом алгоритма, но зависят от полученных случайных чисел. Можно рассматривать усредненные за­траты для каждого конкретного входа; такие затраты уже будут функ­цией входа.

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

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

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

См., например, статью «Алгоритма сложность» в [40].

Введение

алгоритма такого, сложность которого растет с увеличением размера входа не слишком быстро, например, остается ограниченной неко­торым полиномом, вид которого не оговаривается (такой алгоритм принято называть полиномиальным).

При исследовании существования алгоритма решения задачи, имеющего «не очень высокую» сложность, важную роль играет сво­димость какой-то задачи к другой—из возможности быстро решить некоторую задачу может следовать такая же возможность для ряда других, и наоборот, невозможность быстрого решения какой-то од­ной задачи может автоматически повлечь такую же невозможность для ряда других задач.

Сложности многих алгоритмов трудно или вообще нельзя пред­ставить в простом «замкнутом» виде; помимо этого, точное значе­ние сложности алгоритма для каждого конкретного значения разме­ра входа часто не представляет особого интереса, актуальным же яв­ляется исследование роста сложности при возрастании размера вхо­да (особый интерес к исходным данным большого размера оправдан тем, что на них «захлебываются» тривиальные алгоритмы). Поэтому в теории сложности широко используется асимптотическое оценива­ние. Однако сравнение сложностей различных алгоритмов на основе асимптотических оценок этих сложностей возможно не для всех ти­пов таких оценок.

Этот круг вопросов, наряду с рассмотрением общих достаточно элементарных подходов и методов, которые могут оказаться полез­ными при сложностном анализе алгоритмов, составляет содержание предлагаемого курса теории сложности алгоритмов.

Дата добавления: 2014-01-11