§ 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₂nl), (25.3)

где

и, если к = 0,

(v+w)t(fc-l)+(^(2^fc), еслик>0.

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

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

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

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

vFf +wFf +У^> еслип>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