Что такое алгоритм и его сложность

Под алгоритмом, если говорить неформально, можно понимать четко описанную последовательность действий, приводящую к определенному результату.

Понятие алгоритма очень долго оставалось интуитивным понятием. Только в 30‑е годы XX века в работах выдающихся математиков Д. Гильберта, А. Черча, С. Клини, Э. Поста и А. Тьюринга были предложены формальные определения алгоритма на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Тем самым формировалась теория алгоритмов – новое направление в математике, которое стало впоследствии теоретической основой развития вычислительной техники. В настоящее время теория алгоритмов бурно развивается, многие ее понятия проясняются и уточняются (доказуемость, разрешимость, эффективность и др.).

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

Очень важным понятием в математике (интуитивно ясным, но не очень просто формализуемым) является сложность алгоритма. Приведем простой пример. Пусть требуется угадать задуманное число, про которое известно, что оно натуральное и не превосходит 1000. Разрешается задавать вопросы, на которые можно ответить «да» или «нет». Одним из способов (алгоритмов) угадывания может быть такой: последовательно перебираются все числа от 1 до 1000 до тех пор, пока нужное число не будет найдено. В худшем случае для этого потребуется 999 вопросов. Однако можно предложить и другой алгоритм, позволяющий угадать число за 10 вопросов: сначала выясняется, больше ли угаданное число 500 или нет, если да, то больше 750 или нет и т.д. С каждым шагом число возможных кандидатов уменьшается в два раза. Здесь сложностью алгоритма можно считать число вопросов. Тогда первый алгоритм в 100 раз «сложнее» второго.

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

В математической теории сложности вычислений рассматриваются алгоритмы решения не конкретных задач, а так называемых массовых задач. Массовую задачу удобно представлять себе в виде бесконечной серии индивидуальных задач. Индивидуальная задача характеризуется некоторым размером, т.е. объемом входных данных, требуемых для описания этой задачи. Если размер индивидуальной задачи – некоторое натуральное число n, тогда сложность алгоритма решения массовой задачи становится функцией от n. Приведем два примера.

Рассмотрим алгоритм простого перебора всех двоичных ключей длины n. Ясно, что таких ключей – 2 ⁿ , и поэтому в данном алгоритме 2 ⁿ шагов, т.е. его сложность равна 2 ⁿ . Это – простейший пример экспоненциального алгоритма (его сложность выражается через n экспонентой). Большинство экспоненциальных алгоритмов – это просто варианты полного перебора.

Рассмотрим теперь алгоритм умножения столбиком двух n ‑значных чисел. Он состоит из n ² умножений однозначных чисел, т.е. его сложность, измеренная количеством таких умножений, равна n ². Это – простейший пример полиномиального алгоритма (его сложность выражается через n полиномом).

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

В математике есть много задач, для решения которых пока не удалось построить полиномиальный алгоритм. К ним относится, например, задача коммивояжера: есть n городов, соединенных сетью дорог, и для каждой дороги указана стоимость проезда по ней; требуется указать такой маршрут, проходящий через все города, чтобы стоимость проезда по этому маршруту была минимальной.

Подумайте сами:

1. Можете ли вы предложить алгоритм умножения двух n ‑значных чисел, требующий меньшего числа умножений однозначных чисел, чем при умножении столбиком?