Анализ алгоритмов. Понятие сложности алгоритма

Если для решения задачи существует один алгоритм, то можно придумать и много других алгоритмов для решения этой же задачи. Какой алгоритм лучше подходит для решения конкретной задачи? По каким критериям следует выби­рать алгоритм из множества возможных? Как правило, мы высказываем суждение об алгоритме на основе его оценки исполнителем-человеком. Алгоритм кажется нам сложным, если даже после внимательного его изучения мы не можем понять, что же он делает. Мы можем наз­вать алгоритм сложным и запутанным из-за того, что он обладает разветвленной логической структурой, содержа­щей много проверок условий и переходов. Однако для компьютера выполнение программы, реализующей та­кой алгоритм, не составит труда, так как он выполняет одну команду за другой, и для компьютера неважно — операция ли это умножения или проверка условия.

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

Для оценки эффективности алгоритмов введено поня­тие сложности алгоритма.

Определение. Вычислительным процессом, порожденным алгоритмом, называется последовательность шагов алгоритма, пройденных при исполнении этого ал­горитма.

Определение. Сложность алгоритма — коли­чество элементарных шагов в вычислительном процессе этого алгоритма.

Обратите внимание, именно в вычислительном про­цессе, а не в самом алгоритме. Очевидно, для сравнения сложности разных алгоритмов необходимо, чтобы слож­ность подсчитывалась в одних и тех же элементарных действиях.

Определение. Временная сложность алгорит­ма — это время Т, необходимое для его выполнения. Оно равно произведению числа элементарных действий на среднее время выполнения одного действия: Т = kt.

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

Пусть есть алгоритм А. Для него существует пара­метр а, характеризующий объем обрабатываемых алго­ритмом данных, этот параметр часто называют размер­ностью задачи. Обозначим через Т(n) время выполне­ния алгоритма, через f — некую функцию от п.

Определение. Будем говорить, что Т(n) алгорит­ма имеет порядок роста f(n), или, по-другому, алго­ритм имеет теоретическую сложность O^*(f(n)), если найдутся такие константы с₁, с₂ > 0 и число п₀, что c₁ f(n)) < Т(п) < c₂ f(n) при всех п >= n₀. Здесь предпола­гается, что функция f(n) неотрицательна, но крайней мере при п >= n₀. Если для Т(п) выполняется условие Т(n) <= сf(п), то говорят, что алгоритм имеет теорети­ческую сложность О(п) (читается "о" большое от n).

Так, например, алгоритм, выполняющий только опе­рации чтения данных и занесения их в оперативную па­мять, имеет линейную сложность 0(п). Алгоритм сорти­ровки методом прямого выбора имеет квадратичную сложность 0(п²), так как при сортировке любого мас­сива надо выполнить (п²- п)/2 операций сравнения (при этом операций перестановок вообще может не быть, на­пример, на упорядоченном массиве, в худшем случае надо будет выполнить п перестановок). А сложность алгоритма умножения матриц (таблиц) размера п x п будет уже кубической O(n³), так как для вычисления каждого эле­мента результирующей матрицы требуется п умножений и п - 1 сложений, а всего этих элементов п².

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

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

Если мы рассматриваем алгоритмы, реализующиеся на компьютере, то к требованию выполнения за разумное время прибавляется требование выполнения в ограни­ченном объеме оперативной памяти.

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

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

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

Заменим в этой записи каждую " 1" парой букв КХ, а каждый "О" — буквой К.

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

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

Пример 1. Возвести х в степень п = 100.

Переведем число п в двоичную систему счисления: п = 100₁₀= 1100100,

Строим последовательность КХКХКККХКК

Вычеркиваем АХ слева => КХКККХКК

Вычисляем искомое значение

К => возводим х в квадрат => получаем х²,

X => умножаем результат на х=> получаем х³

К => возводим результат в квадрат => получаем х⁶

К=> возводим результат в квадрат => получаем х¹²,

К=> возводим результат в квадрат => получаем х²⁴,

Х=> умножаем результат на х =>получаем х²⁵

К=> возводим результат в квадрат => получаем x⁵⁰

К=> возводим результат в квадрат => получаем х¹⁰⁰.

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

Например, при п = 49 учащиеся могут предложить такой эффективный алгоритм возведения в степень:

При реализации этого алгоритма было выполнено 7 операций умножения (вместо 48 операций при вы­числении "в лоб") и использовано 3 ячейки (для хранения переменной х, для хранения значения х¹⁶ и для хране­ния текущего результата, получаемого на каждом шаге). Если же использовать алгоритм "Быстрого возведения в степень", то получим то же количество операций (7 операций умножения), но для реализации этого алгоритма потребуется только 2 ячейки (для хранения переменной х и для хранения текущего результата).

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

Пример 2. Умножим 23 на 43 "русским" методом.

Ответ: 23 х 43 = 23 + 46 + 184 + 736 = 989.

В итоговую сумму вошли числа первого столбца, рядом с которыми во втором столбце стоят нечетные числа.