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

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

Пример 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) = 2 s (n - 1) + n - 1 или

s (n)-2 s (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. Простейшие рекуррентные уравнения

этому (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. Непосред­ственно видно, что V i = {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)

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

¹⁵ "ч 2 s 1 ⁵ ~\ 2

Получаем

C 1 = 4=, С₂ = - ˜=. (24.5)

а/ 5 а/ 5

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

Таким образом, z{n) = F_n+1 - 1. Отсюда следует ряд асимптотических формул:

z (n) = -j=0 ^{n +1} + O (l), z (n) ~ -±=ф^п+1, z{n) = Q{<bⁿ) (24.6)

V5 V5

и т.д. Обратимся теперь к (24.2). Характеристическим уравнением здесь вновь является (24.4). Поскольку F_n+1 = с_гф^п + с₂ф^п, где с_ъс₂ — полиномы нулевой степени, то правая часть уравнения (24.2) явля­ется суммой двух квазиполиномов, и для нахождения интересующе­го нас решения может быть привлечен общий метод, в результате чего получится формула вида у{п) = р_г{п)ф^п + р₂{п)ф^п, где, в силу того, что ф и ф являются корнями кратности 1 характеристическо­го уравнения, а также того, что с_ъс₂ф0, степени полиномов р_г{п) и р₂{п) равны 1. Это показывает, что у{п) = С_гф^п+ С₂ф^п+ р_г{п)ф^п + + р₂{п)ф^п = q₁(n)ф^п + q₂{n)ф^п при соответствующем выборе полино­мов q i(n), q ₂(n) первой степени. Можно было бы найти эти полино­мы, но даже не делая этого, а просто принимая во внимание, что степень q₁(n) равна 1, получаем

у(п) = в(пф"). (24.7)

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

С помощью рекуррентных уравнений мы получаем информацию о вычислительной сложности рекурсивного алгоритма. Правда, дело не всегда обстоит просто,—иногда возникают уравнения с перемен­ными коэффициентами или нелинейные уравнения и неравенства, и об этом мы еще будем говорить. Тем не менее, сам метод исследо­вания сложности рекурсивных алгоритмов с помощью рекуррентных уравнений выглядит очень естественно.

Задержимся на формулах (24.6), (24.7). Если бы построение мно­жества V_n при п > 2 разворачивалось не по алгоритму V _Rec, а несколь­ко иначе, то затрат было бы существенно меньше. Можно находить шаг за шагом множества V₁,V₂,V₃,... до появления интересующего нас V_n, при этом каждое V_k, к = 3, 4,..., п, строится исходя из уже име­ющихся множеств V_k2 и У_кг. Или же можно организовать рекурсию

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

для вычисления пары Р_п = (V_n, V_n-₁) так, чтобы при вычислении Р_п исходя из Р_п-₁ множество V_n-₁ просто переходило бы из пары в пару. Будем использовать обозначения у*(п) и z*(n) для количества преоб­разований чисел и соответственно для количества объединений мно­жеств, затрачиваемых при нахождении (V_n, V_n -₁). При п>2 имеем y *(n) = y *(n -1)+ F_n + F „-1. Перепишем уравнение в более удобном виде и добавим начальное значение:

y *(n)- y *(n -1) = F_{n +1}, (24.8)

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

z *(n)- z *(n -1) = 1, (24.9)

z *(1) = 0. Легко получаем z*(n) = n- 2 для п^2 и у*(п) = в(ф").

Причина избыточной сложности первого из рассмотренных алго­ритмов ясна. Построение V_n требует вычисления У_п-₁ и V_n-₂, а У_п-₁ в свою очередь потребует построения V_n-₂ и V_n-₃. Таким образом, да­же не прослеживая ход построений слишком далеко, мы видим, что требуются два независимых построения множества V_n-₂, при этом по­строение V_n-₂ по тем же причинам будет производиться не лучшим образом.

Пример 24.3. Достаточно ясно, что при к > 2 рекурсия вида

Y_n = U(Y_n-₁,...,Y_n-_k) (24.10)

(например, с заданными У₀,У ₁ ,...,У_к-₁) заслуживает еще меньше до­верия, чем при к = 2, коль скоро эта рекурсия предписывает неза­висимое вычисление Y_n-1,Y_n-2,...,Y_n-k; при этом не важно, являются ли Y_t числами, множествами или же какими-то другими объектами. Нахождение Y_n с помощью простейшего циклического алгоритма по­требует п-к + 1 обращений к U. Если при рекурсивном нахождении их требуется у(п), то

у(п) - у(п - 1) -... - у(п - к) = 1, (24.11)

у(0) = у(1) =... = у(к - 1) = 0. Можно найти асимптотику у(п), не решая полностью рекуррентного уравнения (24.11), и получить сле­дующее предложение.

Предложение 24.1. Пусть рекурсивный алгоритм организован по схеме (24.10), пусть к ^ 2 и пусть для получения значения функции U необходимы значения всех ее к аргументов. Тогда количество вычис­лений значений этой функции при нахождении Y_n есть Q (aⁿ_k), и а_к

удовлетворяет условию 2-^а_к<2, к = 2,3,

§ 25. Об одном классе нелинейных рекуррентных соотношений 163

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

A^fc-A^fc-1-...-A-l = 0,

к = 2,3,... Эти уравнения являются характеристическими для рекур­рентных уравнений (24.11).

§ 25. Об одном классе нелинейных рекуррентных соотношений

Одним из источников появления рекурсии в алгоритмах служит при­влечение стратегии «разделяй и властвуй»: вычислительная задача с размером входа п разбивается на s > 1 одноименных задач, раз­мер входа любой из которых примерно равен n/s («разделяй»); эти задачи решаются рекурсивно, т. е. с применением этой же страте­гии, а затем полученные решения соединяются в решение исходной задачи («властвуй»). Для входов маленьких размеров — как прави­ло, 0 или 1—задачи решаются каким-то простым способом, без ре­курсии. При анализе сложности таких алгоритмов возникают специ­фические нелинейные рекуррентные соотношения в виде уравнений и неравенств. В общем случае такие соотношения довольно трудны для решения, но для многих конкретных задач удается исследовать сложность алгоритмов сведением рекуррентных соотношений к хоро­шо изученным линейным рекуррентным уравнениям первого порядка с постоянными коэффициентами и квазиполиномиальными правыми частями.

Пример 25.1. Обратимся к сортировке слияниями в ее рекурсив­ном варианте и исследуем ее сложность Г_ш(п) по числу сравнений (п —длина массива). Функция T _MS(n) подчиняется рекуррентному неравенству

(О, если п = 1,

Г\п\Л ГГп1Л (25.1)

?MS (\~п \ +?MS (\~п \ + ^п - 1 > если П>1.

В самом деле, для любого массива длины п > 1 сортировка первых его [|J элементов потребует не более ^MsQfJ) сравнений (так как

T_MS( тМ) —это максимальное число сравнений, которое может по­требоваться рассматриваемой сортировке при работе с массивом дли­ны тН); аналогично, сортировка последних ^ элементов потре-

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

бует не более, чем Г_М8(|"|"|) сравнений, а слияние потребует срав­нений в количестве, не превосходящем ^ + ^-1 = п-1.В лю­бом, а значит, и в худшем случае потребуется не более T_MS( Ц) +

+ Tms (\l]) + ^п ~ ^г сравнений.

Рекуррентные неравенства, схожие с неравенством (25.1), харак­терны для многих алгоритмов, построенных на стратегии «разделяй и властвуй». Мы прервем на некоторое время рассмотрение этого примера и обсудим общую ситуацию с неравенствами возникающе­го типа.

Предложение 25.1. Пусть вещественная функция f натурального аргумента удовлетворяет неравенству

(

и, если п= 1,

<Ш) + .*(Ш) + *м, »„„ >!, (²⁵. ²)

/(n)^ t ([log₂ n l), (25.3) где и, если к = 0, (v + w) t (fc-l)+(^(2^fc), еслик>0.

«*) = "' ™= ^>(₂₅.4)

где u,v,w — неотрицательные вещественные числа, причем v +w ^ 1, а функция у —неотрицательная неубывающая. Тогда

Доказательство. Установим прежде всего, что вещественная функция F натурального аргумента, удовлетворяющая равенству

(и, если п = 1, Г\п\\ ГГп1\ ___ (25.5)

vF f + wF f +У^> еслип>1,

является неубывающей, т. е. при п ^ 2 выполнено

F (n)^ F (n -l). (25.6)

Проведем индукцию по п. При п = 2 неравенство выполнено, так как

F (2) = (v + w) u + (^(2)^ u = F (l).

Пусть п > 2 и неравенство (25.6) выполнено для 2, 3,...,п-1; дока­жем, что тогда оно верно и для п. Воспользуемся тем, что при п > 2

§ 25. Об одном классе нелинейных рекуррентных соотношений 165

Имеем

F (n)= vF ₂ +_w f ₂ +<p(ri)2

>vF^lL21 +wF^{IL -}₂ ~ +4> (n- 1) =F(n-1).

Неравенство (25.6) доказано.

Аналогичным образом по индукции докажем, что

f(n)^F(n) (25.7)

для п=г 1. Очевидно, /(1) ^ u = F (1). Пусть п> 1 и неравенство (25.7) выполнено для 1, 2,...,п- 1; докажем, что тогда оно верно и для п. В силу (25.2) мы имеем при п > 1

и так как при п > 1 выполняются неравенства ₂k n -1 и 2 ^ ^ п - 1, то по предположению индукции

^V^Q₂J) +^М^(Т₂1) +⁽/>(")^ v ⁱ⁷Q₂J) + wF ([₂l) + ¥>("). (25.9)

Правая часть последнего неравенства есть F (n). Это доказывает (25.7).

Свойства (25.6), (25.7) дают нам

/(n) ^ F (n) ^ F (2^{гlog2 n l}) (25.10)

для п^1. Исследуем функцию t (fc) = F (2^fc), fc = 0,1,... В силу (25.5)

F (2^fc) =

и, если к = 0,

(v + w) F (2^fc-¹) + ^(2^fc), если)с > 0,

и, следовательно, t (fc) удовлетворяет линейному рекуррентному урав­
нению (25.4). Отсюда и из (25.10) следует требуемое. □

Определение 25.1. Рекуррентное уравнение (25.4), включающее в себя начальное условие £(0) = и, мы назовем уравнением, ассоцииро­ванным с рекуррентным неравенством (25.2).

Если u,v,Lp(n) удовлетворяют условиям, сформулированным в предложении 25.1, то решение ассоциированного уравнения — неот­рицательная функция (см. задачу 125).

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

Продолжение примера 25.1. Уравнением, ассоциированным с (25.1), будет

t k = 1°' _k если k = 0' (25.11)

2 t (k -l)+2-l, если k> 0.

Отвлекаясь временно от начального значения t (0) = 0, мы замечаем, что правая часть в

t{k)-2t{k-l) = 2^k-l (25.12)

является суммой квазиполиномов 2^k и —1; первый из них, т.е. 2^k, интересен тем, что 2 является корнем характеристического уравне­ния А - 2 = 0, и поэтому рекуррентное уравнение t (k) - 2t{k - 1) = 2^k имеет частное решение вида p{k)2^k, где p (k)— полином первой сте­пени. Подстановка (p ₁ k + p ₀)2 ^k в рекуррентное уравнение дает

{p_гk + p₀)2^k - (p iC k - 1) + p ₀)2 ^k = 2^k,

откуда получаем, что p₁ = 1, p ₀—любое. Итак, k2^k является част­ным решением рекуррентного уравнения с правой частью 2^k. Слагае­мое -1 правой части исходного уравнения можно переписать в виде (-1) • 1^k, единица не является корнем характеристического уравне­ния, поэтому рекуррентное уравнение t (k) - 2t{k) = -1 имеет в каче­стве частного решения некоторую константу, значение которой опре­деляется без труда — это 1.

Таким образом, любое решение рекуррентного уравнения (25.12) может быть записано в виде

c2^k+k2^k + 1

с некоторым конкретным c. Из условия t (0) = 0 находим c = —1 и

t (k) = k 2 ^k -2 ^k + l. (25.13)

По предложению 25.1

T _MS(n) *S [log, n!2П°& n 1 - 2^ n 1 + 1 = = ([log₂ n l-l)2^rlo& ^{n l} + l^ ^log₂ n -2^lo^ n ⁺¹ + l = = 2 n log₂ n + 1.

Мы еще раз прервем рассмотрение примера 25.1 и сформулируем следующее предложение.

§ 25. Об одном классе нелинейных рекуррентных соотношений 167

Предложение 25.2. Пусть вещественная функция f натурального аргумента удовлетворяет неравенству

и, еслип = 1,

Q§J) +^м//([§1) +У(п), еслип>1,

где u,v,w — неотрицательные вещественные числа, причем v +w ^ 1, а функция у —неотрицательная неубывающая. Тогда

/(n)^ t (Llog₂ n J), (25.15)

где t—решение рекуррентного уравнения (25.4).

Доказательство получается заменой знака ^ на ^ в (25.7), (25.8) и (25.9), а также переходом от (25.10) к

/(n)^ F (n)^ F (2L^l0&"J).

Сохраняя введенную терминологию, рекуррентное уравнение (25.4) будем называть ассоциированным с рекуррентным неравен­ством (25.14).

Если же возникает соотношение со знаком = вместо ^ или ^, то мы можем рассматривать его как систему двух рекуррентных нера­венств (25.2), (25.14). Тогда получим оценки

t aiog₂ n |)sS/(n)sS t (riog₂ n l).

Завершим рассмотрение примера 25.1. Можно доказать (см. зада­чу 133), что для сложности по числу сравнений рекурсивной сорти­ровки слияниями выполнено

0, еслип = 1,

^Гш§ +^Гш§ +^п-1' если^п > 1>

и прийти к справедливым для всех п оценкам

(Llog₂ п\ - l)2^Ll0& ^{n J} + 1 s= Т_ш{п) s= aiog₂ п] - l)2^rl0& ^{n l} + 1. (25.17)

Для исследования сложности Т_ш (п) рекурсивной сортировки сли­яниями по числу перемещений рассмотрим рекуррентное уравнение

„0, если п = 1,

(\j) +?MS (5) + ^п> если п>1

r_MS(n)=~ _л„_п сГтЦЛ (25.18)

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

(при слиянии массивов, содержащих соответственно ^ и ^ эле­ментов, требуется ровно п перемещений элементов). Решением ассо­циированного уравнения

«в=

О, если/с = 0,

2t{k-l) + 2^k, если)с > 0,

является k2^k, что дает нам

Llog₂ n j2^"J ^ f_MS(n) ^ [log₂ п^Ч (25.19)

Пространственная сложность этой сортировки есть П(п), ибо слия­ние упорядоченных массивов выполняется с получением результата на новом месте. (Дополнительно к этому будет использоваться стек отложенных заданий.) Рассмотрение примера 25.1 закончено.

Интересно посмотреть на результаты применения разобранного метода на каком-нибудь примере, для которого мы знаем точное зна­чение сложности алгоритма, — сколь далеки будут получаемые оцен­ки от известного точного значения?

Пример 25.2. Вернемся к бинарному алгоритму вычисления а" (пример 4.2), который можно легко описать рекурсивно. Для его сложности по числу умножений имеем

(

О, если п = 1,

Г\п\Л (25.20)

T_RS I - I + 2, если п > 1,

и

(0, еслип = 1,

Гцк(п)И Г\п\Л (25.21)

7rs(L§JJ+1, еслип > 1.

о, t (fc-	D+ 2,	если если	fc = 0, fc > l,
о, t (fc-l) + l,	если если	fc = 0, fc > l,

и

Соответствующими ассоциированными уравнениями будут t (fc) =

t (fc) =

их решения суть 2fc и fc. Отсюда

Llog₂ n J s= T_RS (n) s= 2 riog₂ n]. (25.22)

Эти оценки не сильно расходятся с точной формулой T _RS(n) = A(n) + + А*(п)-2.

§ 26. Асимптотические оценки решений рекуррентных неравенств 169

Дата добавления: 2014-01-11