Анализ рекурсивных алгоритмов немного отличается от анализа итеративных алгоритмов, он не является таким прямым. Обычно, нетрудно представить временную сложность рекурсивного алгоритма в виде рекуррентного уравнения. Решая рекуррентное уравнение мы и находим временную сложность алгоритма. В этой главе будут рассмотрены основные методы решения рекуррентных уравнений.
Решение рекуррентных уравнений используя индукцию
Расммотрим простешую реализацию алгоритма вычисляющего факториал заданного числа. Рекурсивнный алгоритм выглядит следующим образом
int fact (int n)
{
if (n == 0)
return 1;
else
return n * fact (n - 1);
}
Чтобы получить представление об эффективности этого алгоритма, давайте определим, сколько раз эта функция выполняет инструкцию умножения для каждого значения $$n$$. Для заданного n число выполненных умножений равно числу вычислений $$fact(n−1)$$ плюс одно умножение, на умножение $$n fact(n−1)$$. Пусть $$T(n)$$ - число умножений необходимых для вычисления $$n!$$, тогда получим уравнение
$$ T(n)=T(n−1)+1
$$
Такое уравнение называется рекуррентным уравнением, поскольку значение функции для $$n$$ - $$T(n)$$ задается через значение функции для меньшего аргумента $$n−1$$. Рекуррентное уравнение само по себе определеяет множество функций, то есть решением такого уравнения является множество функций. Для единственности решения необходимо начальное условие, в нашем случае $$T(0)=0$$, поскольку $$0!=1$$ и не требуется операций умножения. Последовательно вычисляя значения для $$n=1,2,3,4$$ имеем
$$T(1)=T(1−1)+1=1, \ T(2)=T(2−1)+1=T(1)+1=1+1=2 \ T(3)=T(3−1)+1=T(2)+1=2+1=3 \ T(4)=T(4−1)+1=T(3)+1=3+1=4$$
Продолжая далее, можно сделать предположение, что решением рекуррентного уравнения является $$T(n)=n$$. Для доказательства воспользуемся принципом математической индукции.
- База индукции. Очевидно $$T(0)=0$$.
- Индукционное предположение. Пусть формула верна, для $$n=k$$, то есть $$T(k)=k$$.
- Индукционный переход. Покажем, что верно равенство $$T(k+1)=k+1$$. Имеем,
$$ T(k+1)=T((k+1)−1)+1=T(k)+1=k+1
$$
Таким образом мы закончили наше доказательство и $$T(n)=n$$ верное решение.
Итак, для анализа рекурсивного алгоритма необходимо сделать два шага. Первый шаг - определить рекуррентное уравнение, второй шаг - решить его.
Рассмотрим еще несколько примеров.
$$T(n) = T(n/2) + 1, T(1) = 1$$, где $$n$$ - степень двойки
Последовательно вычисляя значения для $$n=2,4,8,16$$ имеем
$$ T(2) = T(2/2) + 1 = T(1) + 1 = 1 + 1 = 2 \ T(4) = T(4/2) + 1 = T(2) + 1 = 2 + 1 = 3 \ T(8) = T(8/2) + 1 = T(4) + 1 = 3 + 1 = 4 \ T(16) = T(16/2) + 1 = T(8) + 1 = 4 + 1 = 5
$$
Можно предположить, что $$T(n) = \log_2 n + 1$$. Докажем это утверждение с помощью принципа математической индукции.
База индукции. Очевидно $$T(1)=1 = \log_2 1 + 1$$.
Индукционное предположение. Пусть формула верна, для $$n=k$$, то есть $$T(k)=\log_2 k + 1$$.
Индукционный переход. Покажем, что верно равенство $$T(2k)=\log_2 (2k) + 1$$. Имеем,
$$ T(2k)=T(2k / 2) + 1=T(k) + 1 = \log_2 k + 1 + 1 = \log_2 k + \log_2 2 + 1 = \log_2 (2k) + 1
$$
Пусть требуется решить рекуррентное уравнение
$$T(n) = 7T(n/2), T(1) = 1$$, где $$n$$ - степень двойки
Последовательно вычисляя значения для $$n=2,4,8,16$$ имеем
$$T(2) = 7T(2/2) = 7T(1) = 7 \T(4) = 7T(4/2) = 7T(2) = 7^2 \ T(8) = 7T(8/2) = 7T(4) = 7^3 \ T(16) = 7T(16/2) = 7T(8) = 7^4$$
Делаем предположение, что $$T(n) = 7^{\log_2 n}$$.
- База индукции. Очевидно $$T(1)= 1 = 7 ^ {\log_2 1}$$.
- Индукционное предположение. Пусть формула верна, для $$n=k$$, то есть $$T(k)=7^{\log_2 k}$$.
- Индукционный переход. Покажем, что верно равенство $$T(2k)=7^{\log_2 (2k)}$$. Имеем,
$$ T(2k)= 7 T(2k / 2)=7T(k) = 7 \cdot 7^{\log_2 k} = 7^{\log_2 k +1} = 7^{\log_2 (2k)}
$$
Нужно понимать, что математическя индукция позволяет лишь проверить верность предположение. Она ничего не говорит по поводу того в какой форме искать решение. Рассмотрим следующим пример,
Пусть требуется решить рекуррентное уравнение
$$T(n) = 2T(n/2) + n - 1, T(1) = 0$$, где $$n$$ - степень двойки
Последовательно вычисляя значения для $$n = 2, 4, 8, 16$$ имеем
$$ T(2) = 2T(2/2) + 2 - 1 = 2T(1) + 1 = 1\ T(4) = 2T(4/2) + 4 - 1 = 2T(2) + 3 = 5\ T(8) = 2T(8/2) + 8 - 1 = 2T(4) + 7 = 17\ T(16) = 2T(16/2) + 16 -1 = 2T(8) + 15 = 49
$$
Как видим, не существует очевидного решения, предложенного этими значениями. Как упоминалось ранее, индукция может только проверить правильность решения. Поскольку у нас нет решения для кандидата, мы не можем использовать индукцию для решения этой задачи. Однако его можно решить, используя технику, обсуждаемую в следующем разделе.
Однородные линейные рекуррентные уравнения
Уравнение $$a0t_n + a_1t{n-1} + \ldots + ak t{n-k} = 0$$, где $$k$$ и $$a_i$$ - константы называются однородными линейными рекуррентными уравнениями с постоянными коэффициенатми.
Уравнение называется линейным поскольку каждое слагаемое $$ti$$ входит в первой степени. То есть в уравнении не может присутсвовать слагаемые вида $$t_i^2$$ или $$t{n-i} \cdot t{n-j}$$. Помимо этого не должно быть индексов вида $$c(n-i)$$ где $$c$$ - некоторая положительная константа отличная от 1. К примеру, следующие слагаемые недопустимы $$t{i/2}$$, $$t_{7(n-2)}$$ и т.д. Уравнение называется однородным поскольку линейная комбинация слагаемых равна нулю. Следующие уравнения являются однородными линейными
$$ 7tn - 3t{n-1} = 0 \ 6tn-5t{n-1}+8t{n-2} = 0 \ 8t_n - 4t{n-3} = 0 \ tn - t{n-1} - t_{n-2} = 0$$
Последние уравнение при начальных условиях $$t_0 = 0, t_1 =1$$ задает последовательность чисел Фибоначчи.
Пусть требуется решить уравнение $$tn - 5t{n-1}+6t_{n-2} = 0, t_0 = 0, t_1 = 1$$.
Подставим вместо $$t_n=r^n$$, получим
$$tn - 5t{n-1}+6t_{n-2} = r^n-5r^{n-1}+6r^{n-2}$$. Таким образом, $$t_n = r^n$$ является решением если $$r$$ является корнем уравнения
$$ r^n-5r^{n-1}+6r^{n-2} = 0
$$
Запишем уравнение в виде $$r^n-5r^{n-1}+6r^{n-2} = r^{n-2} (r^2-5r + 6) = 0$$. Корнями последнего уравнения являются числа $$r=0, r=2, r=3$$.
Таким образом $$t_n = 0, t_n = 2^n, t_n = 3^n$$ являются решением данного рекуррентного уравнения. Более того, легко показать, что поскольку $$t_n = 2^n, t_n = 3^n$$ являются решениями, то и $$t_n = c_1 \cdot 2^n + c_2 \cdot 3^n$$ где $$c_1, c_2$$ некоторое константы так же является решением. (Доказать это и показать его единственность). Для нахождения констант $$c_1$$и $$c_2$$, воспользуемся начальными условиями $$t_0 = 0, \, t_1 = 1$$. Имеем систему
$$ \left{ \begin{aligned} &c_1 + c_2 = 0 \ &3c_1 + 2c_2 = 0\ \end{aligned} \right. \iff \left{ \begin{aligned} &c_1 = 1 \ &c_2 = -1\ \end{aligned} \right.
$$
Итак, решение уравнения имеет вид $$t_n = 1 \cdot 3^n - 1\cdot 2^n = 3^n - 2^n$$.
Меняя начальные условия, будем иметь разные решения. Например, при $$t_0 = 1, \, t_1 = 2$$, получим $$c_0=0, \, c_1 = 1$$ откуда находим $$t_n = 2^n$$.
Определение. Уравнение $$a0r^k + a_1 r^{k-1} + \ldots + a_kr^0 = 0$$ называется характеристическим уравнением для однородного рекуррентного уравнения $$a_0 t_n + a_1 t{n-1}+\ldots + akt{n-k} = 0$$.
Например, для уравнения $$5tn - 7t{n-1} + 6t_{n-2}=0$$ характеристическое уравнение имеет вид $$5r^2-7r+6=0$$.
Теорема 1. Пусть дано однородное линейное уравнение с постоянными коэффициентами $$a0 t_n + a_1 t{n-1}+\ldots + akt{n-k} = 0$$. Если характеристическое уравнение $$a_0r^k + a_1 r^{k-1} + \ldots + a_kr^0 = 0$$ имеет $$k$$ различных действительных корней $$r_1, \, r_2, \ldots, r_k$$ то общее решение такого уравнения имеет вид
$$ t_n = c_1r_1^n+c_2r_2^n+\ldots+c_kr_k^n
$$
Для нахождения констант $$c_1, c_2, \ldots c_k$$ необходимо использовать начальные условия. Для нахождения $$k$$ констант потребуется $$k$$ начальных условий.
Рассмотрим несколько примеров.
Пример 1. Пусть требуется решить уравнение $$tn = 3t{n-1} + 4 t_{n-2}, \, t_0=0, \, t_1 = 1$$.
Составляем характеристическое уравнение $$r^2-3r-4 = 0$$. Корни характеристического уравнения равны $$r=4, \, r=-1$$. Отсда находим общее решение в виде $$t_n = c_1 4^n + c_2 (-1)^n$$. Для нахождения констант решим ситему уравнений
$$ \left{ \begin{aligned} &c_1 + c_2 = 0 \ &4c_1 - c_2 = 0\ \end{aligned} \right. \iff \left{ \begin{aligned} &c_1 = \dfrac{1}{5} \ &c_2 = -\dfrac{1}{5}\ \end{aligned} \right.
$$
Итак, $$t_n = \dfrac{1}{5} 4^n - \dfrac{1}{5} (-1)^n$$ - решение рекуррентного уравнения.
Пример 2. Пусть требуется решить уравнение $$tn = t{n-1} + t_{n-2}, \, t_0= 0, \, t_1 = 1$$ задащее последовательность чисел Фибоначчи.
Для применения Теоремы 1 требовалось, чтобы характеристическое уравнение имело ровно $$k$$ различных корней. Что делать если характеристическое уравнение имеет вид $$(r-1)(r-2)^3=0 ?$$ Корень $$r=2$$ называется корнем кратности 3. Следущая теорема позволяет решать рекуррентные уравнения, чьи характеристические уравнения имет кратные корни.
Теорема 2. Пусть $$r$$ - корень кратности $$m$$ характеристического уравнения для линейного однородного рекуррентного уравнения с постоянными коэффициентами. Тогда общее решение имеет вид
$$ tn = c_1 r^n + c_2 nr^n + c_3n^2r^n + \ldots + c{m-1}n^{m-1}r^n
$$
Рассмотрим несколько примеров.
Пример 3. Пусть требуется решить уравнение $$tn = 7t{n-1} + 15 t{n-2} - 9{n-3}, \, t_0=0, \, t_1 = 1, \, t_2 = 2$$.
Характеристическое уравнение имеет вид
$$ r^3-7r^2+15r-9 = 0 \iff (r-1)(r-3)^2 = 0
$$
Корнями характеристического уравнения являтся числа $$r=1$$ и $$r=3$$ (корень кратности 2). Отсюда находим общее решение в виде $$t_n = c_1 1^n + c_2 3^n + c_3 n 3^n$$. Для нахождения констант решим ситему уравнений
$$ \left{ \begin{aligned} &c_1 + c_2 = 0 \ &c_1 + 3c_2 + 3c_3 = 1\ &c_1 + 9c_2+18c_3 = 2\ \end{aligned} \right. \iff \left{ \begin{aligned} &c_1 = -1 \ &c_2 = 1 \ &c_3 = \dfrac{1}{3}\ \end{aligned} \right.
$$
Итак, $$t_n = -1 \cdot 1^n + 1 \cdot 3^n - \dfrac{1}{3} \cdot n 3^{n-1} = -1 + 3^n - n 3^{n-1}$$ - решение рекуррентного уравнения.
Пример 4. Пусть требуется решить уравнение $$tn = 5t{n-1} - 7 t{n-2} + 3{n-3}, \, t_0=1, \, t_1 = 2, \, t_2 = 3$$.
В случае если характеристическое уравнение имеет комплексные корни придется использовать тригонометрическу формулу комплексного числа.
Пример 5. Пусть требуется решить уравнение $$tn = 2t{n-1} - 2 t_{n-2}, \, t_0=1, \, t_1 = 3$$.
Характеристическое уравнение $$r^2-2r+2 = 0$$ имеет два сопряженных комплексных числа $$r_1=1+i, \, r_2 = 1-i$$. В тригонометрической форме числа имет вид
$$ r_1 = \sqrt{2} \left(\cos \dfrac{\pi}{4} + i \sin \dfrac{\pi}{4} \right) \ r_2 = \sqrt{2} \left(\cos \dfrac{\pi}{4} - i \sin \dfrac{\pi}{4} \right)
$$
Находим общее решение по формуле
$$ t_n = c_1 \cdot r_1^n + c_2 \cdot r_2^n = (\sqrt{2})^n \left(c_1\left(\cos \dfrac{\pi}{4} + i \sin \dfrac{\pi}{4} \right)^n + c_2 \left(\cos \dfrac{\pi}{4} - i \sin \dfrac{\pi}{4} \right)^n \right) = (\sqrt{2})^n \left(c_1 \cos n \dfrac{\pi}{4} + c_2 \sin n \dfrac{\pi}{4} \right)
$$
Используя начальные условия находим $$c_1 = 1, \, c_2 = 2$$. Отсюда решение уравнения имеет вид
$$ t_n= (\sqrt{2})^n \left( \cos n \dfrac{\pi}{4} +2 \sin n \dfrac{\pi}{4} \right)
$$