11.2. Сложность алгоритмов

Изменение алгоритма во времени или время, затраченное алгоритмом как функция размерности задачи, называется временной сложностью алгоритма (ВСА).

ВСА — это количество единиц времени, требуемое для обработки входных данных задачи.

Обозначается ВСА O[f_A(n)]. Функция f_A(n) дает верхнюю границу для максимального числа операций, которые должен выполнить алгоритм для решения любой задачи размерности n.

Основные операции — это сдвиг, сравнение, сложение и тому подобное.

Существует теорема, что для достаточно больших n линейные алгоритмы всегда эффективнее квадратичных, кубичных и т.д. алгоритмов.

Четкой границы между экспоненциальными и полиномиальными алгоритмами нет.

Все алгоритмы, у которых ВСА O(n), O(n²), O(n³), считаются эффективными и применяются при решении практических задач.

Все алгоритмы, у которых ВСА O(n⁵) и выше, считаются не эффективными для использования на практике.

Кроме ВСА, важной характеристикой является сложность алгоритма (СА). Сложность алгоритма характеризуется числом выполняемых операций N и общим объемом используемой информации.

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

С числом операций алгоритма связано время его выполнения на конкретной ЭВМ. Объем информации связан с объемом памяти ЭВМ, необходимой для реализации этого алгоритма. Значит, время реализации алгоритма есть функция T = f(N, V).

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

Количество операций для алгоритма получается следующим образом. На основании анализа алгоритма можно получить вектор встречаемости операций в алгоритме

N = {Q₁, Q₂, ..., Q_r},

где Q_i — количество операций в исследуемом классе задач,

N = , P_i = Q_i/N— относительная частота операций.

Умножая время выполнения каждой операции на количество этих операций и суммируя результаты по всем операциям, получим время реализации алгоритма:

T = .

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

B_i = t_i / t_э,

где t_i — время реализации i-й операции; t_э — время реализации эталонной операции сложения.

Тогда количество условных элементарных операций составит

N = ,

а общее время их реализации — T_э = N_эt_э.

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

И = Ип + Ии + Ив + Ипр,

где И — общий объем информации; Ип — объем программной информации; Ии — объем исходной информации; Ив — объем выходной информации; Ипр — объем промежуточной информации.

Тогда обобщенный коэффициент сложности Ксл = Nэ/И, т.е. он характеризуется числом эталонных операций, выполняемых при обработке единицы информации.

В современных ЭВМ распределением памяти занимается операционная система, и пользователь зачастую не знает, какую память он использует.

В современных ЭВМ объем внешней памяти значительно опережает объем оперативной памяти:

V_в.п. >> V_о.п.,

поэтому T = f(N, V_в.п.).

Основной путь повышения скорости реализации алгоритма — это параллельное выполнение большого числа операций.

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

Обычно изучают зависимость времени работы от размера входной последовательности. Способ измерения размера входа зависит от конкретной задачи. В одних случаях, как, например, для задачи сортировки, под размером понимают число элементов на входе. В других размером принято считать общее число битов, необходимое для представления всех входных данных. Иногда размер входа измеряется не одним числом, а несколькими (например, число вершин и число рёбер графа).

Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Каждая строка псевдокода требует фиксированного числа операций (если только это не словесное описание каких-то сложных действий — типа «отсортировать все точки по координате x»). Также необходимо различать вызов процедуры (исполняемый за фиксированное число операций) и её выполнение, которое может быть долгим.

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

• Зная время работы в худшем случае, можно гарантировать, что выполнение алгоритма для всех входов данной размерности займет не более определенного промежутка времени вне зависимости от конкретного входа;

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

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

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

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

Предположим, что алгоритм разбивает задачу размера n на а подзадач, каждая из которых имеет в b раз меньший размер. Считаем, что разбиение требует времени D(n), а соединение полученных решений — времени С(n). Тогда получаем соотношение для времени работы Т(n) на задачах размера n (в худшем случае): Т(n) = aT(n/b) + D(n) + C(n). Это соотношение справедливо для достаточно больших n, когда задачу имеет смысл разбивать на подзадачи. Для малых n, когда такое разбиение невозможно или не нужно, применяется какой-либо прямой метод решения задачи. Так как n ограничено, время работы тоже не превосходит некоторой константы.

Можно сказать, что разработка эффективных алгоритмов не менее важна, чем разработка аппаратного обеспечения.

Основной метод повышения скорости работы алгоритма - это параллельные вычисления. В соответствии с гипотезой Минского параллельные машины, выполняющие последовательную программу над n множествами данных, повышают производительность, по крайней мере, на множитель O(log n).

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