33. к любому дереву порядка х с разрешением 1 можно применить простую операцию для получения другого дерева, длина взвешенного пути которого не превышает длины пути исходного дерева, причем: (а) существует такое число к, что все внешние узлы лежат на уровнях А; и А; - 1, (Ь) не более чем один внешний узел содержит нецелое значение, и если таковой имеется, то он находится на уровне к. Длина взвешенного пути любого такого дерева имеет указанное значение, так что оно должно быть минимальным. Обратно, если в вещественнозначном дереве поиска выполняются условия (iv) и (v), то, применив индукцию, можно показать, что длина взвешенного пути имеет указанное значение, поскольку для этого параметра существует простая формула, выражающая ее через длины путей двух поддеревьев корня.

35. Ключ к решению этой задачи содержится в безуспешных экспериментах, описанных в работе Knuth, Kaehler, Information Processing Letters 1 (1972), 173-176.

36. См. Математические заметки 4 (1968), 511-518. Обзор достижений в решении этой задачи представлен в работе S. Felsner, W. Т. Trotter, Combinatorics, Paul Erdos is Eighty 1 (1993), 145-157. Там же доказано, что мы всегда можем получить 1 < T{G\)jT{G2) < р, где константа р чуть-чуть меньше 8/3.

РАЗДЕЛ 5.3.2

1. S{m + п) < S{m) + S(n) + М(т, п).

2. Внутренний узел, который является А;-м по счету при отношении порядка, симметричном к исходному, соответствует сравнению Ai.Bk-

3. Стратегия В(1,/) не лучше стратегии А(1,1+1), а стратегия В(1,/) не превосходит стратегии А(1, /-1). Следовательно, нужно разрешить рекуррентное соотношение

.М.(1,п)= min max(max (1--.М.(1, г-1)), max (1--.М.(1, п-0)), п > 1;

l<j<n 1<<J j<l<n

.М.(1,0) =0.

Нетрудно проверить, что этому соотношению удовлетворяет решение [lg(n + 1)].

4. Нет [см. С. Christen, FOCS 19 (1978), 259-266].

6. При j = i + 1 можно воспользоваться стратегией А(г, г--1), за исключением случая i < 2. При j > i + 2 можно применить стратегию А(г, i+2).

7. Чтобы вставить к + т элементов в поетедовательность п других элементов, вставьте независимо к элементов и т элементов. (Если кит велики, то можно применить более совершенную процедуру; см. упр. 19.)

8. На следующих диаграммах i:j означает сравнение Ai.Bj; через Мц обозначено слияние i элементов с j элементами за M{i,j) шагов, а через А - сортировка конфигурации .V. или .V, за три шага.

М23 (2:5) fl: 4) Mis,

Mi4 Mi5 Mi3 + 1 A (2:l)l+M22 M22 + I l+A

Мы Mi3 + 1

Симметрично

2:2) (3:3)М22+1+-4

М25 Мы+2 M23+I М22+2 2Mi2+l 2+Л (4:2) М22+2 М12+З М12+З

Mi4 + 1 М13+2

11. Воспользуемся указанием: положим п = gt- Можем считать, что t > 6. Без потери общности можно первым сравнением сделать Ai-Bj. Если j > gt-i, то исход а2 < Bj потребует еще > t шагов. Если j < gt-i, то исход а2 < Bj не вызовет трудностей, и поэтому необходимо исследовать лишь случай а2 > Bj. Больше всего информации мы паиучаем при j = gt-i. Если t = 2к + 1, то можно было бы слить а2 с gt - gt-i = 2*"" элементами, превышающими Вд, , и слить Ai с остальными gt-i элементами, но для этого понадобилось бы еще к + (к + 1) = t шагов. С другой стороны, если п = gt - 1, то можно было бы слить а2 с 2*"" - 1 элементами, а затем Ai - с п элементами еще за (к - 1) + (к + 1) шагов. Следовательно, М(2, Pt -1) < t.

Случай t = 2к значительно сложнее; обратите внимание на то, что gt - gt-i > 2*~. Предположим, что если Аг > Bg, i, то мы будем сравнивать Ai.Bj. Если j > 2*"" то исход Ai < Bj потребует еще к + (к-1) сравнений (слишком много). Если j < 2*", то можно, как и раньше, доказать, что выбор j = 2*~ даст больше всего информации. В случае Ai > Bjk-i можно было бы сравнить также Ai с Вг-+г-, затем с 52-1+2-2+2-3; поскольку 2*-1ц.2*-22*~з > gt-i, остается лишь слить {Ai, Аг} с п-(2*~--2*~+2*") элементами. Разумеется, вовсе не обязательно сразу же выполнять какие-либо сравнения с Ai; можно

вместо этого сравнить A2:Bn+i-j. Если j < 2 , то рассматриваем случай Аг < 5n+i если же j > 2*"", то рассматриваем Аг > Bn+i-j- Этот последний случай требует еще не менее (к-2) + {к + 1) шагов. Продолжая рассуждение, обнаруживаем, что единственный потенциально плодотворный путь - это Аг > Bgf y, Аг < В„+1 гь-з, А\ > Bjk-i, Ai > B2-i+2*-2> Ai > B2-i+2-2+2-3i HO тогда остается еще ровно gt-ъ элементов! Обратно, если п = - 1, то этот путь приводит к желаемому результату. [Acta Informatica 1 (1971), 145-158.]

12. Первое сравнение должно быть либо а:Хк, где 1 < к <i, либо (симметрично) 13:Х„-к, где 1 < к < j. В первом случае при исходе а < Хк остается выполнить еще R„(k - l,j) сравнений; исход а > Хк приводит к задаче сортировки а < /3, Vi < • • < Уп-*, а < Yi-k+i, 3>Yn-k-j,тдeYr=Xr-k.

13. См. Computers in Number Theory (New York: Academic Press, 1971), 263-269.

14. SICOMP 9 (1980), 298-320. Полное решение для случая М(4, п) получено спустя непродолжительное время в работе J. Schulte, Monting, Tiieor. Сотр. Sci. 14 (1981), 19-37, где также предлагается решение для случая М{5,п).

15. Удваивать т до тех пор, пока результат не превзойдет п. Для этого придется выполнить Llg(n/m)J + 1 операций удваивания.

16. При всех (т, п), за исключением (т, п) = (2,8), (3,6), (3, 8), (3,10), (4,8), (4,10), (5,9), (5,10). При этих значениях число сравнений на единицу больше оптимального.

17. Предположим, т < п, и пусть t = \g{n/m.) - в. Тогда Ig С"") > Ign"" - Igm! > mlgra-(mlgm-m-l-l) = m.(t + e) + m-l = Н{т,п)+вт-[2т} > Н(т,п) + ет-2т > Н{т, п) - т. (Неравенство т\ < т"2~" является следствием того, что к(т - к) < (т/2)2 при 1 < А; < т.)

19. Слейте сначала {Ai,..., Am} с {Вг, В4, , B2[n/2j } Тогда останется вставить нечетные элементы Вг,-! в последовательность ai элементов А, 1 < i < Гп/2], где ai + а2 + • + 0{„/21 < т. При выполнении этого последнего действия на каждое значение г придется выполнить а, операций, так что для завершения сортировки достаточно выполнить еше не более т сравнений.

20. Применить неравенство (12).

22. В работе R. Michael Tanner, SICOMP 7 (1978), 18-38, показано, что в алгоритме "фрактальных вставок" используется в среднем не более 1.06 Ig (",") сравнений. В работе L. КоПаг, Computers и Artificial Int. 5 (1986), 335-344, проанализировано поведение "в среднем" алгоритма Н.

23. Соперник имеет матрицу X размера п х п, элементы которой xij вначале все равны единице. Когда алгоритм спрашивает, имеется ли равенство Ai = Bj, соперник устанавливает Xij равным нулю. Он отвечает "нет" до тех пор, пока перманент матрицы X не станет равным нулю. В этом случае соперник отвечает "да" (ему ничего не остается делать, иначе выполнение алгоритма немедленно завершится!) и исключает из матрицы А строку i и столбец j; полученная матрица (п -1) х (п-1) будет иметь ненулевой перманент. Соперник продолжает и дальше действовать таким образом, пока у него не останется матрица 0x0.

Если перманент близок к нулю, можно перекомпоновать строки и столбцы таким образом, что г = j = 1 и все единицы будут на главной диагонали матрицы. Таким образом перманент обращается в нуль, если хц <- 1; значит, мы должны получить xux/ti = О для всех А; > 1. Отсюда следует, что, по крайней мере, п нулей удаляются при первом ответе "да" соперника, а п - 1 - при втором ответе и т. д. Выполнение алгоритма завершится лишь после получения п положительных ответов на неизбыточные вопросы и после того

как мы зададим, по меньшей мере, п-Ь(п- 1) Н-----hi вопросов [JACJVf 19 (1972), 649-659].

Аналогичные рассуждения приведут нас к заключению, что необходимо п + (п - 1) + + (п - т+1) вопросов для того, чтобы выяснить, что А С В при А = m < п = В.

24. Грубое предварительное слияние потребует не более т + q - 1 слияний, а каждая последующая процедура вставки - не более t. Эта верхняя оценка не может быть уменьшена. Таким образом, максимальное число сравнений будет тем же, что и в алгоритме Н (см. (19)).

25. В общем, сложность этой задачи такова же, как и для отдельного случая, когда каждый элемент Ху - это либо О, либо 1 и х = . Тогда каждое сравнение эквивалентно анализу бита х и мы стремимся определить всю матрицу, просматривая только младшие разряды. Любая задача сортировки (1) соответствует матрице 0-1, если установить х = [Ai>Bn+i-j]. (В работе N. Linial, М. Saks, J. Algoritlims 6 (1985), 86-103, этот вывод приписывается Дж. Ширеру (J. Shearer). Аналогичный результат связывает сортировку и поиск при любом частичном упорядочении.)