Методы оценки алгоритмов. Оценки итерационных и рекурсивных алгоритмов, страница 2

2  Оценки итерационных алгоритмов

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

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

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

//Функция принимает a - массив размера size

int inversionCount(const int* a, int n)

{

  int ic = 0;

  for (int i = 0; i < n; ++i)

    for (int j = i + 1; j < n; ++j)

      if (a[i] > a[j]) ++ic;

  return ic;

}

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

f(n) = sum (i=0, n-1) {sum (j=i+1, n-1) C} (здесь sum – замена),

f(n) = sum (i=0, n-1) {C (n - i - 1)},

f(n) = C (n² – n (n - 1) / 2 - n) = C (n² - n) / 2

Таким образом, для этого алгоритма f(n) = Θ(n²). Кстати, существует алгоритм, позволяющий найти количество инверсий в массиве за время Θ(nlogn). Если кто-то из новоприбывших найдёт его до 27 октября 2001 года и сможет вразумительно объяснить принцип его работы, он получит от лектора ценный приз в размере одной бутылки пива ценой от 0 до 5 грн.

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

3  Оценки рекурсивных алгоритмов

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

В качестве рабочего примера при рассмотрении способов оценки рекурсивных алгоритмов будет взят рекурсивный алгоритм сортировки слиянием, работающий за время Θ(nlogn). Поэтому первый подпункт главы будет посвящён именно этому алгоритму.

3.1  Сортировка слиянием

Данный алгоритм использует метод «разделяй и властвуй». Вначале исходный массив делится на 2 части, которые сортируются отдельно, а потом сливаются вместе. То же самое происходит с каждым из двух кусков и так далее до тех пор, пока в сортируемом куске массива не будет одного элемента. Всё гениальное просто. Кстати, данный алгоритм имеет приводившуюся выше асимптотически точную оценку Θ(nlogn), поэтому время его работы должно являться более устойчивым, чем у быстрой сортировки, для которой в худшем случае время выполнения равно O(n²).

Приведём код алгоритма.

//Функция принимает a - массив от p до r

void mergeSort(int* a, int p, int r)

{

  if (p < r) {

    int q = (p + r) / 2;

    mergeSort(a, p, q);

    mergeSort(a, q + 1, r);

    merge(a, p, q, r);  //Работает за время Teta(r - p + 1)

                        //Сливает куски [p, q] и [q + 1, r]

  }

}

Как видите, время работы данного алгоритма невозможно оценить формулой «в лоб», поскольку имеет место соотношение рекурсивного вида с неизвестной заранее глубиной рекурсии. Мы можем только написать рекурсивное соотношение для времени работы алгоритма сортировки:

f(n) = 2f(n/2) + Θ(n),

где n = r – p + 1 – длина сортируемого массива.

Формула верна, поскольку действительно в каждом случае исходный массив бьётся на две равные (или почти равные – это не принципиально) части, для каждой из которых происходит рекурсивный вызов, плюс слияние происходит за время, пропорциональное n. Конечно, необходимо добавить, что f(1) = Θ(1). Тогда рекурсия будет иметь конец.

Итак, приступим к изучению методов оценки рекурсивных алгоритмов.

3.2  Метод подстановки

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

Докажем оценку O(nlogn) для сортировки слиянием. Нам надо доказать, что f(n) <= cnlogn. Предположим, что выполняется неравенство

f(n/2) <= cn/2 log n/2

Подставим его в формулу для f(n). Имеем:

f(n) <= 2(cn/2 logn/2) + n = cnlogn – cnlog 2 + n = cnlogn + (1 - c)n <= cnlogn  (при c >= 1 и n₀ = 2)