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

При n = 1  log 1 = 0, а это мешает выполнению неравенства при начальных условиях. Поэтому-то n₀ = 2.

Доказано.

Как же угадать оценку?

Можно действовать по аналогии, т. к. похожая формула может иметь такую же оценку. Например, f(n) = 2f(n/2 + 6) + Θ(n) также имеет оценку O(nlogn), что логично предполагать.

Можно приближать оценки постепенно, пока очередную приближённую оценку ещё можно будет доказать.

Можно использовать замену переменных для нахождения подобия.

Можно, в конце концов, просто взять оценку получше с потолка и доказать.

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

3.3  Метод итераций

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

Рассмотрим этот метод на примере сортировки слиянием. У нас есть рекуррентное соотношение f(n) = 2f(n/2) + Θ(n). Его можно разложить в сумму следующим образом:

f(n) = 2f(n/2) + n = n + 2(n/2 + 2f(n/4)) = n + 2(n/2 + 2(n/4 + sf(n/8))) = …

Здесь чётко прослеживается сумма по n. В итоге получим формулу:

f(n) = n + n + … + n + Θ(2^{log n})

Тут n повторится logn раз (поскольку до вызова f(1) рекурсия дойдёт через logn шагов; собственно, по этой же причине останется 2^{log n} членов f(1) с оценкой Θ(1)). Имеем формулу:

f(n) = sum(0, log n) n + Θ(n) = n log n + n + Θ(n) = Θ(n log n)

Итак, нами найдена точная асимптотическая оценка сортировки слиянием. Она оказалась равна ожидаемой, что является просто замечательным фактом.

Этот метод нахождения оценки очень хорош. Но у него есть и недостаток – сложно уследить за временем, потраченном на очередном уровне рекурсии, и глубиной рекурсии одновременно. Для облегчения этой задачи используются деревья рекурсии.

Покажем дерево рекурсии для нашей сортировки:

n        

n/2                                  n/2

n/4                n/4                n/4                n/4

……

Глубина полученного дерева – logn, а сумма элементов каждого уровня равна n. Получаем для сортировки оценку f(n) = Θ(nlogn).

Итак, метод итераций в паре с деревьями рекурсии даёт хороший результат. Но следующий метод даёт универсальную функцию для определённых типов рекурсий.

3.4  Общая формула

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

f(n) = af(n/b) + g(n),

где a >= 1, b > 1 – константы, а g(n) – функция, положительная для больших значений n.

Такое соотношение обычно возникает, если алгоритм разбивает задачу на a подзадач трудоёмкостью n/b каждая. Для объединения результатов выполнения этих подзадач необходимо время g(n).

Основная теорема о рекуррентных оценках

Пусть a >= 1 и b > 1 – константы, g(n) – функция, f(n) определено при неотрицательных n формулой

f(n) = af(n/b) + g(n),

где под n/b понимается либо ceil(n/b), либо floor(n/b). Тогда:

1)  если g(n) = O(n^log_b^a-e) для некоторого e > 0, то f(n) = Θ(n^log_b^a);

2)  если g(n) = Θ(n^log_b^a) , то f(n) = Θ(n^log_b^alogn);

3)  если g(n) = Ω(n^log_b^a+e) для некоторого e > 0 и если ag(n/b) <= cg(n) для некоторой константы c < 1 и достаточно больших n, то f(n) = Θ(g(n)).

В чём же заключается суть теоремы?

Функция g(n) сравнивается с n^log_b^a и, в зависимости от результатов, выводится та или иная оценочная формула. При этом функция g(n) не просто должна быть меньше или больше n^log_b^a – между функциями или не должно быть зазоров, или должен быть зазор не меньше n^e, при этом e есть сколь угодно малая константа. Кроме того, должно выполняться условие регулярности ag(n/b) <= cg(n), которое гарантирует у последующих шагов трудоёмкость не большую, чем у предыдущих.

Попробуем применить основную теорему к сортировке вставками. Для неё a = b = 2, g(n) = n. Тогда n^log_b^a = n, g(n) = n = Θ(n).

Значит, f(n) = Θ(nlogn), что и требовалось доказать.

4  Домашнее задание

1.  Оцените алгоритмы задач II тура.

2.  С помощью метода итераций решите соотношение f(n) = f(n - a) + f(a) + n, a >= 1 – некоторая константа.

3.  С помощью основной теоремы найдите оценку времени работы алгоритма двоичного поиска (f(n) = f(n/2) + Θ(1)).

4.  Дан массив S из n действительных чисел, а также число x. Как за время Θ(nlogn) определить, можно ли представить x в виде суммы двух элементов массива S?

5  Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Ривест [2001], Алгоритмы. Построение и анализ, МЦНМО, М., 35–77

Дональд Э. Кнут [2000], Искусство программирования, третье издание. Том 1: Основные алгоритмы, Вильямс, 127-155