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

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

Пример рекурсии. Вычисление факториала
static int Factorial(int x)
{
if (x == 1)
{
return 1;
}
else
{
return x * Factorial(x - 1);
}
}
n! - факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно.
Формула: n!= n*(n-1)!
0!=1

Рекурсивные вызовы
Factorial(3)
return 3 * Factorial(2)
Factorial(3)
return 3 * Factorial(2)
Factorial(3)
Factorial(2)
return 3 * Factorial(2)
Factorial(3)
Factorial(2)
return 2 * Factorial(1)
return 3 * Factorial(2)
Factorial(3)
Factorial(2)
return 2 * Factorial(1)
Factorial(1)
return 3 * Factorial(2)
Factorial(3)
Factorial(2)
return 2 * Factorial(1)
Factorial(1)
return 1
2
2
2
1
2
1

Рекурсивные вызовы
return 3 * Factorial(2)
Factorial(3)
Factorial(2)
return 2 * Factorial(1)
Factorial(1)
return 1
2
1
1
return 3 * Factorial(2)
Factorial(3)
Factorial(2)
return 2
2
2
return 3 * 2
Factorial(3)
6

Построение оценки для рекурсивного алгоритма
static int Factorial(int x) Т(n)
{
if (x == 1) 1
{
return 1; 1
}
else 1
{
return x * Factorial(x - 1); Т(n-1)
}
}
T(n)=T(n-1)+Ɵ(1)

Методы решения рекуррентных отношений
Метод итераций
Дерево рекурсии
Основная теорема

Метод итераций
На основании формулы T(n) записываем формулу для меньшего элемента, находящегося в правой части формулы, например T(n-1).
Подставляем правую часть полученной формулы в исходную формулу
Выполняем первые два шага, пока не развернем формулу в ряд без функции T(n)
Оценим полученный ряд на основании арифметической или геометрической прогрессии

Сумма n - первых членов арифметической прогрессии Sn=a1+a2+…+an
может быть найдена по формуле
где а1 — первый член прогрессии, аn— член с номером n , n — количество суммируемых членов.
Числовая последовательность, каждый член которой, начиная со второго, равен предыдущему, умноженному на постоянное для этой последовательности число q , называется геометрической прогрессией. Число q называется знаменателем прогрессии. Любой член геометрической прогрессии вычисляется по формуле: bn = b1 q n - 1 .
Сумма n первых членов геометрической прогрессии вычисляется по формуле:
Бесконечно убывающая геометрическая прогрессия. Это геометрическая прогрессия, у которой | q | < 1 . Сумма членов бесконечно убывающей геометрической прогрессии вычисляется по формуле:
Суммы прогрессий

Метод итераций. Вычисление Factorial
T(n)=T(n-1)+1,
T(1)=1
T(n)=θ(g(n)), g(n)=?
T(n-1)=T(n-2)+1
T(n-2)=T(n-3)+1
T(n)= T(n-1)+1=
T(n-2)+1+1=
T(n-3)+1+1+1=…
Т(1) +n-1= n
T(n)=θ(n)
Асимптотическая оценка алгоритма вычисление факториала
Factorial(n) = θ(n)
Линейная зависимость скорости работы алгоритма от объема входных данных

Сортировка слиянием (merge sort) – асимптотически оптимальный алгоритм сортировки сравнением, основанный на методе декомпозиции («разделяй и властвуй», decomposition)
Требуется упорядочить заданный массив A[1..n] по неубыванию (non-decreasing order) так, чтобы
?[1] ≤ ?[2] ≤ ⋯ ≤ ?[?]
Алгоритм включает два этапа
Разделение (partition) – рекурсивное разбиение массива на меньшие подмассивы, их сортировка
Слияние (merge) – объединение упорядоченных массивов в один
Анализ рекурсивных алгоритмов. Сортировка слиянием

Разбиваем массив на две половины меньшего размера, пока размер массива больше 1
2. Рекурсивно сортируем каждую половину
3. Сливаем два отсортированных массива
Сортировка слиянием

void mergeSort (int a[], int l, int r) {
int mid; if (l < r) {
mid = (l + r)/2;
mergeSort(a, l, mid);
mergeSort(a, mid +1, r);
merge(a, l, mid, r);
}
}
Сортировка слиянием

Этап разделения

Этап слияния

Сортировка слиянием

A1: 3, 4, 6, 11 A2: 2, 5, 7, 8
A: 2 2<3
A1: 3, 4, 6, 11 A2: 5, 7, 8
A: 2, 3 3<5
A1: 4, 6, 11 A2: 5, 7, 8
A: 2, 3, 4 4<5
A1: 6, 11 A2: 5, 7, 8
A: 2, 3, 4, 5 5<6
A1: 6, 11 A2: 7, 8
A: 2, 3, 4, 5, 6 6<7
A1: 11 A2: 7, 8
A: 2, 3, 4, 5, 6, 7 7<11
A1: 11 A2: 8
A: 2, 3, 4, 5, 6, 7, 8 8<11
A: 2, 3, 4, 5, 6, 7, 8, 11
Слияние упорядоченных массивов

void mergeSort (int a[], int l, int r) { T(n)
int mid; 1 if (l < r) { 1
mid = (l + r)/2; 1
mergeSort(a, l, mid); T(n/2)
mergeSort(a, mid +1, r); T(n/2)
merge(a, l, mid, r); n
}
}
Анализ рекурсивных алгоритмов. Сортировка слиянием

Рекуррентное соотношение - это соотношение содержащее функцию Т(n) в левой и правой части выражения
Дерево рекурсии: T(n) = 2*T(n/2) +cn, с –const, c>0
Рекуррентное соотношение

Дерево рекурсии для
T(n) = 2*T(n/2) + cn
Дерево рекурсии

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

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

T (n) = Θ(n · log2(n))
Дерево рекурсии

Сравнение алгоритмов сортировки
Сортировка вставками – Θ(n2)
Сортировка слиянием - Θ(n * log2(n))

Дерево рекурсии
Дерево рекурсии - графический метод, который отображает разворачивание рекуррентного соотношения в систему рекурсивных вызовов
T(n)=2T(n/2)+n2
n2
T(n/2) T(n/2)

Дерево рекурсии
T(n)=2T(n/2)+n2
n2
(n/2)2 (n/2)2
T(n/4) T(n/4) T(n/4) T(n/4)

Дерево рекурсии
T(n)=2T(n/2)+n2
n2 n2
(n/2)2 (n/2)2 log n (1/2)*n2
(n/4)2 (n/4)2 (n/4)2 (n/4)2 (1/4)*n2
T(n)=θ(n2)

Сумма: по уровням
(1 + 1/2 + 1/4 + . . . + 1/2k + . . .)n2 =?
b1=1, q= 1/2
T(n)=θ(n2)
Подсчет оценки

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

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

Сумма: по уровням
(1 + 5/16 + 25/256 + . . . + 5k/16k + . . .)n2 =?
b1=1, q= 5/16
T(n)=θ(n2)
Подсчет оценки

T (n) = aT (n/b) + f (n), a ≥ 1, b > 1, f (n) − (f (n) > 0, n > n0)
Основная теорема о рекуррентных оценках

1.
T (n) = 4T (n/2) + n
a=4, b=2, f(n)=n
При ε=1 выполняется условие для первого случая теоремы
T(n)=θ(n2)
Подсчет оценки

2.
T (n) = 4T (n/2) + n2
a=4, b=2, f(n)=n2
второй случай теоремы
T(n)=θ(n2*log n)
Подсчет оценки