2<1 = 3 = 42 = 3 = 4<1

Рис. А-1. Решение упр. 7. ("*" означает невозможный случай.)

Aijki = fj.l

i<j=k<l i<k<i=l

j:k\ i = k = l<j k-l<i<j

Рис. A-2. Решение упр. 8.

15. Если rigfn] =lg(fn) + e, то F(n) =nlgn-{3-\g3)n + n{e + l-2% + 0(logn). Если [Ign] =lgn + e, TO B(n) = nlgn - n + п(в + 1 - 2) + 0(logn). [Обратите внимание на то, что Ig п! = п Ig п - п/(1п 2) + OOog п); 1/(1п 2) и 1.443; 3 - Ig 3 и 1.415.]

17. Число случаев, когда 6* < Ор < bk+i, равно

т-р + п-к\ /р-1+к\ \ т-р А р-1 /

а число случаев, когда aj < Ь, < aj+i, равно

n-g + m-j j 9- 1+J j

18. Нет, поскольку мы рассматриваем всегда наименее эффективную ветвь под каждым узлом-сравнением. Одна из более эффективных ветвей могла бы оказаться более трудоемкой.

20. Пусть L - максимальный номер уровня, на котором есть внешние узлы, а / - такой минимальный номер. Если L > Z -Ь 2, то на уровне L можно удалить два узла и поместить их под некоторым узлом на уровне /; в результате длина внешнего пути сократится на I + 2L - {L - 1 + 2(1 + 1)) = L - I - I > I. Обратно, если L < I + 1, то пусть к внешних узлов находятся на уровне I и N - к узлов - на уровне 1 + 1, где О < к < N. Как показано в упр. 2.3.4.5-3, к2~ + {N - к)2~~ = 1; следовательно, N + к = 2+К Из неравенств 2 < N < 2"" вытекает, что I = [lgN\; отсюда определяется значение к, а также получается длина внешнего пути (34).

21. Пусть г(х) - корень правого поддерева узла х. Все поддеревья будут иметь минимальную высоту тогда и только тогда, когда [lgt(/(x))] < [Igt(x)] - 1 и [lgt(r(x))] < [lgt(a;)] -1 для всех х. Первое из них эквивалентно условию 2t{l(x)) - t{x) < 2fe4)l - t(x), а второе - условию t{x) - 2t{l(x)) < 2fetix) t{x).

22. Согласно упр. 20 четыре условия, [lgt(/(x))J, [lgt(r(x))J > [lgt(x)J - 1 и \lgt{l(x))], [lgt(r(x))] < rigt(x)] - 1, необходимы и достаточны. Рассуждая, как в упр. 21, можно доказать, что они эквивалентны сформулированным в условии этого упражнения неравенствам. [См. Martin Sandelius, АММ 68 (1961), 133-134.] Распространение этого решения на общий случай приводится в упр. 33.

23. При сортировке посредством вставок в несколько списков предполагается, что ключи равномерно распределены в известном диапазоне, значит, он не принадлежит к числу методов "чистых сравнений", удовлетворяющих ограничениям, которые рассматриваются в этом разделе.

24. Действуйте сначала, как при сортировке пяти элементов, до тех пор, пока не получите одну из конфигураций (6). В первых трех случаях завершите сортировку пяти элементов при помощи еще двух сравнений, после чего вставьте шестой элемент /. В последнем случае нужно сначала сравнить f:b, вставить / в главную цепочку, а затем вставить с. [Picard, Theorie des Questionnaires, page 116.]

25. Поскольку iV = 7! = 5040 и g = 13, было бы 8192-5040 = 3152 внешних узла на уровне 12 и 5040 - 3152 = 1888 внешних узлов на уровне 13.

26. В работе L. KoUar, Lecture Notes in Сотр. Sci. 233 (1986), 449-457, представлен прекрасный способ проверки утверждения, что оптимальный метод сортировки дает путь длиной 62416.

27. Это единственный способ распознать две наиболее часто встречающиеся перестановки за два сравнения, несмотря на то что первому сравнению соответствует разбиение с вероятностью .27/.73.

28. Лунь Куань (Lun Kwan) составил программу длиной 873 строки, среднее время работы которой равно 38.925U. Максимальное время ее работы равно 43и; по-видимому, оно оптимально, поскольку как раз столько времени требуется для выполнения 7 сравнений, 7 проверок, 6 загрузок и 5 записей в память.

29. Не выполнив S(n) сравнений, невозможно дать однозначный ответ, какой является перестановка: четной или нечетной. В самом деле, если предположить, что в результате выполнения некоторого числа сравнений мы "сузили" задачу до такой степени, что осталось всего два возможных исхода в зависимости от того, будет ли а, меньше или больше Oj, где i и j - некоторые индексы, то один из этих возможных исходов - четная перестановка, другой - нечетная. [С другой стороны, для решения этой задачи существует алгоритм с временем работы 0{п); он просто подсчитывает количество циклов и вовсе не содержит сравнений; см. упр. 5.2.2-2.]

30. Возьмите оптимальное дерево сравнений высотой S(n). Двигаясь сверху вниз, меняйте местами г о j в правом поддереве узла В полученном дереве, которое интерпретируется как дерево сравнений-обменов, каждый концевой узел определяет единственную перестановку, а ее можно рассортировать не более чем за п - 1 дополнительных сравнений-обменов (это показано в упр. 5.2.2-2). [Идея дерева сравнений-обменов принадлежит Т. Н. Хиббарду (Т. N. Hibbard).]

31. Необходимо не менее 8 сравнений-обменов, поскольку в любом дереве высотой 7 существует ветвь, которая после 4 шагов приведет к конфигу-рации, где а Ф I (или двойственной по отношению к ней). Эту конфигу- d рацию нельзя рассортировать за три операции сравнения-обмена. С другой стороны, ниже показано дерево, на котором достигается искомая нижняя граница оценки (а также, быть может, минимальное среднее число сравнений-обменов).