строки, разделив его на подблоки и приняв за основу к-ю букву каждой строки. При этом сохранится сортировка блоков, выполненная по начальным буквам (будем называть их префиксом). Когда в блоке останется только один элемент и все их к-е символы будут равны null (т. е. все ключи будут одинаковыми), организуем работу так, чтобы избежать его повторного анализа. [R. Paige, R. Е. Tarjan, SICOMP 16 (1987), 973-989, §2.] Этот процесс, по сути, есть построение дерева, как описано в разделе 6.3. Более простой, но и немного менее эффективный алгоритм базируется на поразрядной сортировке справа налево и описывается в работе Aho, Hopcroft, Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, 1974), 79-84. Метод Мак-Илроя, на который имеется ссылка в тексте раздела, обеспечивает на практике еще более быструю сортировку.

17. Метод Мак-Ларена позволяет ускорить выполнение на втором уровне, но не может использоваться на первом уровне, поскольку он не предусматривает вычисление значений Л.

18. Во-первых докажем то, что рекомендовано в указании. Пусть pk = Jk/cN f{x) dx - вероятность того, что ключ попадет в стопку к, если имеется CN стопок. Время, необходимое для распределения записей, имеет порядок 0(N), а среднее число инверсий, остав-шихся после распределения, составляет Е=о~ - рО""= 5Е=о QPk < РкВ/С, поскольку Pk < B/CN.

Теперь рассмотрим два уровня распределения, причем на верхнем уровне число стопок - cN, и пусть bk - sup{/(x) I k/cN < x < (к -i- l)/cN}. Тогда среднее суммарное время выполнения равно 0{N) плюс Е1=о* ""Д - среднее время, затрачиваемое при выполнении сортировки Nk ключей, для которых функция плотности вероятностей имеет вид Д(х) = f{{k -Ь x)jcN)jcNpk в соответствии с алгоритмом Мак-Ларена. Как следует из приведенного выше анализа, Tk = EO{bkNk/cNpk), поскольку fk(x) ограничена величиной bk/cNpk. HoENk = Npk, так что Tk = 0(bk/c). А при N оо по определению интегрируемости по Риману получим Е1=о bk -¥ N f{x)dx = N.

РАЗДЕЛ 5.3.1

1. (а) (i?2) либо

а Bijk есть

Bij3 Bi3j

i:4j . Длина внешнего пути равна 112 (оптимальная).

(Ь) Здесь Aij =

, где djki =

Cij34 Cij43

ikjl iklj kijl kilj

Длина внешнего пути также равна 112 (оптимальная).

Цп) - В{п) = ((efc + к- 1)2" - (ei + 1)2=) + 2+ - 2 = 2=1 2 - (е,-efc+2-fc)2=

> 21 - (2"" + + 2"+ + 2") > 0.

При этом равенство достигается тогда и только тогда, когда п = 2*" - 2- при некоторых к > j > 0. [Если для слияния используется "нисходящая" версия, как в упр. 5.2.4-23, максимальное число сравнений будет равно В{п).]

3. При п > О число исходов, в которых наименьший ключ встречается точно к раз, равно {1)Рп-к. Таким образом, 2Р„ = E/t {1)Рп-к при п > О и мы имеем 2P(z) = eP{z) + 1, как следует из формулы 1.2.9-(10).

Другое доказательство опирается на тот факт, что Р„ = Е*:>о {fc}- поскольку {} есть число способов разбиения множества из п элементов на к непустых подмножеств, а эти подмножества можно переставить А;! способами. Таким образом, согласно форму-ле 1.2.9-(23) Е„>о PnZln = Е.>о(е - 1) = V(2 - е).

И все же остается еие одно, пожалуй, наиболее интересное доказательство. Скомпонуем из всех элементов устойчивую последовательность, так что Ki предшествует Kj тогда и только тогда, когда Ki < Kj или {Ki - Kj и г < j). Среди всех возможных Р„ исходов данное расположение Kai Ка„ встретится ровно 2*" раз, где к - число восходящих серий перестановки oi ... а„; следовательно, Р„ можно выразить через числа Эйлера: Р„ = Efc (fc)2 Искомый результат можно получить, используя формулу 5.1.3-(20), при z - 2.

Эту производящую функцию нашел А. Кейлей (А. Cayley) [Phil. Mag. 18 (1859), 374-378] применительно к перечислению одного нечетко определенного класса деревьев. См. также Р. А. MacMahon, Ргос. London Math. Soc. 22 (1891), 341-344; J. Touchard, Ann. Soc. Sci. Bruxelles 53 (1933), 21-31; O. A. Gross, AMM 69 (1962), 4-8. В последней работе получена интересная формула

Рп = Efc>i А;72+*, п > 1.

4. Представление

оо/ ч 1Л . iiz-\n2)\ 1 1 1 , 1 \

= n-°-2) = 2-72-7[z-ln2-2nik + z-ln2 + 2.ik)

дает сходящийся ряд Рп/п\ = (1п2) 5.

+ E.>iK((«2 + 27riA:)-"-).

1<2<3 1<2=3

2=3<1 3<2<1

1<3<2

6. S(n) > S(n), поскольку все ключи могут быть различны; таким образом, остается показать, что S(n) < S(n). Пусть дан алгоритм сортировки для различных ключей.

требующий S(n) шагов. Тогда можно построить алгоритм сортировки для общего случая, считая, что ветвь для отношения "=" идентична ветви для отношения "<" и удалить лишние сравнения. По достижении внешнего узла нам становятся известными все отношения равенства, поскольку Kai < Ка2 < • < Ка„ и при всех 1 < г < п были выполнены явные сравнения Kai -Koi+i-

М. Патерсон (М. Paterson) обратил внимание на то, что если множество ключей есть (п1,..., Пт), то число сравнений может быть уменьшено до п Ig п - 3 Ig + 0(п); см. SICOMP 5 (1976), 2. Этой нижней границы можно достичь без существенного увеличения объема дополнительной памяти, модифицировав метод пирамидальной сортировки применительно к случаю равных ключей, как предложено в работе Munro, Raman, Lecture Notes in Сотр. Sci. 519 (1991), 473-480.

7. См. рис. А-1. Среднее число сравнений равно (2-I-3-I-3-I-2-I-3-I-3-I-3-I-6-I-3-I-3-I-3-Ь 2-Ь 3-Ь 3-Ь 2)/16 = 2.

8. См. рис. А-2. Среднее число сравнений равно ЗЦ.

9. Если все ключи равны, то для того, чтобы обнаружить это, необходимо выполнить, по крайней мере, п - 1 сравнений. Обратно, п - 1 сравнений всегда достаточно, потому что окончательное упорядочение можно получить, сравнив Ki со всеми остальными ключами.

10. Пусть /(п) - искомая функция, а д(п) - минимальное среднее число сравнений, необходимое для сортировки п + к элементов, где А; > О, и ровно к элементов имеют известные значения (О или 1). Тогда /(0) = /(1) = д(0) = О, д(1) - 1; f{n) = 1 + f{n -1) + p(n - 2), д{п) = 1 + тт{д(п - 1), р(п - 1) + р(п - 2)) = 1 + р(п - 1) + р(п - 2) при п > 2. (Таким образом, наилучшая стратегия заключается в том, чтобы сравнивать каждый раз по возможности два неизвестных ключа.) Отсюда вытекает, что /(п) - д(п) = (/(п- 1) - д{п- 1)) при п > 2 и д{п) = Цп + (1 - (-5)")) при п > 0. Следовательно, ответ есть п-1- - (-1)" - (5)" при га > 1. (Эту точную формулу можно сравнить с теоретико-информационной оценкой нижней границы log3(2 - 1) и 0.6309га.)

11. То, что Sm{n) < В{т) -Ь (га - m)["lg(m + 1)] при п > т, можно доказать, используя методику бинарных вставок. С другой стороны, 5т(га) > fig EfcLi , предел правой части равен ralgm -Ь 0{{{т - 1)/т)") (см. формулу 1.2.6-(53)).

12. (а) Если избыточные сравнения не выполняются, то равным ключам, когда они сравниваются впервые, можно приписать произвольное отношение порядка, поскольку это отношение порядка нельзя вывести из предыдущих сравнений. (Ь) Предположим, что дерево сильно сортирует лфбую последовательность нулей и единиц. Докажем, что оно сильно сортирует любую перестановку элементов {1,2,..., га}. Пусть это не так, т. е. существует перестановка, которую оно якобы упорядочивает, как Ка < Ка < < АГа„, но в действительности существует г, при котором Kai > Iai+i Заменим нулями все элементы < АГа, и единицами - все элементы > Kai; по предположению наш метод рассортирует полученную перестановку, если выбрать путь, ведущий к Kai < < Ка„. Значит, мы получили противоречие.

13. Если п четно, то F(ra) - F(n - 1) = 1 + F([n/2J) - F([ra/2J - 1) и нам нужно доказать, что Wk-i < Ln/2J < Wk; это очевидно, поскольку Wk-i = [w*;/2J. Если п нечетно, то F(ra) - F(ra - 1) = G("ra/2l) - G([n/2J) и нам нужно доказать, что tk-i < Гп/2] < tk; это очевидно, поскольку tk-i = \wk/2].

14. Согласно упр. 1.2.4-42 эта сумма равна raflg га] - {wi -I----+ Wj), где Wj < п < Wj+i.

Последняя сумма равна wj+i - [j/2J - 1. Следовательно, F(n) можно записать в виде "[Ig 1 "1 ~ [2-"-/3j 4- [ lg(6n)J (а также многими другими способами.)