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

Имеем

F(n)=vF₂ +_wf₂ +<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 выполняются неравенства ₂kn-1 и 2 ^ ^ п - 1, то по предположению индукции

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

2

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

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

/(n) ^ F (n) ^ F (2^{гlog2 nl}) (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)

2t(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 - (piCk - 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) = k2^k-2^k + l. (25.13)

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

T_MS(n) *S [log, n!2П°&n1 - 2^n1 + 1 = = ([log₂nl-l)2^rlo&^nl + l^ ^log₂n-2^lo^n⁺¹ + l = = 2n log₂ n + 1.

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

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

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

и, еслип = 1,

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

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

/(n)^t(Llog₂nJ), (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). Тогда получим оценки

taiog₂n|)sS/(n)sSt(riog₂nl).

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

0, еслип = 1,

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

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

(Llog₂ п\ - l)2^Ll0&^nJ + 1 s= Т_ш{п) s= aiog₂ п] - l)2^rl0&^nl + 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₂ nj2^"J ^ f_MS(n) ^ [log₂ п^Ч (25.19)

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

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

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

(О, если п = 1,

Г\п\Л (25.20)

T_RSI - 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₂ nJ s= T_RS (n) s= 2 riog₂ n]. (25.22)

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