Начало
Учебные материалы
Анализ алгоритмов
Анализ рекурсивного алгоритма
Алгоритм F(`n`)
// Входные данные: Целое неотрицательное число `n`
// Выходные данные: Значение `n!`
**if** `n = 0`
`quad` **return** 1
**else**
`quad` **return** `F(n-1) * n` // `(n-1)!*n`
Основной операцией этого алгоритма является умножение. Количество операций умножения `C(n)`,
выполняемых при этом в алгоритме, должно удовлетворять следующему равенству для всех `n > 0`:
`{:(C(n),=, C(n-1),+,1),(\ ,\ ,"Вычисление " F(n-1),\ ,"Умножение " F(n-1) " на " n):}`
--
Значение для `C(n)` не задано явно, т.е. в виде функции от числа `n`.
Оно выражено неявно в виде функции, значение которой зависит от значения этой же функции на предыдущем шаге алгоритма,
т.е. при `n-1`. Подобные равенства называют *рекуррентными уравнениями* или *рекуррентными соотношениями*.
Существует бесконечное множество последовательностей, являющихся решением приведенного выше рекуррентного соотношения.
Чтобы найти однозначное решение, нужно задать *начальные условия*, т.е. указать значение, с которого начинается последовательность.
Рекурсивный вызов процедуры в нашем алгоритме прекращается при `n=0` и в строке кода алгоритма, в которой задано условие завершения работы
не выполняются операции умножения. Поэтому начальное условие будет выглядеть так:
`C(0)=0`
--
`C(0)=0`
`C(n)=C(n-1)+1 " для " n>0`
Существует несколько методик решения рекуррентных отношений: метод прямой подстановки, метод обратной подстановки, решение
характеристического уравнения для линейных рекуррентных соотношений второго порядка с постоянными коэффициентами. Методом обратной подстановки получаем
`C(n)=C(n-1)+1=[C(n-2)+1]+1=C(n-2)+2=`
`=[C(n-3)+1]+2=C(n-3)+3=...=C(n-i)+i`
Осталось только применить начальные условия.
`C(n)=C(n-n)+n=C(0)+n=0+n=n`
--
Для получения `n!` можно было воспользоваться простым
циклическим алгоритмом, в котором выполнялось бы ровно столько же операций умножения.
При этом в нем не тратилось бы время на дополнительный вызов функции и не расходовалась бы дополнительная память для размещения параметров
рекурсивной функции в стеке.
--
Уменьшение на единицу: `T(n)=T(n-1)+f(n)`
`T(n)=T(0)+sum_{i=1}^(n) f(i)`
Для `f(n)=n^k`: `T(n) in Theta(n^{k+1})`
Уменьшение на постоянный множитель: `T(n)=T(n/b)+f(n)`
`T(b^k)=T(1)+sum_{i=1}^k f(b^i)`
*Правило сглаживания* позволяет применить эту формулу и для `n != b^k`
Для `f(n)=1`: `T(n)=T(1)+ |~ log_b n ~|`
Для `f(n)=n`: `T(n)=T(1)+ (b*(n-1))/(b-1)`
--
##### Общий план анализа эффективности рекурсивных алгоритмов
1. Выберите параметр (или параметры), по которому будет оцениваться
размер входных данных алгоритма.
2. Определите основную операцию алгоритма.
3. Проверьте, зависит ли число выполняемых основных операций только
от размера входных данных. Если оно зависит и от других факторов,
рассмотрите при необходимости, как меняется эффективность
алгоритма для наихудшего, среднего и наилучшего случаев.
4. Составьте рекуррентное уравнение, выражающее количество
выполняемых основных операций алгоритма, и укажите соответствующие
начальные условия.
5. Найдите решение рекуррентного уравнения или, если это невозможно,
определите хотя бы его порядок роста.
--
Рассмотрим головоломку Ханойские башни. Суть ее состоит
в том, что у нас есть `n` дисков разного диаметра и три колышка.
В исходном состоянии все диски надеты на первый колышек и упорядочены по диаметру,
т.е. самый большой диск находится внизу стопки, а самый малый -- вверху. Цель задачи --
перенести все диски на третий колышек, используя при необходимости в качестве вспомогательного
второй колышек. За один раз можно перенести только один диск, и кроме того,
нельзя помещать диск большего диаметра на диск меньшего диаметра.
--
Чтобы перенести `n >1` дисков с колышка A на C, используя B в качестве вспомогательного, сначала нужно
рекурсивно перенести `n—1`
дисков с колышка A на B, используя при этом колышек C в качестве вспомогательного.
После этого мы должны перенести наибольший диск непосредственно с колышка A на C и, наконец,
рекурсивно перенести `n-1` дисков со колышка B на C, используя при
этом колышек A в качестве вспомогательного.
Естественно, что при `n=1`,
мы можем непосредственно перенести единственный диск с колышка A на C.
Размер входных данных нужно оценивать по количеству дисков `n`, а основной операцией алгоритма будет перенос одного диска.
--
Получается рекуррентное соотношение
`C(n) = C(n-1) + 1 + C(n-1)=2*C(n-1)+1`
при начальном условии
`C(1)=1`
Используем метод обратной подстановки:
`C(n)=2*C(n-1)+1=2*[2*C(n-2)+1]+1=4*C(n-2)+2+1=`
`=4*[2*C(n-3)+1]+2+1=8*C(n-3)+4+2+1=`
`=2^i C(n-i)+sum_{j=0}^{i-1} 2^j=2^i C(n-i)+2^i-1`
Применяем начальные условия.
`C(n)=2^{n-1} C(n-(n-1))+2^{n-1}-1=2^{n-1} C(1)+2^{n-1}-1=`
`=2*2^{n-1}-1=2^n-1`
--
Данный алгоритм является самым эффективным среди всех возможных алгоритмов решения нашей задачи.
Сложность присуща самой задаче.
Рекурсивные алгоритмы следует использовать очень осторожно,
поскольку часто за их внешней компактностью может скрывается неэффективность, что рассматривается далее.
--
Последовательность чисел Фибоначчи определяется так:
`F(0)=0`
`F(1)=1`
`F(n)=F(n-1)+F(n-2) " для " n>1`
Наихудший случай входных данных для алгоритма НОД соответствует последовательным
числам Фибоначчи -- количество итераций будет равно номеру элемента в последовательности.
Алгоритм F(`n`)
// Входные данные: Целое неотрицательное число `n`
// Выходные данные: `n`-й элемент последовательности Фибоначчи
**if** `n <= 1`
`quad` **return** `n`
**else**
`quad` **return** `F(n-1) + F(n-2)`
--
Основной операцией этого алгоритма является сложение, при этом
`C(n)=C(n-1)+C(n-2)+1` с начальными условиями `C(0)=0, C(1)=0`
Рассмотрим сначала получение явной формулы для `n`-го элемента последовательности чисел Фибоначчи.
*Однородное линейное рекуррентное уравнение второго порядка* с постоянными коэффициентами
`a x(n) + b x(n -1) + c х(n -2) = 0`
имеет общее решение вида
`x(n)= alpha r_1^n + beta r_2^n`, где `r_1, r_2` -- корни характеристического уравнения `a r^2+b r+ c =0`,
коэффициенты `alpha, beta` вычисляются по начальным условиям.
Если `r=r_1=r_2`, то `x(n)= alpha r^n + beta n r^n`.
--
Перепишем рекуррентное уравнение следующим образом:
`F(n) -F (n -1) -F (n -2) = 0`
Его характеристическое уравнение имеет вид:
`r^2 -r-1 = 0`.
`D=1-4*(-1)=5`
Корни `r_1=(1+sqrt 5)//2`, `r_2=(1-sqrt 5)//2`
`F(0)=alpha+beta=0`
`F(1)=alpha (1+sqrt 5)//2+ beta (1-sqrt 5)//2=1`
`beta=-alpha`, `alpha=1/(sqrt 5)`
--
Первый корень `(1+sqrt 5)//2` -- это число `Phi`, которое называют *золотым сечением*
(деление отрезка точкой на две части так, что большая часть относится к меньшей, как весь отрезок к большей),
второй корень можно записать как `1-Phi` или `-1/Phi`.
`F(n)=1/(sqrt 5) (Phi^n - (-1/Phi)^n)`
Функция `F(n)` имеет экспоненциальный порядок роста: `F(n) in Theta(Phi^n)`.
--
В рекуррентном уравнении `C(n) - C(n - 1) - C(n -2)=1` правая часть не равна нулю.
Можно привести *неоднородное рекуррентное уравнение* к однородному, переписав выражение:
`[C(n)+1] - [C(n - 1)+1] - [C(n -2)+1]=0`
Обозначив `B(n) = C(n) + 1`,
получаем уравнение `B(n)-B(n-1)-B(n-2)=0` с начальными условиями `B(0)=1, B(1)=1`.
`B(n)` -- это та же рекурсия, что и `F(n)`, за исключением того, что она начинается
с двух единиц, т.е. опережает `F(n)` на один шаг. Поэтому `B(n) = F (n + 1)`.
`C(n)=B(n)-1=F(n+1)-1 in Theta(Phi^n)`
--
Причиной неэффективности рекурсивного алгоритма является то, что функция с одним и тем же значением
аргумента вызывается по несколько раз.
Если числа Фибоначчи вычислять последовательно одно за другим в цикле, то получится намного более эффективный алгоритм.
Алгоритм Fib(`n`)
// Входные данные: Целое неотрицательное число `n`
// Выходные данные: `n`-й элемент последовательности Фибоначчи
`F[0] larr 0`
`F[1] larr 1`
**for** `i in [2...n]` **do**
`quad F[i] larr F[i -1] + F[i -2]`
**return** `F[n]`
--
В этом алгоритме выполняется `n-1` операция сложения.
Следовательно, алгоритм является линейным. Можно
избежать использования дополнительного массива для хранения всех предыдущих
элементов последовательности Фибоначчи: для выполнения задачи достаточно
сохранять только два значения.
Третий способ вычисления `n`-го элемента последовательности чисел
Фибоначчи заключается в использовании выведенной формулы, но на правильность конечного результата может повлиять точность вычислений.
--
Существует алгоритм со временем работы `O(log n)`, в котором используются только целые числа.
В нем используется равенство
`[[F(n-1), F(n)],[F(n), F(n+1)]]=[[0,1],[1,1]]^n`
Возведение матрицы в степень выполняется за `O(log n)` операций.
---
##### Задания для практики
1. \
а) Разработайте рекурсивный алгоритм вычисления значения `2^n` для произвольного неотрицательного целого числа `n`, который основан на формуле `2^n = 2^{n-1} + 2^{n-1}`.\
б) Постройте рекуррентное уравнение для количества операций сложения, выполняемых в алгоритме, и найдите его решение.\
в) Изобразите дерево рекурсивных вызовов для этого алгоритма и подсчитайте количество вызовов рекурсивной функции, выполняемых алгоритмом.\
г) Можно ли сказать, что это хороший алгоритм для решения поставленной задачи?
2. Рассмотрим следующий рекурсивный алгоритм
Алгоритм Min1(`A`)
// Входные данные: массив чисел `A[0...n-1]`
**if** `n = 1`
`quad` **return** `A[0]`
**else**
`quad` `m larr "Min1"(A[0..n-2])`
`quad` **if** `m <= A[n-1]`
`quad quad` **return** `m`
`quad` **else**
`quad quad` **return** `A[n-1]`
a) Что вычисляется этим алгоритмом?\
б) Назовите основную операцию алгоритма.\
в) Постройте рекуррентное отношение для количества выполнений основной операции и найдите её решение.
3. Рассмотрим следующий рекурсивный алгоритм
Алгоритм Min2(`A,l,r`)
// Входные данные: массив чисел `A[0...n-1]`
**if** `l = r`
`quad` **return** `A[l]`
**else**
`quad` `a larr "Min2"(A,l,|__ (l+r)//2 __|)`
`quad` `b larr "Min2"(A,|__ (l+r)//2 __|+1,r)`
`quad` **if** `a <= b`
`quad quad` **return** `a`
`quad` **else**
`quad quad` **return** `b`
а) Постройте рекуррентное отношение для количества выполнений основной операции и найдите её решение.
