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

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

Одним из основных методов построения рекурсивных алгоритмов является метод декомпозиции. Идея метода состоит в разделении задачи на части меньшей размерности, получении решений для выделенных частей и объединении решений при возврате рекурсивных вызовов. Если в алгоритме происходит разделение задачи на b подзадач, которое приводит к необходимости решения а подзадач размерностью п/Ь, то функцию трудоемкости (см. [3]) можно представить в виде FA (n)=aF A (n/b) + d(n) + U (п),где d(n) — трудоемкость алгоритма деления задачи на подзадачи, U(n) — трудоемкость алгоритма объединения полученных решений.Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману (см. 3.6. основного текста). На каждом рекурсивном вызове переданный массив делится пополам, что дает оценку для d(n) — 0(1), далее рекурсивно вызывается сортировка полученных массивов половинной длины (до тех пор,пока длина массива не станет равной единице), и возвращенные отсортированные массивы объединяются с трудоемкостью 0(п). Тогда ожидаемая трудоемкость на сортировку составит: FА (п) = 2 •FA(п/2) + 0 (1) + 0 (п). Тем самым возникает вопрос о получении оценки сложности функции трудоемкости, заданной в виде (Д.2.4), для произвольных целых значений а и Ь. Ответ на этот вопрос можно получить на основе теоремы о рекуррентных соотношениях, авторами которой являются Дж. Бентли, Д.Хакен и Дж. Сакс (статья 1980 г.), приведем ее формулировку в соответствии с [3]. Теорема Д.2.1. Пусть а > 1, b > 1 — константы, д(п) — функция, пусть далее

/ (п) = а • f (n/b) + д (п), где п/Ь = [п/Ъ] или п/Ь — [п/Ь], тогда

(1) Если д(п) = О (n^ log b (a-£)), £ > 0, то f(п) = 0 (n log b (a)).

Пример: / (п) = 8 • f (га/2) + п 2, тогда / (п) = 0 (п 3).

(2) Если g(n)=Q (n^ log b a), то / (n) = 0 (n^ log b a • log n).

Пример: / (n) = 2 • / (n/2) + 0 (n), тогда / (n) = 0 (n • logn).

(3) Если д (n) = 0 (n ^log b a+£), e > 0, то / (n) = 0 (g (n)).

Пример: / (n) = 2 • / (n/2) + n 2, здесь подходит случай (3), поскольку

n^log b a = П ^1, И; следовательно / (п) = 0 (п ^2).

Данная теорема является мощным средством анализа асимптотической сложности рекурсивных алгоритмов, использующих метод декомпозиции, но, к сожалению,она не дает возможности получить в явном виде коэффициенты функции трудоемкости. Для решения этой задачи необходим более детальный анализ рекурсивного дерева.На основании этой теоремы получим оценку сложности функции трудоемкости для алгоритма сортировки слиянием. Поскольку в этом случае д (п) — 0 (n:log2 2),то /д (п) = 0 (п • logn).