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

      Комментарии к записи Анализ алгоритмов. понятие сложности алгоритма отключены

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

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

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

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

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

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

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

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

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

Определение.Будем говорить, что Т(n) алгоритма имеет порядок роста f(n), или, по-другому, алгоритм имеет теоретическую сложностьO*(f(n)),если найдутся такие константы с1, с20 и число п0, что c1 f(n))Т(п)c2 f(n) при всех п = n0. Здесь предполагается, что функция f(n) неотрицательна, но крайней мере при п = n0. Если для Т(п) выполняется условие Т(n)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Самое сложное выживание! День 35+ V.1.21 Сложность: Custom! Interloper+! ► [The Long Dark]