накопленную информацию, постройте одно дерево с выбыванием размером n - 1 - 2*°. (iv) Продолжайте, как при доказательстве (11).

23. [М49] Каково асимптотическое значение Vfn/2\ () при п -> оо?

24. [НМ4О] Докажите, что Vt{n) < n + t + 0(\/nlogn) при t < \п/2]. Указание. По-кажите, что, используя столько сравнений, можно фактически найти и \t - \ДТап\-&, и \t + y/tlnnl-u элементы, после чего легко выявляется t-й.

► 25. [MS5] (В. Кунто (W. Cunto) и Дж. И. Мунро (J. I. Munro).) Докажите, что Vt{n) > n + t-2, eaiHt< \п/2].

26. [MS2] (А. Шенхаж (А. Schonhage), 1974.) (а) Докажите в обозначениях упр. 14, что Ut{n) > min(2 + Ut{n - 1),2 + Ut-i{n - 1)) при n > 3. {Указание. Сконструируйте соперника посредством уменьшения количества элементов с п до п - 1 до тех пор, пока частичное упорядочение не будет состоять полностью из компонентов вида • или •-•.] (Ь) Аналогично докажите, что

Vt{n) > min(2 + Ut{n- 1), 3 + Ut-iin- 1), 3 + Ut{n- 2))

при n > 5, сконструировав соперника, который имеет дело с компонентами •-•, >», (с) Таким образом, получим Ut{n) >n + t + min([(n - t)/2\,t) - 3 при \ <t< n/2. [Неравенства в (a) и (b) относятся также к случаю, когда V или W заменяет f/, обеспечивая таким образом оптимальность определенных элементов в табл. 1.]

► 27. \М34\ Рандомизированный соперник - это соперник, алгоритм поведения которого позволяет при принятии решения использовать подбрасывание монеты.

a) Пусть А - рандомизированный соперник и пусть Pi{l) - вероятность того, что А достигнет листа I данного дерева сравнений. Покажите, что, если Рт{1) < р для всех I, высота дерева сравнений > Ig(l/p).

b) Проанализируйте поведение следующего соперника для выбора t-ro по старшинству из п элементов, причем целочисленные параметры q и г будут выбраны позже.

А1. Выбирается случайное множество Г, состоящее из t элементов; все (") вариантов считаются равновероятными. (Будем считать, что обеспечивается условие, при котором t-1 наибольших элементов принадлежат Г.) Пусть 5 = {1,...,п}\Г - другие элементы и установлено So S, То i- Т; So и Го будут представлять элементы, которые могут стать t-ми по старшинству.

А2. До" тех пор, пока То > г, все сравнения х:у выполняются следующим образом. Если X & S и у & Т, считается, что х < у. Если i € S и у € S, подбрасывается монета и удаляется меньший элемент из So, если он принадлежит So- Если i € Т и у & Т, подбрасывается монета и удаляется больший элемент из Го, если он принадлежит Го.

A3. Как только получим Го = г, элементы разделятся на три класса, P,Q,R, следующим образом. Если 5о < q, считается, что Р = S, Q = То, R = Т \ То. В противном случае для каждого у € Го считается, что С (у) - это элемент из S, который уже прошел сравнение с у и выбирается уо, такой, что С(2/о) минимально. Пусть Р = (5 \ 5о) U С{уо), Q = {So\ С{уо)) U {уо}, R = Т\ {уо}. Все последующие сравнения х: у выполняются так, что элементы из Р считаются меньше элементов из Q, а элементы из Q меньше элементов из R; если же х и у принадлежат одному и тому же классу, подбрасывается монета.

Докажите что, если 1 < г < t и С(уо) < q - г в начале шага A3, каждый лист достигается с вероятностью < (п + 1 - <)/(2""(")). Указание. Покажите, что будет сделано не менее п - q подбрасываний монеты.

c) Продолжая (b), покажите, что

Vt{n) > тт{п - 1 + (г - l){q + l-r),n-q + lg(()/(n + 1 - t)))

для всех целочисленных значений q и г.

d) Выведите (14), выбрав соответственно q и г.

*5.3.4. Сети сортировки

В настоящем разделе мы будем изучать класс методов сортировки, удовлетворяющих некоторому ограничению. Интерес к таким методам объясняется в основном приложениями и солидной теоретической основой. Это новое ограничение требует, чтобы последовательность сравнений не зависела от предыстории в том смысле, что если мы сравниваем и Kj, то последующие сравнения для случая Ki < Kj в точности те же, что и для случая Ki > Kj, однако г и j меняются ролями.

На рис. 43, (а) изображено дерево сравнений, в котором это условие однородности выполнено. Заметим, что на каждом уровне производится одинаковое число сравнений, поэтому после т сравнений имеется 2™ результатов. Так как п! не является степенью 2, некоторые сравнения будут излишними в том смысле, что одно из их поддеревьев никогда не встречается на практике. Иными словами, на некоторых ветвях дерева приходится выполнять больше сравнений, чем необходимо, чтобы сортировка была правильной на всех соответствующих ветвях.

Поскольку каждый путь на таком дереве сверху донизу определяет все дерево, эту схему сортировки проще изображать в виде сети, как на рис. 43, (Ь). Прямоугольник в подобной сети представляет "модуль компаратора", имеющий два входа (изображены линиями, входящими в .модуль сверху) и два выхода (изображены линиями, выходящими вниз); левый выход - меньший из двух входов, а правый выход - больший из них. Элемент К[ в нижней части сети есть наименьший из {К1,К2,Кз,К4}, К2 - второй в порядке возрастания и т. д. Нетрудно доказать, что любая сеть сортировки соответствует дереву сравнений, обладающему свойством независимости от предыстории (в указанном выше смысле), и что любое такое дерево соответствует сети модулей компараторов.

Между прочим, технически модуль компаратора довольно легко изготовить. Предположим, например, что по линиям связи в модуль поступают двоичные числа по одному разряду в единицу времени, начиная со старшего. Каждый модуль компаратора имеет три состояния и функционирует следующим образом.

Момент t Момент {t + 1)

Состояние Входы Состояние Выходы

О 0 0 О 0 0

О 0 1 1 0 1

О 1 0 2 0 1

0 11 О 11

1 X у 1 X у

2 X у 2 ух

Первоначально все модули находятся в состоянии О и выдают О 0. Модуль переходит в состояние 1 или 2, как только его входы становятся различными. .Числа, которые в момент времени t начали поступать сверху в сеть, соответствующую рис. 43, (Ь),

К\ к2 Кз К.\ I I

2 3 4

(а) (Ь)

Рис. 43. (а) Дерево сравнений, в котором не учитывается предыстория. (Ь) Соответствующая ему сеть.