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

временную функцию 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 справедлива, если будут выполняться неравенства 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).