выражение \uiVi+i - Ui+iVt\. (Хотя этот метод использует гораздо меньше информации, чем содержится в полной матрице сравнений, подобной (24), он, как оказывается, во многих случаях дает оптимальные результаты.)

► 20. [М26] Докажите, что расширенное бинарное дерево имеет минимальную длину внешнего пути тогда и только тогда, когда существует такое число I, что все внешние узлы находятся на уровнях I и I + 1 (или, быть может, только на уровне /).

21. 1М21 ] Высотой расширенного бинарного дерева называется максимальный номер уровня, на котором есть внешние узлы. Пусть х - внутренний узел расширенного бинарного дерева; обозначим через t{x) число внешних узлов-потомков узла х, а через 1{х) - корень левого поддерева узла х. Если х - внешний узел, то положим t{x) = 1. Докажите, что расширенное бинарное дерево имеет минимальную высоту среди всех бинарных деревьев с тем же числом узлов тогда и только тогда, когда для всех его внутренних узлов х выполняется неравенство

<(x)-2t(Z(x))<2f«<-<(x).

22. [М24] Продолжение упр. 21. Докажите, что бинарное дерево имеет минимальную длину внешнего пути среди всех бинарных деревьев с тем же числом узлов тогда и только тогда, когда для всех его внутренних узлов х выполняются неравенства

\t{x) - 2t{l{x))\< 28<"1 - t{x) и \t{x) - 2t{l{x))\< t{x) - 2L8(J.

[Так, например, если t{x) - 67, то должно выполняться следующее: t{l{x)) = 32, 33, 34 или 35. Если нужно просто минимизировать высоту дерева, то согласно предыдущему упражнению достаточно, чтобы 3 < t{l{x)) < 64.]

23. [10] В основном тексте раздела доказано, что среднее число сравнений, выполняемых любым методом сортировки п элементов, не может быть меньше [IgJi!] ~ nig п. Однако при сортировке методом вставок в несколько списков (программа 5.2.1М) затрачивается в среднем всего 0{п) машинных циклов. Чем это объясняется?

24. [27] (К. Пикар (С. Picard).) Постройте такое дерево сортировки для шести элементов, чтобы все его внешние узлы располагались на уровнях 10 и 11.

25. [11] Если бы существовала процедура сортировки семи элементов, при которой достигался бы минимум среднего числа сравнений, вычисляемый при помощи формулы (34), то сколько внешних узлов было бы на уровне 13 соответствующего дерева?

26. [М42] Найдите процедуру сортировки для семи элементов, минимизирующую среднее число выполняемых сравнений.

► 27. [20] Пусть известно, что конфигурации Ki < К2 < К3, Ki < К3 < К2, К2 < Ki < Кз, К2 < Кз < Ki, Кз < Ki < К2, Кз < К2 < Ki встречаются с вероятностями соответственно .01, .25, .01, .24, .25, .24. Найдите дерево сравнений, которое бы сортировало такие три элемента с наименьшим средним числом сравнений.

28. [40] Напишите программу для MIX, которая сортирует 5 однословных ключей за минимально возможное время, после чего останавливается. (См. основные правила в начале раздела 5.2.)

29. [М25] (С. М. Чэйз (S. М. Chase).) Пусть 0102-. .Оп - перестановка множества {1,2, ...,п}. Докажите, что любой алгоритм, который распознает, является ли данная перестановка четной или нечетной (т. е. содержит ли она четное или нечетное число инверсий), и основанный исключительно на сравнениях элементов а, должен выполнить не менее п ig п сравнений, хотя он имеет всего два возможных исхода.

30. [М25] {Оптимальная обменная сортировка.) Любой алгоритм обменной сортировки в соответствии с определением, данным в разделе 5.2.2, можно представить в виде дерева сравнений-обменов, а именно - в виде структуры бинарного дерева, внутренние узлы которого имеют вид где i < j, и интерпретируются след>Ющим образом: "Если Kt < Kj, то продвинуться по левой ветви дерева; если Kt > Kj, то поменять местами записи i и j и продвинуться по правой ветви дерева" По достижении внешнего узла должны выполняться условия Ki < К2 < •• < Kn- Таким образом, дерево сравнений-обменов отличается от дерева сравнений тем, что оно описывает не только операции сравнения, но и операции перемещения данных.

Обозначим через Se{n) минимальное число сравнений-обменов, необходимых в наихудшем случае для сортировки элементов при помощи дерева сравнений-обменов. Докажите,

что Se{n) < S{n) + П - 1.

31. [М38] Продолжение упр. 30. Докажите, что Se(5) = 8.

32. [М42] Продолжение упр. 31. Исследуйте значения функции Se{n) при малых п > 5.

33. [МЗО] (Т. Н. Хиббард (Т. N. Hibbard).) Вещественнозначным деревом поиска порядка, X с разрешением S называется расширенное бинарное дерево, каждый узел которого содержит неотрицательное действительное значение, такое, что: (i) значение в любом внешнем узле < S; (ii) значение в любом внутреннем узле не превышает суммы значений двух его потомков; (iii) значение в корне равно х. Длина взвешенного пути такого дерева определяется как сумма по всем внешним узлам номеров уровней этих узлов, умноженных на содержащиеся в них значения.

Докажите, что вещественнозначное дерево поиска порядка х с разрешением 1 имеет длину взвешенного пути, минимальную среди всех таких деревьев того же порядка и с тем же разрешением тогда и только тогда, когда в (ii) имеет место равенство и для всех пар значений хо и xi, принадлежащих узлам-братьям, выполняются следующие условия: (iv) не существует целого числа А: > О, такого, что iq < 2* < xi или ii < 2* < хо; (v) [хо] - Хо -\- [xi] - xi < 1. (В частности, если х - целое число, то из условия (v) следует, что все значения в дереве - целые, а условие (iv) эквивалентно результату упр. 22.)

Докажите также, что соответствующая минимальная длина взвешенного пути равна x[lgx] + [х] -2f8l

34. [М50] Определите точные значения функции S{n) для бесконечного множества аргументов п.

35. [49] Определите точное значение функции 5(13).

36. [MS0] (С. С. Кислицын, 1968.) Докажите или опровергните следующее утверждение: любой ориентированный ациклический граф G, в котором T{G) > 1, имеет две вершины, и а v, такие, что диграфы Gi и G2, полученные из G в результате добавления дуг и г и и v, также ацикличны и удовлетворяют условию 1 < T{Gi)/T{G2) < 2. (Таким образом, T{Gi)jT{G) всегда лежит между и при некоторых и и v.)

*5.3.2. Слияние с минимальным числом сравнений

Рассмотрим теперь вопрос, имеющий отношение к предыдущему разделу: каков наилучший способ слияния упорядоченного множества т элементов с упорядоченным множеством п элементов? Обозначим элементы сливаемых множеств

Ai < А2 < < А„, и Bi < В2 < < Вп. (1)

Как и в разделе 5.3.1, будем предполагать, что все m + п элементов различны. Элементы А среди элементов В могут располагаться ("J") способами. Таким

образом, из анализа, которым мы воспользовались в задаче о сортировке, следует, что необходимо выполнить, по крайней мере,

сравнений. Если положить т = an и устремить п оо, оставив а неизменным, то по формуле Стирлинга

Igf""") =n((l + Q)lg(l+a)-algQ) -ilgn + 0(l). (3)

\ an /

Обычная процедура слияния (алгоритм 5.2.4М) выполняет в худшем случае т + п - 1 сравнений.

Обозначим через М{т,п) функцию, аналогичную 5(п), а именно минимальное число сравнений, заведомо достаточное для слияния т элементов с п элементами. Из только что сделанного вывода следует, что

< М{т,п) <т + п - I прит,п>1. (4)

Формула (3) показывает, насколько далеко могут отстоять друг от друга нижняя и верхняя оценки. При а = 1 (т. е. m = п) нижняя оценка равна 2п - lgn + 0(1), так что обе оценки - величины одного порядка, но разность между ними может быть сколь угодно велика. При а = 0.5 (т. е. m = п) нижняя оценка равна

n(lg3-f)+0(logn),

что составляет примерно lg3 - « 0.918 от верхней оценки. С убыванием а разница между верхней и нижней оценками все увеличивается, поскольку стандартный алгоритм слияния разработан, главным образом, для массивов с m « п.

При т = п задача о слиянии имеет весьма простое решение; слишком грубой оказывается не верхняя, а нижняя оценка в (4). Следующую теорему независимо доказали Р. Л. Грэхем (R. L. Graham) и Р. М. Карп (R. М. Кагр) примерно в 1968 году.

Теорема М. М{т,т) = 2т - 1 при т>1.

Доказательство. Рассмотрим какой-нибудь алгоритм, который осуществляет слияние элементов Ai < •• < Am с Bi < •• < Вт- При сравнении элементов Ai.Bj выберем ветвь Ai < Bj, если i < j, и ветвь Ai > Bj, если г > j. Слияние должно завершиться конфигурацией

Bx<Ai <В2<А2<---<Вт< Am, (5)

поскольку она согласуется со всеми выбранными ветвями. И каждое из 2т - 1 сравнений Bi.Ai, Ai:B2, В2:А2, Вт-Ат должно быть выполнено явно, иначе найдется по меньшей мере две конфигурации, не противоречащие известным фактам. Если бы мы, например, не сравнили Ai с В2, то конфигурация

Bi<B2<Ax<A2<---<Bm< Am

была бы неотличима от (5).