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

то слагаемое, которое содержит степень двойки с меньшим показа­телем. Вместо предложения 25.1 пользуемся предложением 25.2. □

Справедливость следующего предложения проверяется непосред­ственно.

Предложение 26.1. Если в условиях теорем 26.1 и 26.2 предполо­жить, что с = 0, то получим соответственно /(п) = 0(пlo&O+w)) и /(n) = n(n^l0&^(v+w)).

Пример 26.1. Вновь рассмотрим сложности рекурсивной сорти­ровки слияниями и бинарного возведения в степень. Уравнение (25.18) представим как систему двух неравенств со знаками соот­ветственно ^ и ^. Применяя к ним теоремы 26.1_и 26.2 (y + w = 2, log₂(v+w)=d = l), из первой теоремы получаем Т_ш(.п) = О(n log п), из второй — Т_ш(п) = П(п log п). В итоге имеем T_MS(n) = 6(n logn). Аналогичным образом представим в виде системы двух неравенств уравнение (25.16). Заменим в правой части п - 1 на п в случае ^ и на у в случае ^. Очевидно, что полученные неравенства являются след­ствиями исходных. С помощью теорем 26.1 и 26.2 (вновь v + w = 2, log₂(v+w) = d = l) получаем T_MS(n) = 0(n logn) и T_MS(n) = fi(nlogn). В итоге имеем T_MS(n) = 6(n logn).

Сложность рекурсивной сортировки слияниями как по числу срав­нений, так и по числу перемещений элементов массива допускает оценку 6(n log п).

Применяя теоремы 26.1 и 26.2 к (25.20), (25.21) (теперь v + w = l, log₂(v+w) = d = 0), получим T_RS(n) = О (log п) и T_RS(n) = n(logn). В итоге получаем T_RS (п) = в (log п).

Асимптотические оценки T_MS(n) = G(nlogn), T_MS(n) = G(nlogn), r_RS(n) = 6(logn) можно было бы получить и из выведенных ранее неравенств (25.19), (25.17), (25.22). Этот пример демонстрирует лишь то, что теоремы о рекуррентных неравенствах позволяют быстро по­лучать асимптотические оценки непосредственно из первоначальных рекуррентных неравенств.

Пример 26.2. Известен алгоритм построения выпуклой оболоч­ки объединения двух выпуклых многоугольников, имеющих соответ­ственно п_г и п₂ вершин, со сложностью 0{п_г + п₂) по общему числу операций, п_г + п₂ рассматривается как размер входа этого алгоритма (см. задачу 62). Стратегия «разделяй и властвуй» позволяет, исходя из этого, описать алгоритм построения выпуклой оболочки данного

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

множества n точек, сложность которого по общему числу операций при выборе n в качестве размера входа определяется соотношением

0, еслиn=1,

T(n)=

Tl +Tl +⁰^ при"^°°-

От этого соотношения мы переходим к неравенству

(О, если п = 1,

'( ^ ] + т(\ ^ ] + сп, если п > 1,

где с—некоторое неизвестное нам положительное число,—мы поль­зуемся здесь тем, что если g{n) = 0(,h(n)) и fr(n) > О при п > 1, то g{n) s= ch{n) для некоторой константы с и всех п > 1.

Применяем теорему 26.1 (v + w = 2, log₂(v + w) = 1, d = 1). Это да­ет T{n) = 0{n logп). Мы имеем, таким образом, еще один алгоритм построения выпуклой оболочки п заданных точек, по общему числу операций имеющий сложность O(nlogn).

Теоремы о рекуррентных неравенствах в некоторых книгах фор­мулируется иначе (см. задачу 144). Иногда¹ в условии этой теоремы предполагается, что исследуемая сложность является неубывающей функцией от п. Перед тем как применять теорему в таком ее виде к сложности конкретного алгоритма, необходимо доказывать неубы­вание этой сложности. Неубывание не является самоочевидным фак­том для алгоритмов, построенных по стратегии «разделяй и власт­вуй». Например, для бинарного алгоритма вычисления а" это не так: T_RS(7) = 4, T_RS(8) = 3. В теоремах 26.1 и 26.2 неубывание не предпола­гается.

Еще одно замечание. В § 9 мы получали формулы и оценки для сложностей алгоритма бинарного поиска места элемента, сортиров­ки фон Неймана и т. д. путем сравнения возникающих величин с по­следовательностью 2',Z = 0,1, ...; этот прием во многом аналогичен использованию соотношений вида (25.2), (25.14), но в том лишь част­ном случае, когда одно из чисел v,w равно нулю.