3. П одход заключается в использовании общих решений определенных рекуррентных

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

принципов организации рекурсии: рекурсия, организованная по принципу «разделяй и властвуй» и аддитивное уменьшение размерности задачи на некоторую константу.
Использование этих теорем позволяет избежать утомительных расчетов и выбрать наименее трудоемкую схему организации рекурсии.

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




«Разделяй и

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

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

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

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

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

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

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

общее число вершин дерева рекурсии,
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).
Во внутренних вершинах дерева выполняются некоторые действия, связанные с подготовкой параметров для следующих рекурсивных вызовов и обработкой возвращаемых результатов. Трудоемкость такой обработки может зависеть как от обрабатываемых в этой вершине данных, так и от положения вершины в дереве рекурсии. С целью учета этой зависимости, введем нумерацию внутренних вершин, начиная с корня, по уровням дерева.

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

зависимостей для характеристик дерева как функций от длины входа N и/или характеристических особенностей множества входных данных.
2. Определение трудоемкости обслуживания рекурсии на один вызов-возврат Fс/b.
3. Определение трудоемкости алгоритма при останове рекурсии FCL(1).
4. Исследование трудоемкости продуктивных вычислений во внутренних вершинах дерева рекурсии .
5. Получение функции трудоемкости рекурсивного алгоритма .