Анализ трудоемкости алгоритма вычисления факториала



Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, n, при этом передается и возвращается по одному значению (m=1, k=1), в предположении о сохранении четырех регистров – r=4, а на последнем рекурсивном вызове значение функции вычисляется непосредственно – в итоге:

fa(n)=n*2*(1+1+4+1)+(n-1)*(1+3)+1*2=18*n - 2

Отметим, что n – параметр алгоритма, а не количество слов на входе.

РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА

Логарифмические тождества

При анализе рекурсивных алгоритмов достаточно часто используются логарифмические тождества, далее предполагается, что, a > 0, b > 0, c > 0, основание логарифма не равно единице:


в записи Q(ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением Q.

Можно показать, что для любого

Методы решения рекурсивных соотношений

В математике разработан ряд методов, с помощью которых можно получить явный вид рекурсивно заданной функции – метод индукции, формальные степенные ряды, метод итераций и т.д. Рассмотрим некоторые из них:

а) Метод индукции

Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:

f(0)=1 f(n+1)=2*f(n)

Предположение: f(n)=

Базис: если f(n)= , то f(0)=1, что выполнено по определению.

Индукция: Пусть f(n)= , тогда для n+1 f(n+1)= 2 * =

Заметим, что базис существенно влияет на решение, так, например:

Если f(0)=0, то f(n)=0;

если f(0)=1/7, то f(n)=(1/7)* ; если f(0)=1/64, то f(n)=(2)

б) Метод итерации (подстановки)

Суть метода состоит в последовательной подстановке – итерации рекурсивного определения, с последующим выявлением общих закономерностей:

Пусть f(n)=3*f(n/4)+n, тогда:

f(n)=n+3*f(n/4)=n+3*[n/4+3*f(n/16)]=n+3*[n/4+3{n/16+3*f(n/64) }],

и раскрывая скобки, получаем:

f(n)=n+3*n/4+9*n/16+27*n/64+…+ *n/

Остановка рекурсии произойдет при , в этом случае последнее слагаемое не больше, чем

, то окончательно:

Рекурсивные алгоритмы.

Основной метод построения рекурсивных алгоритмов – это метод декомпозиции. Идея метода состоит в разделении задачи на части меньшей размерности, получение решение для полученных частей и объединение решений.

общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид:

fA(n )= a * fA( n/b )+d(n)+U(n) (9.1), где:

d(n) – трудоемкость алгоритма деления задачи на подзадачи,
U(n) – трудоемкость алгоритма объединения полученных решений.

Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману:

На каждом рекурсивном вызове переданный массив делится пополам, что дает оценку для d(n) =Q (1), далее рекурсивно вызываем сортировку полученных массивов половинной длины (до тех пор, пока длина массива не станет равной единице), и сливаем возвращенные отсортированные массивы за Q (n).

Тогда ожидаемая трудоемкость на сортировку составит:
fA(n )= 2 * fA( n/2 )+ Q (1)+ Q (n)

Тем самым возникает задача о получении оценки сложности функции трудоемкости, заданной в виде (9.1), для произвольных значений a и b.


Дата добавления: 2018-02-28; просмотров: 571; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!