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

Лекция 1: Методы оценки алгоритмов

0  Введение в оценку алгоритмов

Вопрос «Зачем оценивать алгоритмы?» возникает первым. Оценив время работы алгоритма в тех или иных условиях, вы сможете сравнить результаты  с другими результатами подобных исследований и выбрать для себя именно тот алгоритм, который в вашем конкретном случае принесёт наибольшую выгоду, будь то денежный эквивалент или восхищение начальства по поводу «этого нового супербыстрого алгоритма».

Вопрос «Зачем мне оценивать алгоритмы?» вызывает целый ряд других вопросов. А вы разве не хотите выжать из предоставленной вам техники максимум? Или, может, вы желаете, чтобы инженеры занимались анализом, а программисты – кодированием? Нет, так дело не пойдёт. Программист – это нечто большее, нежели кодировщик, выучивший, скажем, Visual Basic на курсах «VB за 3 секунды». Программист – это не только человек, который может самостоятельно разработать алгоритм, а и аналитик, который сможет обосновать то, почему он использовал именно алгоритм X, а не алгоритм Z.

Вопрос «Что означает словосочетание “оценка алгоритмов”?» уже ближе к истине. Предполагается, что оцениваемый вами алгоритм является так называемой массовой задачей. Т. е. время работы алгоритма является некоторой функцией от параметра алгоритма, причём параметр всегда один. Например, для сортировок параметром является длина сортируемой последовательности, а для алгоритмов на матрицах параметром чаще всего выступает количество элементов матрицы. Итак, в общем случае время работы t алгоритма является функцией от n – параметра алгоритма.

t = f(n)

Вот эту f(n) вам и надо найти. Как это делать? Читай ниже.

1  Асимптотические обозначения

1.1  Основы оценки и Θ-обозначение

Для начала попробуем оценить какой-нибудь несложный алгоритм. Например, алгоритм поиска целого в массиве. Код подобного алгоритма предельно прост:

//Функция принимает a - массив размера n, и искомое целое x

bool isInArray(const int* a, int n, int x)

{

  while (n)

    if (a[--n] == x) return true;

  return false;

}

Оператор if выполняется за константное время (C). Он содержится в теле цикла, количество итераций которого заранее неизвестно. В худшем случае цикл выполняется n раз (если искомого числа нет в массиве), в лучшем – 1 раз (если число находилось в конце массива). В среднем (при равномерном распределении чисел и случайном выборе искомого) цикл выполнится n / 2 раз. Оператор return и затраты на вызов функции можно не брать в расчёт, поскольку они занимают постоянное время.

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

t = C (n - 1) / 2

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

Приведенную выше формулу можно оценить следующим образом:

f(n) = C (n - 1) / 2 = Θ(n)

Эта запись читается как «эф от эн равно тэта от эн» и означает, что функция f(n) пропорциональна некой функции g(n) (в данном случае g(n) = n), или функция g(n) является асимптотически точной оценкой f(n). Если говорить строго математически, то

f(n) = Θ(g(n))

означает

0 <= c₁ g(n) <= f(n) <= c₂ g(n)  для всех  n >= n₀,

где c₁, c₂ > 0 – константы.

Итак, для нашего алгоритма

c₁ n <= C (n - 1) / 2 <= c₂ n,

c₁  <= C / 2 - 1 / (2n) <= c₂  при  c₁ = (C – 1) / 2; c₂ = C / 2; n₀ = 1

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

Кроме Θ-обозначения существуют Ω- и O-обозначения (читаются «омега» и «о большое»).

1.2  Ω-обозначение

Применяется для оценки функции снизу.

Запись

f(n) = Ω(g(n))

означает

0 <= cg(n) <= f(n)  для всех  n >= n₀,

где c – константа.

1.3  O-обозначение

Применяется для оценки функции сверху.

Запись

f(n) = O(g(n))

означает

0 <= f(n) <= cg(n)  для всех  n >= n₀,

где c – константа.

1.4  Свойства асимптотических обозначений

f(n) = Θ(g(n)) если и только если f(n) = O(g(n)) и f(n) = Ω(g(n))

Транзитивность:

f(n) = Θ(g(n)) и g(n) = Θ(h(n)) влечёт f(n) = Θ(h(n))

f(n) = O(g(n)) иg(n) = O(h(n)) влечётf(n) = O(h(n))

f(n) = Ω(g(n)) иg(n) = Ω(h(n)) влечётf(n) = Ω(h(n))

Рефлексивность:

f(n) = Θ(g(n)),      f(n) = O(g(n)),      f(n) = Ω(g(n))

Симметричность:

f(n) = Θ(g(n)) если и только если g(n) = Θ(f(n))

Обращение:

f(n) = O(g(n)) если и только если g(n) = Ω(f(n))

1.5  Послесловие

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