Основы анализа алгоритмов

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

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

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

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

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

Некоторые часто встречающиеся классы функций приведены в таблице. В этой таблице приведены значения функций из данного класса на широком диапазоне значений аргумента. Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Во-вторых, быстродействующие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего. Если, например, установлено, что алгоритму нужно x³-30x операций, то будем считать, что сложность алгоритма растёт как x³. Причина этого в том, что уже при 100 входных данных разница между x³ и x³ -30x составляет лишь 0,3%.

Таблица классов роста функций

Скорость роста сложности алгоритма играет важную роль, скорость роста определяется старшим, доминирующим членом формулы. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является. Алгоритмы можно сгруппировать по скорости роста их сложностей. Мы вводим три категории: алгоритмы, сложность которых растёт по крайней мере так же быстро, как данная функция (класс Ω(f) - читается Омега большое), алгоритмы, сложность которых растёт с той же скоростью(класс О(f) - читается О большое) и алгоритмы, сложность которых растёт медленнее, чем эта функция (класс θ(f) - читается Тета большое).

Мы занимаемся эффективностью алгоритмов, поэтому класс Ω(f) не будет представлять для нас большого интереса: например в Ω(n²) входят все функции, растущие быстрее, чем n².

Класс О(f) состоит из функций, растущих не быстрее f. Функция f образует верхнюю границу для класса О(f). Проверить принадлежит ли данная функция классу О(f) можно двумя способами:

1. С формальной точки зрения функция g принадлежит классу O(f), если g(n) cf(n) для всех n, больших некоторого n₀, и для некоторой положительной константы с.

2. g принадлежит O(f), если lim(g(n)/f(n)) = c (n-> ) для некоторой константы с.

По правилу Лопиталя можно заменить предел самих функций пределом их производных.

Через θ (f) мы обозначаем класс функций, растущих с той же скоростью, что и f. С формальной точки зрения этот класс представляет пересечение двух предыдущих классов θ(f)= Ω(f) O(f). При сравнении алгоритмов нас будут интересовать такие, которые решают задачу быстрее, поэтому класс θ(f) нам не очень интересен.