Таблица 1

НИЖНИЕ ОЦЕНКИ ДЛЯ СЛИЯНИЙ, ВЫПОЛНЕННЫХ ПРИ УЧАСТИИ СОПЕРНИКА

Если перейти к более общему случаю, выполнив для этого сначала сравнение Ai:Bk, а затем использовав двоичный поиск в случае Ai < Bk, увидим, что при m > 1 и п > к выполняется неравенство

М(т, п) < max(M(m,п-к) + 1, М(т-1, п) + 1 + [Ig1)• (14)

Оказывается, M(m,n) = .М.{т,п) при всех т,п < 10, так что в табл. 1 в действительности приведены оптимальные значения для слияний. Это можно доказать, применяя соотношения (9)-(14), а также специальные построения для (т, п) = (2,8), (3,6) и (5,9), которые приводятся в упр. 8-10.

С другой стороны, такой соперник не всегда дает наилучшую возможную нижнюю оценку. Простейший пример: m = 3, п = 11, когда .М.(3,11) = 9, а М(3,11) = 10. Чтобы понять, где же в этом случае наш соперник "промахнулся", нужно изучить мотивы, на которых основаны его решения; при дальнейшем тщательном исследовании обнаруживается, что если {i,j) ф (2,6), то соперник может отыскать стратегии, требующие 10 сравнений; если же (г, j) = (2,6), то ни одна стратегия не превосходит стратегию А(2,4), которая приводит к нижней оценке 1 + .Л/.(2,3) Л-.Л/. (1,8) = 9. Необходимо, но не достаточно, чтобы процесс заканчивался слиянием {Лх, Лг} с {Bi, Вг, Вз} и {Лз} с {в4,..., Вц}; таким образом, нижняя оценка в этом случае оказывается неточной.

Аналогично можно показать, что .М.(2,38) = 10, в то время как М(2,38) = 11, и т. д. Значит, наш соперник не достаточно искусен, чтобы справиться со случаем m = 2. Однако существует бесконечный класс значений, для которых он работает безупречно.

Теорема К. М{т, т+2) - 2т+1 при m > 2;

М{т, т+3) = 2т + 2 при т > 4; М{т, т+4) = 2т + 3 при m > 6.

Доказательство. На самом деле мы можем доказывать эти соотношения, заменив М на .М.; при малых т эти результаты были получены на компьютере, поэтому можно предполагать, что т достаточно велико. Можно также считать, что первое сравнение есть Ai.Bj, где i < Гт/2]. Если j < г, то воспользуемся стратегией А(г, г); тогда получим

.M.{m,m+d) > 1 + .M.{i-l,i) + .M.{m+l-i,m+d-i) = 2т + d - 1,

применив индукцию по d, d < 4. Если j > г, то воспользуемся стратегией А(г,г+1); применив индукцию по т, получим

.M.{m,m+d) > 1 + .M.{i,i) + .M.(m-i,m+d~i) = 2m + d - 1.

Первые два утверждения теоремы К получили Ф. Хванг и Ш. Линь в 1969 году. Спустя несколько лет Пол Стокмайер (Paul Stockmeyer) и Фрэнсис Яо (F. F. С. Yao) показали, что некоторые свойства этих формул можно распространить и на более обший случай. В частности, нижние оценки, выведенные стратегиями соперника, достаточно удовлетворительны для того, чтобы обеспечить значения М(т, m+d) = 2m + d - 1 при m > 2d - 2. [SICOMP 9 (1980), 85-90.]

Верхние оценки. Рассмотрим теперь верхние оценки функции М{т,п). Хорошие верхние оценки соответствуют эффективным алгоритмам слияния.

При m = 1 задача слияния эквивалентна задаче вставки, когда имеется п + 1 мест между элементами Бх,..., В„, куда может попасть элемент Ai. В этом случае нетрудно видеть, что любое расширенное бинарное дерево с п + 1 внешними узлами есть дерево для некоторого метода слияния (см. упр. 2)! Следовательно, можно выбрать оптимальное бинарное дерево, реализовав теоретико-информационную нижнюю оценку

1+LIgnJ =М(1,п)= rig(n+l)l. (15)

Разумеется, бинарный поиск (раздел 6.2.1) - простейший способ, позволяющий достичь этого значения.

Случай m = 2 чрезвычайно интересен, но анализировать его гораздо сложнее. Этот анализ полностью выполнен Р. Л. Грэхемом, Ф. К. Хуаном и Ш. Линем, которые вывели формулу для общего случая (см. упр. 11-13):

М(2, п) = [Ig (п + 1)1 + [Ig И(п + 1)1. (16)

Мы видели, что при т - п оптимальна обычная процедура слияния, а при m = 1 оптимальна довольно сильно отличающаяся от нее процедура бинарного поиска. Нам же нужен некоторый промежуточный метод, объединяющий в себе лучшие черты алгоритмов обычного слияния и бинарного поиска. Формула (14) наводит на мысль о следующем алгоритме (F. К. Hwang и S. Lin [SICOMP 1 (1972), 31-39]).

Алгоритм Н {Бинарное слияние).

HI. Если ш или п равно О, прекратить выполнение алгоритма. В противном случае, если т > п, установить t +- [lg(m/n)J и перейти к шагу Н4. В противном случае установить t •ь- [lg{n/m)\.

Н2. Сравнить Am-Bn+i-2*• Если Am меньше, то установить п •ь- п-2* и вернуться к шагу HI.

НЗ. Используя бинарный поиск (который требует ровно t дополнительных сравнений), вставить Am в нужное место среди {Bn+i-2,---,Вп}- Если к максимальное и такое, что Bk < Am: установить тп +- т-1 и п +- к. Вернуться к шагу HI.

Н4. (Шаги Н4 и Н5 подобны Н2 и НЗ, но переменные тп и п, А и В меняются ролями.) Если Бп < Ат+1-2Ч установить ш ш - 2* и вернуться к шагу HI.

Н5. Вставить В„ в нужное место среди элементов А. Если к максимальное и такое, что Ak < Bn, установить тп+-кип+-п - 1. Вернуться к шагу HI.

В качестве примера работы этого алгоритма в табл. 2 показан процесс слияния трех ключей {087, 503, 512} с тринадцатью ключами {061, 154,..., 908}; в этом примере выполняется восемь сравнений. Элементы, сравниваемые на каждом шаге алгоритма, выделены полужирным шрифтом.

Таблица 2

ПРИМЕР ПРИМЕНЕНИЯ МЕТОДА БИНАРНОГО СЛИЯНИЯ

Пусть Н{тп,п) - максимальное число сравнений, выполняемых алгоритмом Хуана и Линя. Чтобы вычислить Н{тп,п), можно предположить, что А; = п на шаге НЗ и А; = ш на шаге Но, поскольку при помощи индукции по ш нетрудно доказать, что Я(ш - 1,п) < Я(ш - 1,п + 1) при всех п > т - 1. Таким образом, при т <п имеем

Я(ш, п) = тах(М(ш, п-2)+1, Я(ш-1, n)+t+l) (17)

при 2*ш < п < 2*+im. Заменим п на 2п -Н б (е = О или 1) и получим

Я(ш, 2п+е) = max (Я(ш, 2n+e-2+i) + 1, Я(ш-1, 2n+e)+t+2) при 2ш < п < 2*+1ш. Отсюда вытекает, если применить индукцию по п, что

Н{гп,2п+е) = Н{т,п) + т при ш < п и е = О или 1. (18)