Методы анализа сложности рекурсивных алгоритмов

конструкций «следование», «ветвление», «цикл» с использованием правил суммы и произведения.
Рекурсивные

алгоритмы
Основные элементы:
1)метод рекуррентных соотношений (только временная сложность)
2) Теоретико - графовый метод исследования дерева рекурсии.

t(n), где n определяет объем аргументов процедуры. Затем пытаются построить

и решить рекуррентное соотношение, которому удовлетворяет функция t(n).

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

оценки временной сложности.
Позволяет получить только верхнюю оценку для t(n).
Рекуррентное соотношение

для t(n) удается найти только тогда, когда преобразование, уменьшающее значение параметра рекурсии n, линейно относительно n.
Если рекуррентное соотношение для t(n) найдено, нет ни какой гарантии, что удастся получить асимптотическую оценку так как общих методов решения рекуррентных соотношений - нет!

f(n), которая мажорировала бы t(n) для всех значений n (т.е.

для всех n  1 должно выполняться неравенство t(n) < f(n)). Часто, для начала, определяется только вид функции f(n), предполагая, что она зависит от некоторых пока неопределенных параметров (например, f(n) = an2, где а — неопределенный параметр), затем подбираются такие значения параметров, чтобы для всех значений n выполнялось неравенство t(n) < f(n).

метода математической индукции доказывается, что решение правильное;
вычисляются константы.
Пример 1: (точное

решение).

пока неопределенный параметр. При n=1 эта оценка «не работает», т.к.

выражение an log(n)=0 независимо от значения a. Добавим константу к функции: T(n)≤an log(n)+b. При n = 1 эта оценка правильная, если положить b  с1.
Далее в соответствии с методом математической индукции предполагаем, что для всех k < n выполняется неравенство
t(k)  ak log(k) + b и попытаемся доказать, что t(n)  an log(n) + b.
Пусть эта оценка верна для k=n/2, т.е. T(n/2)≤a(n/2)log(n/2)+b. Подставим ее в исходное соотношение:

Последнее неравенство получено в предположении, что а  с2 + b.

если будут выполняться неравенства b  с1 и а 

с2 + b. В данном случае можно удовлетворить этим неравенствам, если положить b = с1 и а = с1 + с2. Вывод: для всех n > 1 выполняется неравенство и следовательно t(n) имеет порядок O(nlog(n)).

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

рекуррентном соотношении в правую часть последовательно подставляются выражения для t(m), m < n, так, чтобы исключить из правой части все выражения t(m) для m > 1, оставляя только t(1). Поскольку t(1) всегда является константой, то в результате получим формулу для t(n), содержащую только n и константы. Такая формула называется "замкнутой формой" для t(n).