Легко видеть также, что Н{т,п) - т + п - 1, если т < п < 2т. Следовательно, многократное применение формулы (18) даст нам общую формулу

H{m,n) = m+[n/2}-l + tm при ш < п, t=[lg(n/m)J. (19)

Отсюда следует, что Н{т,п) < Н{т, п+1) для всех п>т, что подтверждает нашу гипотезу, полученную по индукции применительно к шагу НЗ. Полагая т = an и в = \g{n/m) - t, найдем

Я(ст,п) =ап(1 +2--IgQ)+0(1) (20)

при п 00. Из формул 5.3.1-(3б) известно, что 1.9139 < 1 + 2* - < 2. Следовательно, (20) можно сравнить с теоретико-информационной нижней оценкой (3). Хуан и Линь доказали (см. упр. 17), что

Я(ш,п) <

+ min (m,n). (21)

Алгоритм бинарного слияния Хуана-Линя не всегда оптимален, но обладает тем неоценимым достоинством, что его довольно легко запрограммировать. Он сводится к "децентрированному бинарному поиску" при ш = 1 и к обычной процедуре слияния при ш « п, так что это золотая середина между двумя указанными методами. Кроме того, во многих случаях он является оптимальным (см. упр. 16). Дальнейшее совершенствование алгоритма описано в работах F. К. Hwang, D. N. Deutsch, JACM 20 (1973), 148-159; G. К. Manacher, JACM 26 (1979), 434-440; С. Christen, FOCS 19 (1978), 259-266. В последней из них Кристен (Christen) описал процедуру слияния, названную им forward-testing-backward-insertion (просмотр впереди, вставка позади), которая сокращает число сравнений примерно на ш/3 по сравнению с алгоритмом Н при п/ш оо. Более того, метод Кристена обеспечивает нижнюю оценку .М.(т,п) = [(11ш + п - 3)/4J, если 5ш - 3 < п < 7ш + 2[ш even]; следовательно, при этих условиях он оптимален.

Формула (18) наводит на мысль о том, что и сама функция М, быть может, удовлетворяет неравенству

М(ш,п) <М(ш, [n/2j)+m. (22)

Это и в самом деле так (см. упр. 19). Таблицы значений функции М{т, п) позволяют предположить, что, возможно, имеют место и другие соотношения, такие, как

М(ш+1, п) > 1 + М(ш,п) > М(ш, п+1) при ш < п; (23)

М(ш+1,п + 1) > 2 + М(ш,п); (24)

но в настоящее время не известно никаких доказательств этих неравенств. УПРАЖНЕНИЯ

1. [15] Найдите любопытное соотношение, которое связывает функцию М(т, п) и функцию S, определенную в разделе 5.3.1. [Указание. Рассмотрите S{m + п).]

► 2. [22] При m = 1 любой алгоритм слияния, не содержаш;ий избыточных сравнений, определяет расширенное бинарное дерево с ("\") = 1+1 внешними узлами. Докажите, что верно и обратное, т. е. каждому расширенному бинарному дереву соответствует некоторый алгоритм слияния с тп = 1.

3. [М24] Докажите, что .M.(l,n) = M(l,n) при всех п.

4. Справедливо ли неравенство .М.{т,п) > [Ig (""Jj")] при всех тип?

5. [МЗО] Докажите, что .М.(т, п) < .М\(т, n+l).

6. [М2б] Сформулированное выше доказательство теоремы К требует проверки на компьютере большого числа случаев. Каким образом можно резко сократить число таких случаев?

7. [21] Докажите неравенство (И).

8. [24] Докажите, что М(2, 8) < 6. Для этого придумайте такой алгоритм слияния двух элементов с восемью другими, который бы выполнял не более шести сравнений.

9. [27] Докажите, что три элемента можно слить с шестью элементами не более чем за семь шагов.

10. [33] Докажите, что пять элементов можно слить с девятью не более чем за двенадцать шагов. [Указание. Опыт введения соперника подсказывает, что начать нужно со сравнения Al •.В2, а затем, если Ai < В2, попытаться сравнить 5:8.]

11. [М40] (Ф. Хуан и Ш. Линь.) Пусть д2к = [2* if J, 52+1 = [2* tJ "Ри к > О, так что (5о,5ь52,..-) = (1,1,2,3,4,6,9,13,19,27,38,54,77,...). Докажите, что для слияния двух элементов с gt элементами требуется в худшем случае более чем t сравнений, однако слить два элемента с ( - 1 можно не более чем за t шагов. [Указание. Покажите, что если п = gt или п = pt - 1 и если нам нужно слить {Ai, Аг} с {В\,В2,... ,Вп} за t сравнений, то наилучшее первое сравнение - это А2:Вд .]

12. [М21] Пусть Rn{i,j) - наименьшее число сравнений, необходимое для сортировки различных объектов {а, fi,Xi,... ,Хп}, если заданы соотношения а < Р, Хх < Х2 < < Хп, а < Xi+i, Р > Xn-j. (Условие а < или > Xn-j теряет смысл, если i > п или j > п. Поэтому Rn{n, п) = М{2, п).)

Ясно, что Яп{0,0) = 0. Докажите, что

Rn{i,j) = 1 -l-mm( min max(i?„(fc-l, j), Rn-k{i-k, 3)),

\<k<i

min шах(Д„(г, fc-1), Rn-k(i, j-k)))

l<k<j

при 0 < г < n, 0 < J < n, г -f- j > 0.

13. [M42] (P. Л. Грэхем (R. L. Graham).) Покажите, что решение рекуррентного соотношения из упр. 12 можно выразить следуюш,им образом. Определим функцию G{x) при О < ж < оо такими правилами:

1, если О < ж < ;

1 -f G(8a; - 5), если f < ж < f;

\G{2x - 1), если I < ж < 1;

О, если 1 < ж < оо.

(Рис. 38.) Поскольку Rn{i,j) = Rn{3,i) и Rn{0,j) = M{l,j), можно считать, что 1 < г < j < п. Пусть р = [Ig i\,q= [Ig j\,r= [Ig nJ и пусть t = n-2 + 1. Тогда

R(i,J) = P + q + Sn(i,j) +Tn{i,j), где функции Sn и Тп принимают значения О или 1:

Sn{i,j) - 1 тогда и только тогда, когда q < г или (i - 2 > и и j - 2 > и), Tn(i,j) = 1 тогда и только тогда, когда р < г или (t > 2" и г - 2 > w),

где и = 2pg(t/2p) и t; = 2-G(t/2-).

G{x) =

1.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 Рис. 38. Функция Грэхема (см. упр. 13).

(Это, быть может, самое сложное рекуррентное соотношение из всех, которые, возможно, когда-либо будут решены!)

14. [41] (Ф. К. Хуаи.) Пусть кзк = [f 2*J - 1, hsk+i = /гз* + 3 2*- кзк+2 = [2- f J при > 3 и начальные значения подобраны так, что

{ho, /м, /12,...) = (1,1, 2,2,3,4,5, 7,9,11,14,18,23, 29,38,48,60, 76,...).

Докажите, что М(3, Ы) > t и М(3, /ij-1) < t при всех t, определяя таким образом точные значения М(3, и) для всех п.

15. [12] На шаге HI алгоритма бинарного слияния может потребоваться вычислить значение [lg(n/m)J при п > т. Как можно легко вычислить это значение, не применяя операций деления и взятия логарифма?

16. [18] При каких т и п, 1 < т < п < 10, оптимален алгоритм бинарного слияния Хванга и Шень Линя?

17. [М25] Докажите неравенство (21). [Указание. Это неравенство не очень жесткое.]

18. [М40] Исследуйте среднее число сравнений, выполняемых алгоритмом бинарного слияния.

► 19. [23] Докажите, что функция М удовлетворяет неравенству (22).

20. [20] Покажите, что если М{т, п+1) < М{гп+1, п) при всех т < п, то М{т, п+1) < 1 -I- М{т, п) при всех т < п.

21. [М47] Докажите или опровергните соотношения (23) и (24).

22. [М43] Исследуйте минимальное среднее число сравнений, необходимых для слияния m элементов с п элементами.

23. [М31] (Э. Рейнгольд (Е. Reingold).) Пусть {Ai,..., An} и {J5i,..., В„} - множества, содержаш,ие по и элементов. Рассмотрите алгоритм, который пытается проверить наличие равенства между множествами исключительно путем сравнений равенства элементов этих множеств. Таким образом, в процессе выполнения алгоритма задаются вопросы наподобие Ai - Bj?" при некоторых г и j и выбирается дальнейший путь вычислений в зависимости от того, был ли ответ положительным или отрицательным.

Определив подходяш,его соперника, докажите, что любой такой алгоритм в наихудшем случае будет вынужден выполнить не менее п(п + 1) сравнений.