Презентация на тему Рекуррентные соотношения, характерные для двух основных принципов организации рекурсии

рекурсии
В общем виде значение функции сложности рекурсивного алгоритма вычисляется

по формуле:




«Разделяй и властвуй»
Идея метода состоит в разделении задачи на части меньшей размерности n/k, где k >1, получении решений для частей и объединение решений.

дерева рекурсии
Строится полное дерево рекурсии узлами которого являются наборы

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

рекурсивных вызовов и возвратов, выполняемых при одном рекурсивном обращении,

а также с количеством таких обращений. При вызове функции в стек помещается адрес возврата, состояние необходимых регистров процессора, состояние локальных ячеек вызывающей функции, адреса возвращаемых значений и передаваемые параметры.
Введем следующие обозначения: p — количество передаваемых фактических параметров, r — количество сохраняемых в стеке регистров, k — количество возвращаемых по адресной ссылке значений, l — количество локальных ячеек процедуры.
Трудоемкость, связанная с обслуживанием одного вызова и одного возврата, обозначается через Fс/b = 2*(p+r+k+l+1). Где дополнительная единица учитывает операции с адресом возврата.

рекурсивных вызовов – наибольшее одновременное количество рекурсивных обращений функции,

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

N:
R(N) – общее число вершин дерева рекурсии,
RV(N) – объем

рекурсии без листьев (внутренние вершины),
RL(N) – количество листьев дерева рекурсии,
HR(N) – глубина рекурсии.
Очевидно, что R(N)= RV(N)+ RL(N), HR(N)≤ RV(N)+ RL(N).
Требуемый объем памяти в области программного стека определяется не общим количеством вершин порождённого дерева рекурсии, а максимальной глубиной его листьев.
V (N) = HR(N) *(p+r+k+l+1) *uβ– оценка требуемой памяти, где N – вход, uβ - длина слова в байтах.

отличии от оценки объема памяти, которая зависит от максимальной

глубины рекурсивного дерева, для функции трудоемкости количество операций со стеком на один вызов/возврат Fс/b должно быть учтено для всех вершин рекурсивного дерева.
Метод получения ресурсных функций для рекурсивных алгоритмов на основе анализа порожденного дерева рекурсии заключается в определении ресурсных затрат в каждой вершине дерева и их суммировании.
Таким образом, основная задача при использовании этого метода состоит в теоретическом построении функций RV(N), RL(N) и HR(N) — как функций от характеристик множества входных данных.

ряд особенностей рекурсивной реализации, а именно:
- ресурсные затраты

на обслуживание рекурсивных вызовов-возвратов, передачу параметров и возврат значений рекурсивных функций (ресурсные затраты обслуживания рекурсии);
- специфику фрагмента останова рекурсии, приводящую к необходимости отдельного учета ресурсных затрат в листьях дерева рекурсии. 
Трудоемкость алгоритма A на конкретном входе N — FA(N) определяется трудоемкостью обслуживания дерева рекурсии, зависящей от общего количества его вершин, и трудоемкостью продуктивных вычислений, выполненных во всех вершинах дерева рекурсии.

дерева рекурсии, FC(N) — трудоемкость продуктивных вычислений алгоритма, тогда

трудоемкость всего алгоритма:
FА(N)= FR(N)+ FC(N) (*)
Трудоемкость обслуживания дерева рекурсии:
FR(N) = R(N) * Fс/b
При подсчете трудоемкости продуктивных вычислений необходимо учесть, что для листьев рекурсивного дерева трудоемкость отлична от трудоемкости во внутренних вершинах.
Пусть FCV(N) — трудоемкость продуктивных вычислений (обработки данных) во внутренних вершинах, FCL(N) — трудоемкость вычислений в листьях дерева рекурсии, тогда FC(N) = FCV(N) + FCL(N).

дерева (как правило выражается фиксированным числом базовых операций). Зная

количество листьев порожденного дерева рекурсии, можно определить FCL(N) = FCL(1)* RL(N).
Во внутренних вершинах дерева выполняются некоторые действия, связанные с подготовкой параметров для следующих рекурсивных вызовов и обработкой возвращаемых результатов. Трудоемкость такой обработки может зависеть как от обрабатываемых в этой вершине данных, так и от положения вершины в дереве рекурсии. С целью учета этой зависимости, введем нумерацию внутренних вершин, начиная с корня, по уровням дерева.