Тема 1.2. Классификация алгоритмов по степени сложности

1.2. Виды функций оценки сложности алгоритмов

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

1. O(k*f) = O(f),

2. O(f*g) = O(f)*O(g),

3. O(f+g) = Max (O(f), O(g)).

Здесь k обозначает константу, а f и g - функции.

Первое правило означает, что постоянные множители не имеют значения для определения порядка сложности, например, O(2*n) = O(n). В соответствии со вторым порядок сложности произведения двух функций равен произведению их сложностей. Например, O((10*n)* n) = O(n)* O(n) = O(n²). На основании третьего правила порядок сложности суммы двух функций равен максимальному (доминирующему) значению из их сложностей. Например, O(n⁴ + n²) = O(n⁴).

На практике применяются следующие виды О-функций:

a) О(1) – константная сложность, для алгоритмов, сложность которых не зависит от размера данных.

b) О(n) – линейная сложность, для одномерных массивов и циклов, которые выполняются n раз,

c) О(n²), О(n³), … – полиномиальная сложность, для многомерных массивов и вложенных циклов, каждый из которых выполняется n раз,

d) О(log(n)) – логарифмическая сложность, для программ, в которых большая задача делится на мелкие, которые решаются по-отдельности,

e) О(2ⁿ) – экспоненциальная сложность, для очень сложных алгоритмов, использующих полный перебор или так называемый «метод грубой силы».

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

1.3. Экспериментальный метод
оценки трудоемкости (сложности) алгоритма

Метод основан на измерении времени выполнения алгоритма на некотором наборе данных (тесте). При этом используются стандартные средства языка программирования, позволяющие определить системное время компьютера. Например, для среды java это могут быть методы System.CurrentTimeMillis (), позволяющий фиксировать время с точность до миллисекунд и System.nanoTime() – до наносекунд. Последний имеет ограничения и работает не на всех платформах.

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

long start = System.nanoTime();

// Фрагмент программы, реализующий исследуемый алгоритм

long end = System.nanoTime();

long traceTime = end-start;

traceTime даст искомое время.

Быстродействие современных процессоров с тактовой частотой в несколько Гигагерц имеет порядок нескольких десятков миллиардов операций в секунду. При этом время выполнения простых алгоритмов может быть очень малым, а измерение его предлагаемым методом будет иметь большую погрешность. Для ее уменьшения можно зациклить выполнение исследуемого фрагмента (например, повторить его 1000 или 10 000 раз), а величину traceTime поделить на число повторений цикла.

2. Оценка пространственной (емкостной) сложности

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

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

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

Оценка временной сложности в таком случае должна осуществляться экспериментально.

Лекция 2