Лекции - Структуры и алгоритмы компьютерной обработки данных / 2.Методы анализа рекуррентных алгоритмов

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

• Метод подстановки

• Метод итераций

• Анализ дерева рекурсии

• Применение общей теоремы

Пример: вычисление факториала

function fact( n: integer): integer;

begin

if n=0 then fact:=1

else fact:=fact(n-1)*n

end;

Сложность

T(n) = T(n-1)+ 1

T(0) =1

T(n)= Ө(n)

Под слиянием понимается объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. (Дж. Фон Нейман)

Алгоритм сортировки

1. Сначала разделим массив пополам,

2. Отсортируем обе половины с помощью рекурсивного вызова

3. Выполним слияние отсортированных половин в один массив

Оценка сложности сортировки слиянием

T(n) = 2 T (n/2) + n.

Предположим T(n) = O(nlogn).

T(n)≤cnlogn. Пусть оценка верна для n/2.

T(n)≤ 2c(n/2)log(n/2)+n ≤ cnlog(n/2) + n ≤ cnlogn – cnlog2+n ≤ cnlogn

Метод итераций

T(n)=3 T(n/4) + n. Подставляем в себя

T(n) = n+ 3T(n/4)= n+ 3( n/4+3T(n/16)) =

n+3/4n +9/16n + 27T(n/64) ≤

n+3/4n + 9/16n +… =

n Σ(3/4)i= 4n = Ө(n)

Дерево рекурсии

T(n)= 2T(n/2) + n2

T(n) = Ө(n2)

Теорема о рекуррентных соотношениях

a≥0, b>1 – константы, f(n) – функция, T(n)=aT(n/b)+f(n), тогда

1)если f(n)=O(nlogba-ε) для некоторого ε>0, то T(n) = Ө(nlogba)

2)если f(n)= Ө(nlogba), то T(n) = Ө(nlogbalog n)

3)если f(n)=Ω(nlogba+ε) для некоторого ε>0 и если af(n/b)<cf(n) для некоторого с<1 и n>n0, то T(n) = Ө(f(n))