Анализ дерева рекурсивных вызовов

Теория алгоритмов

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

Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.

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

Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:

б) Примеры рекурсивного задания функций

1.	f(0)=0 f(n)= f(n-1)+1

2.	f(0)=1 f(n)= n*f(n-1)

Последовательная подстановка дает – f(n)=1*2*3*…*n = n!

Для полноты сведений приведем формулу Стирлинга для приближенного вычисления факториала для больших n:

Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически

Для получения функции в явном виде рассмотрим ее последовательные значения:f(0)=1, f(1)=2, f(2)=4, f(3)=8, что позволяет предположить, что f(n)=, точное доказательство выполняется по индукции.

Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения – f(n)=, как и в примере 4, что проверяется элементарной подстановкой.

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

Обозначив через Fn — n-ое число Фибоначчи, имеем: f(n)=.

Рекурсивная реализация алгоритмов

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

Источник

10.3 Подсчет вершин в дереве рекурсивных вызовов

Вэтом случае мы имеем полное дерево рекурсивных вызовов глубинойk, содержащееnлистьев, фрагмент дерева показан на рис 10.1.

Рис 10.1 Фрагмент рекурсивного дерева при сортировке слиянием

Обозначим количество вершин дерева через V:

V = n + n/2+n/4+n/8+. +1 = n*(1+1/2+1/4+1/8+. +1)=2n — 1=2 k+1 — 1

Из них все внутренние вершины порождают рекурсию, количество таких вершин – V_r = n-1, остальныеnвершин – это вершины в которых рассматривается только один элемент массива, что приводит к останову рекурсии.

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

Таким образом, для nлистьев дерева выполняется вызов процедурыMS c вычислением r+1, проверка условияp=qи возврат в вызывающую процедуру для слияния, что в сумме с учетом трудоемкости вызова даёт:

F1(n) = n*2*(5+4+1) + n*2(If p=q и r+1) = 22*n;

Для n-1 рекурсивных вершин выполняется проверка длины переданного массива, вычисление середины массива, рекурсивный вызов процедурMS, и возврат, поскольку трудоемкость вызова считается при входе в процедуру, то мы получаем:

Fr(n) = (n-1)*2*(5+4+1) + (n-1)*(1+3+1) = 24*n — 24;

Процедура слияния отсортированных массивов будет вызвана n-1раз, при этом трудоемкость складывается из трудоемкости вызова и собственной трудоемкости процедурыMerge:

Трудоемкость вызова составит (для 6 параметров и 4-х регистров):

Fm_вызов(n) = (n-1)*2*(6+4+1) = 22*n — 22;

Поскольку трудоемкость процедуры слияния для массива длиной mсоставляет18*m + 23 (10.1),и процедура вызываетсяn-1раз с длинами массива равнымиn, n/2, n/4, …,причем2раза с длинойn/2, 4раза с длинойn/4, то совокупно имеем:

Fm_{слияние}(n) = (n-1)*23 + 18*n + 2*18*(n/2) + 4*18*(n/4) + … + =

= 18*n *(log₂n – 1) + 23*(n-1) = 18*n* log₂n + 5*n — 23;

Учитывая все компоненты функции трудоемкости, получаем окончательную оценку:

Fa(n) = F1(n) + Fr(n) + Fm_вызов(n) + Fm_{слияние}(n) =

= 22*n + 24*n — 24 + 22*n — 22 +18*n* log₂n + 5*n — 23 =

= 18*n* log₂n + 73*n — 69 (10.2)

Если количество чисел на входе алгоритма не равно степени двойки, то необходимо проводить более глубокий анализ, основанный на изучении поведения рекурсивного дерева, однако при любых ситуациях с данными оценка главного порядка ( n* log₂n)не измениться [6].

10.5 Вопросы для самоконтроля

1. Рекурсивный алгоритм сортировки слиянием
2. Процедура слияния двух отсортированных массивов
3. Оценка трудоемкости процедуры слияния;
4. Подсчет вершин в дереве рекурсивных вызовов для алгоритма сортировки слиянием;
5. Анализ алгоритма рекурсивной сортировки методом прямого подсчета вершин рекурсивного дерева;

11. Теория и алгоритмы модулярной арифметики

11.1 Алгоритм возведения числа в целую степень

Задача о быстром возведении числа в целую степень, т.е. вычисление значения y = x n для целогоnлежит в основе алгоритмического обеспечения многих криптосистем [11], отметим, что в этом аспекте применения вычисления производятся поmod_k. Представляет интерес детальный анализ известного быстрого алгоритма возведения в степень методом последовательного возведения в квадрат [6]. В целях этого анализа представляется целесообразным введение трех следующих специальных функций: 1. Функция β(n) Функция определена для целого положительного n,иβ(n)есть количество битов в двоичном представлении числаn.Отметим, что функцияβ(n)может быть представлена в виде:β(n) =[log₂(n)]+1=[log₂(n+1)], где [х] – целая часть х, n > 0. 2. Функция β₁(n) Функция определена для целого положительногоn,иβ₁(n)есть количество «1» в двоичном представлении числаn. Отметим, что функцияβ₁(n)не является монотонно возрастающей функцией, например, для всехn=2 k β₁(n)=1. График функции для начальных значенийnпредставлен на рис 11.1. Рис 11.1 Значения функции для n=1,2,…9. В силу определения β₁(n)справедливо неравенство: 1 ≤ β₁(n)≤ β(n) =[log₂(n)]+1, т.е.β₁(n) = O(log₂(n)) Отметим, что функция β₁(n)может быть рекурсивно задана следующим образом [5]: β₁(0)=0; β₁(1) = 1; β₁(2n) = β₁(n); β₁(2n+1) = β₁(n) + 1; 3. Функция β₀(n) Функция определена для целого положительного n,иβ₀(n)есть количество «0» в двоичном представлении числаn. Отметим, что функцияβ₀(n)не является монотонно возрастающей функцией, так для всехn =2 k -1β₀(n)=0 Для любого nсправедливо соотношениеβ(n) = β₀(n) + β₁(n). Для дальнейшего анализа представляет так же интерес определение среднего значения функции β₁(n) для n = N>, где N=2 k -1 (т.е. двоичное представление числаNзанимаетkразрядов), обозначим его через β_s(N). Тогда:, поскольку количество чисел, имеющихLединиц вKразрядах равно количеству сочетаний изLпоK,то, тогда: , поскольку N=2 k -1, то: (11.1). Идея быстрого алгоритма решения задачи о возведении в степень состоит в использовании двоичного разложения числа nи вычисления соответствующих степеней путем повторного возведения в квадрат [6]. Пусть, например,n=11, тогда x 11 = x 8 * x 2 * x 1 , x 4 = x 2 * x 2 иx 8 = x 4 * x 4 . Алгоритмическая реализация идеи требует последовательного выделения битов, возведения хв квадрат и домноженияyна те степених, для которых в двоичном разложенииnприсутствует единица. XstK (x,n;y); z ¬ x; y ¬ 1; Repeat If (n mod 2) = 1 then y ¬ y*z; z ¬ z*z; n ¬ n div 2; Until n = 0 Return (y) End Получим функцию трудоемкости данного алгоритма, используя введенные ранее обозначения и принятую методику счета элементарных операций в формальной системе процедурно-ориентированного языка высокого уровня: Fa(n) = 2 + β(n)*(2+2+2+1) + β₁(n)*(2)= 7*β(n) + 2*β1(n)+2 (11.2) Количество проходов цикла определяется количеством битов в двоичном представлении n – β(n),а количество повторений операцииy ¬ y*z– количеством единиц в этом представлении– β₁(n),что и отражает формула 11.2. Определим трудоемкость алгоритма для особенных значений n, такими особенными значениями являются случаи, когдаn=2 k илиn=2 k — 1: — в случае если n=2 k , то β₁(n)=1 и Fa(n)= 7*β(n) + 4; — в случае если n=2 k -1, то β₁(n)= β(n) и Fa(n)= 9*β(n) + 2. Если показатель степени заранее неизвестен, то можно получить среднюю оценку, в предположении, что представление числа nзанимает не болееkдвоичных разрядов, т.е.n < 2k илиlog₂n k. Тогда по формуле(11.1) β_s(N) = β(N)/2, где N=2 k -1, откуда: Fa(n) ≤ 7*β(N) + 2*β_s(N)+2 = 8*β(N) + 2 =8*([log₂(n)]+1)+2 = 8*k +2. Таким образом, количество операций, выполняемых быстрым алгоритмом возведения в степень, линейно зависит от количества битов в двоичном представлении показателя степени. Введение специальных функций β₁(n) и β(n)позволило получить точное значение функции трудоемкости анализируемого алгоритма.

Читайте также:  Пленка черное дерево салон

Источник

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

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

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

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

При этом объем рекурсии — это одна из характеристик сложности рекурсивных вычислений для конкретного набора параметров, представляющая собой количество вершин полного рекурсивного дерева без единицы.

Будем использовать следующие обозначения для конкретного входного параметра D:

R(D) – общее число вершин дерева рекурсии,

Читайте также:  Цветок денежное дерево его полезные свойства

R_V(D) – объем рекурсии без листьев (внутренние вершины),

R_L(D) – количество листьев дерева рекурсии,

Например, для вычисления n -го члена последовательности Фибоначчи разработана следующая рекурсивная функция:

return Fib(n-1)+Fib(n-2); //декомпозиция

Тогда полное дерево рекурсии для вычисления пятого члена последовательности Фибоначчи будет иметь вид (рис. 34.1):

Рис. 34.1. Полное дерево рекурсии для пятого члена последовательности Фибоначчи

Характеристиками рассматриваемого метода оценки алгоритма будут следующие величины.

Источник