Анализ сложности и эффективности алгоритмов и структур данных

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

1. быть простым для понимания, перевода в программный код и отладки;

2. эффективно использовать вычислительные ресурсы и выполняться по возможности быстро.

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

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

Таким образом, будем различать временную T(n) и пространственную V(n) сложности алгоритма. При рассмотрении оценок сложности, будем использовать только временную сложность. Пространственная сложность оценивается аналогично.

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

1. временная сложность алгоритма программы;

2. качество скомпилированного кода исполняемой программы;

3. машинные инструкции, используемые для выполнения программы.

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

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

Часто, временная сложность алгоритма зависит от количества входных данных. Обычно говорят, что временная сложность алгоритма имеет порядок T(n) от входных данных размера n. Точно определить величину T(n) на практике представляется довольно трудно. Поэтому прибегают к асимптотическим отношениям с использованием O-символики.

Например, если число тактов (действий), необходимое для работы алгоритма, выражается как 11n² + 19n*log n + 3n + 4, то это алгоритм, для которого T(n) имеет порядок O(n²). Фактически, из всех слагаемых оставляется только то, которое вносит наибольший вклад при больших n (в этом случае остальными слагаемыми можно пренебречь), и игнорируется коэффициент перед ним.

Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n²), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов.

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

Таблица 1

Если считать, что числа соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы T(log n) потребуется 20 микросекунд, а алгоритму со временем работы T(n²) – более 12 дней.

Если операция выполняется за фиксированное число шагов, не зависящее от количества данных, то принято писать O(1).

Следует обратить внимание, что основание логарифма здесь не пишется. Причина этого весьма проста. Пусть есть O(log₂n). Но log₂n=log₃n/log₃2, а log₃2, как и любую константу, символ О() не учитывает. Таким образом, O(log₂n) = O(log₃n). К любому основанию можно перейти аналогично, а, значит, и писать его не имеет смысла.

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

• максимальную сложность T_max(n), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего;

• среднюю сложность T_mid(n) – сложность алгоритма в среднем;

• минимальную сложность T_min(n) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего.

Теоретическая оценка временной сложности алгоритма осуществляется с использованием следующих базовых принципов:

1. время выполнения операций присваивания, чтения, записи обычно имеют порядок O(1). Исключением являются операторы присваивания, в которых операнды представляют собой массивы или вызовы функций;

2. время выполнения последовательности операций совпадает с наибольшим временем выполнения операции в данной последовательности (правило сумм: если T₁(n) имеет порядок O(f(n)), а T₂(n) – порядок O(g(n)), то T₁(n) + T₂(n) имеет порядок O(max(f(n), g(n))) );

3. время выполнения конструкции ветвления (if-then-else) состоит из времени вычисления логического выражения (обычно имеет порядок O(1) ) и наибольшего из времени, необходимого для выполнения операций, исполняемых при истинном значении логического выражения и при ложном значении логического выражения;

4. время выполнения цикла состоит из времени вычисления условия прекращения цикла (обычно имеет порядок O(1) ) и произведения количества выполненных итераций цикла на наибольшее возможное время выполнения операций тела цикла.

5. время выполнения операции вызова процедур определяется как время выполнения вызываемой процедуры;

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