Глава 6

Рекуррентные соотношения как средство анализа сложности алгоритмов

§ 24. Простейшие рекуррентные уравнения

Рекуррентные соотношения (уравнения и неравенства) играют суще­ственную роль в анализе алгоритмов. Наиболее известный и про­стой вид таких соотношений —это линейные рекуррентные уравне­ния с постоянными коэффициентами.

Пример 24.1. Вернемся к задаче 104, в которой надо доказать, что если к числу, первоначально равному нулю, прибавляется шаг за ша­гом по единице до достижения значения 2" - 1, n ^ 0, то в целом по­требуется 2" - п - 1 переносов единиц в старшие разряды. Коль скоро заранее указан ответ, для доказательства можно использовать индук­цию. Но формулу 2" - п - 1 можно вывести, исходя лишь из условия задачи. Обозначим через s(n) исследуемое количество переносов и за­метим, что если прибавлением единиц уже получено число 2"^-1 - 1 (на это потребуется s(n-l) переносов), то очередное прибавление единицы потребует п - 1 переносов и приведет к числу 2"^-1, двоич­ная запись которого есть 10...0 (количество нулей после единицы равно п-1). Далее в процессе достижения числа 11...1 (п единиц) потребуется еще s(n-l) переносов. Получаем рекуррентное уравне­ние s(n) = 2s(n - 1) + n - 1 или

s(n)-2s(n-l) = n-l, (24.1)

при этом s(0) = 0. Характеристическое уравнение¹, соответствующее рекуррентному уравнению (24.1), имеет вид А - 2 = 0. Общее реше­ние однородного уравнения s(n) - 2s(n - 1) = 0 есть сТ. Правую часть уравнения (24.1) можно записать в виде квазиполинома (п-1)1^п. Значение 1 не является корнем характеристического уравнения, по-

¹ О методе решения линейных рекуррентных уравнений с постоянными коэффици­ентами см. в приложении G.

§ 24. Простейшие рекуррентные уравнения

159

этому (24.1) обладает частным решением вида an + Ъ; подставляя это выражение вместо s(n) в (24.1), получаем an + Ъ - 2(а(п - 1) + Ь) = = п - 1, и, приравнивая в левой и правой частях коэффициенты при первой и нулевой степенях п, имеем а = Ъ = -1. Получаем общее ре­шение уравнения (24.1): s(n) = с2" - п - 1. Подбираем значение кон­станты с так, чтобы выполнялось s(0) = 0; для этого должно выпол­няться с • 2 - 2 = 0, т. е. с = 1. Итак, потребуется 2" - п - 1 переносов единиц в старшие разряды.

Алгоритм, который содержит прямые или косвенные (т. е. при по­средстве других алгоритмов) обращения к себе, как известно, назы­вается рекурсивным. Рекуррентные соотношения являются удобным средством анализа сложности рекурсивных алгоритмов.

В следующем примере обсуждается использование рекуррентных уравнений в анализе рекурсивных алгоритмов и указывается один неудачный вид рекурсии.

Пример 24.2. Рассмотрим построение множества V_n всех целых чисел, десятичная запись каждого из которых содержит только циф­ры 1 и 2, а сумма цифр равна заданному числу n ^ 1. Непосред­ственно видно, что Vi = {l}, У₂ = Ш,2}, У₃ = Ш1, 21,12}. В общем случае V_n является, очевидно, объединением двух непересекающихся подмножеств, в первое из которых входят все числа из V_n, оканчива­ющиеся цифрой 1, во второе — цифрой 2. Если вычеркнуть послед­нюю цифру, то при п ^ 2 первое подмножество превратится в У_п-_ъ второе — в V_n-₂. Это наблюдение приводит к рекурсивному алгорит­му V_Rec построения V_n: если п = 1 или п = 2, то результатом будет {1} или соответственно {11,2}; иначе надо найти V_n-_x (рекурсивное обращение к алгоритму) и приписать справа ко всем числам этого множества единицу, затем найти V_n-₂ (еще одно рекурсивное обра­щение) и приписать справа ко всем числам этого множества двойку, после чего построить объединение двух получившихся множеств.

Не составляет труда заметить, что алгоритм V_Rec избыточно сло­жен (о чем еще будет идти речь). Но анализ сложности часто прихо­дится проводить и для «плохих» алгоритмов — например, чтобы по­казать их практическую непригодность.

Прежде чем исследовать временную сложность этого алгоритма, установим, чему равно число v(n) элементов V_n. Мы видим, что v(l) = l, v(2) = 2, v(n)=v(n-l)+v(n-2), n = 3,4, ... Таким обра­зом, v(n) равно (п-Ы)-му числу Фибоначчи: v(n)=F_n+1. Явное вы­ражение v(n) через п можно получить, воспользовавшись формулой Бине (10.2), которая сама может быть выведена с помощью общего

160 Глава 6. Рекуррентные соотношения и сложность алгоритмов

метода решения линейных рекуррентных уравнений с постоянными коэффициентами.

Используя рекуррентные уравнения, мы можем определить ко­личество у(п) преобразований чисел при построении множества V_n по описанному алгоритму (каждое из этих преобразований состо­ит в приписывании справа к числу единицы или двойки). Мы мо­жем также определить число z(n) выполняемых операций объедине­ния множеств. Очевидно, имеет место уравнение у(п)=у(п-1) + + y(n-2) +F_n +F_n-1, которое мы перепишем в более удобном виде и добавим начальные значения:

y(n)-y(n-1)-y(n-2)=F_n+1, (24.2)

у(2) = у(1) = 0. Аналогично, имеем

z(n)-z(n-1)-z(n-2) = 1, (24.3)

z(2)=z(1) = 0.

Начнем со второго уравнения. Будем, как обычно, прибегать к обозначениям

, 1 + а/5 г 1-У5

Ф ⁼⁼ ˜ ⁼⁼ .

Непосредственно видно, что -1 является частным решением наше­го рекуррентного уравнения (это частное решение можно получить и общим методом: правая часть является квазиполиномом 1", при этом 1 не есть корень характеристического уравнения

А² - А - 1 = 0, (24.4)

и, следовательно, существует частное решение вида c1", где с — по­лином нулевой степени, т. е. константа; подстановка в (24.3) дает с = -1). Корнями уравнения (24.4) служат числа фи ˜ , входящие в формулу Бине, и общее решение уравнения (24.3) может быть запи­сано в виде z(n) = С₁ф^п + С₂ ˜^п - 1. Начальные условия z(2) = z(1) = 0 приводят нас к системе

¹⁵ "ч 2 s 1 ⁵ ~\ 2

Получаем

C1 = 4=, С₂ = - ˜=. (24.5)

а/5 а/5