Понятие сложности алгоритма

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

Какой же алгоритм лучше подходит для решения конкретной задачи? По каким критериям его следует выбирать из множества возможных?

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

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

Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении.
Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма.

Обратите внимание, в определении сложности алгоритма речь идёт именно о вычислительном процессе, а не о самом алгоритме. Алгоритм состоит из команд. Команда — это отдельная инструкция в описании алгоритма. Шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. В циклических алгоритмах за счёт повторного выполнения одних и тех же команд число шагов при выполнении алгоритма может быть значительно больше числа команд в алгоритме.

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

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

Для решения задачи могут быть разработаны алгоритмы, имеющие разную сложность. Лучшим среди них считается алгоритм, имеющий наименьшую сложность.

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

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

Рассмотрим метод быстрого вычисления натуральной степени п вещественного числа х, описанный в Древней Индии ещё до нашей эры.

1. Запишем n в двоичной системе счисления.

2. Заменим в этой записи каждую единицу парой букв КХ, а каждый ноль — буквой К.

3. Вычеркнем крайнюю левую пару КХ.

4. Полученная строка, читаемая слева направо, даёт правило быстрого вычисления хn, если букву К рассматривать как операцию возведения результата в квадрат, а букву X — как операцию умножения результата на х. Вначале результат равен х.

Воспользуемся этим алгоритмом для того, чтобы возвести х в степень n = 100.

1. 100 = 1100100₂.
2. Строим последовательность: КХКХКККХКК.
3. Вычёркиваем крайнюю левую пару КХ: КХКККХКК.
4. Вычисляем искомое значение:
К: возвести х в квадрат (х²);
X: умножить результат на х (x³);
К: возвести результат в квадрат (х⁶);
К: возвести результат в квадрат (х¹²);
К: возвести результат в квадрат (х²⁴);
X: умножить результат на х (х²⁵);
К: возвести результат в квадрат (х⁵⁰);
К: возвести результат в квадрат (х¹⁰⁰).

Мы вычислили сотую степень числа х за 8 умножений. Это значительно эффективнее «прямолинейного» алгоритма возведения в степень, требующего 99 операций умножения.