Анализ трудоемкости алгоритма вычисления факториала
Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!