AOP_Tom3 (1021738), страница 7
Текст из файла (страница 7)
Нвапб и 8. Гйп [В!СОМР 1 (1972), 31 — 39)). Разумеется, бинарный поиск (раздел 6.2.1) — простейший способ, позволяющий достичь этого значения. Случай т = 2 чрезвычайно интересен, но анализировать его гораздо сложнее. Этот анализ полностью выполнен Р. Л. Грзхемом, Ф. К. Хуаном и Ш. Линем, которые вывели формулу для общего случая (см. упр, 11-13): Алгоритм Н (Бинарное слияние).
Н1. Если т или п равно О, прекратить выполнение алгоритма. В противном случае, если т > п, установить 1 <- (!8(т/п)) и перейти к псагу Н4. В противном случае установить С с- (!8(п/т)) . Н2. Сравнить .4:В„+1 3 . Если А меньше, то установить п с- и — 2' и вернуться к шагу Н1. НЗ, Используя бинарный поиск (который требует ровно 1 дополнительных сравнений), вставить А в нужное место среди (В„+~ з,..., В„).
Если ?с максимальное и такое, что Вь < А, установить т с — т — 1 и п+- !с. Вернуться к шагу Н1. Н4. (Шаги Н4 и Н5 подобны Н2 и НЗ, но переменные т и и., А и В меняются ролями.) Если В„< А +, з, установить т с — т — 2' и вернуться к шагу Н1. Н5. Вставить В„в нужное место среди элементов А. Если !с максимальное и такое, что .4ь < В„, установить т с — й н п с — п — 1. Вернуться к шагу Н1.
) В качестве примера работы этого алгоритма в табл. 2 показан процесс слияния трех ключей (087, 503, 512) с тринадцатью ключами (061, 154,...,908); в этом примере выполняется восемь сравнений. Элементы, сравниваемые на каждом спаге алгоритма, выделены полужирным шряфтом. Таблица 2 ПРИМЕР ПРИМЕНЕНИЯ МЕТОДА БИНАРНОГО СЛИЯНИЯ А В Вывод 653 677 703 765 6$3 677 897 908 897 908 897 908 897 908 897 908 897 908 89? 908 897 908 897 908 653 653 512 612 653 512 612 653 509 512 612 653 509 512 612 653 509 512 612 653 Пусть Н(т,и) — максимальное число сравнений, выполняемых алгоритмом Хуана и Линя. Чтобы вычислить Н(т,п), можно предположить, что й = п на шаге НЗ и !с = гп н» шаге Н5, поскольку при помощи инчукции по сп нетрудно доказать, что Н(гп — 1, и) < Н(т — 1, п + 1) при всех п > т — 1.
Таким образом, при т < п имеем Н(т, и) = снах(М(т, и.— 2')+1, Н(т — 1, и)+1+1) при 2'т < и, < 2с+ст. Заменим п на 2и+ с (е = 0 или 1) и получим Н(т, 2п+е) = гпах (Н(т, 2п+с — 2'+') + 1, Н(т — 1, 2п+с)+3+2) при 2'т < и < 2'+'т. Отсюда вытекает, если применить индукцию по и, что (17) Н(т,2и+с) = Н(т,п) + т при т < и и с = 0 или 1. (18) 087 503 $12 087 503 $12 087 503 $12 087 503 512 087 503 087 $03 087 087 061 154 170 275 061 154 170 275 061 154 170 275 061 154 170 275 061 154 170 275 061 154 170 275 061 154 170 275 061 154 170 061 087 154 170 426 509 612 426 509 612 426 $09 612 426 509 612 426 509 426 509 426 503 275 426 503 275 426 503 703 765 677 703 765 677 703 765 677 703 765 677 703 765 677 703 765 677 703 765 677 703 765 Легко видеть также, что Н(т,и) = т+ и — 1, если т < и < 2т.
Следовательно, многократное применение формулы (18) даст нам обпьую формулу Н(т,и) = т+ (и/2') — 1+ 1т при ги < и, 1 = (!8(и/тЦ. (19) Отсюда следует, что Н(ги, и) < Н(т, и+1) для всех и > т, что подтверждает нашу гипотезу, полученную по индукции применительно к шагу НЗ. Полагая т = аьь и д = !8(и/т) — 1, найдем Н(ои, и) = аи(1 + 2 — 9 — !8 а) + О(1) (20) при и -ь оо.
Из формул 5.3,1 — (36) известно, что 1.9139 < 1+ 2е — д < 2. Следо- вательно, (20) можно сравнить с теоретико-информационной нижней оценкой (3). Хуан и Линь доказали (см. упр. 17), что Гт+ и', Н(т,и) < !8~ / +ьшп(т,п). (21) М(т,и) < М(т, (и./2)) + гп. (22) Это и в самом деле так (см. упр. 19).
Твблицьь значений функции М(ьиь и) позволяют предположить, что, возможно, имеют место и другие соотношения, такие, как М(го+1, и) > 1+ М(т, и) > М(т, и+1) при т < и; М(т+1, п, + 1) > 2 + М(т, и); (23) (24) но в настоящее время не известно никаких доказательств этих неравенств. УПРАЖНЕНИЯ 1. (15) Найдите любопытное соотношение, которое связывает функцию М(т, и) и функцию 5, определенную в разделе 5.3.1. [Указание.
Ресслютрите 8(т+ и).) 2. (ев) При ги = 1 любой алгоритм гляяния, не содержащий избыточных сраььнений, определяет расширенное бинарное дерево с ( „,") = и+1 внешними узлами. Докажите, что верно и обратное, т. е. каждому расширенному бинарному дереву соответствует некоторый алгоритль слияния с ьи = 1.
Алгоритхь бинарного слияния Хуана-Линя не всегда оптимален, но обладает тем неоценимым достоинством, что его довольно легко запрограммировать. Он сводится к "децентрированному бинарному поиску" при ьи = 1 и к обычной процедуре слияния при ти - и, так что зто золотая середина между двумя указанными методами. Кроме того, во многих случаях он леляегися оптимальным (см. упр. 16). Дальнейшее совершенствование алгоритма описано в работах Р.
К. Нв ап8, О. Ль. ОепгзсЬ, Х4СМ 20 (1973), 148-159; О, К. МапасЬег, лАСМ 26 (1979), 434 — 440; С. СЬгЫеп, РОСБ 19 (1978), 259-266. В последней из них Кристен (СЬпзтеп) описал процедуру слиянии, названную им /огшаи)-еез1ьий-!ьасйшагг1-ьизег1ьои (просмотр впереди, вставка позади), которая сокращает число сравнений примерно на т/3 по сравнению с алгоритмом Н при и/т — ь оо. Более того, метод Кристена обеспечивает нижнюю оценку .М.
(т, и) = ((11т+ и — 3)/4), если 5т — 3 < и < 7т + 2(т енеп]; следовательно, при этих условиях он оптимален. Формула (18) наводит на мысль о том, что и сама функция М, быть может, удовлетворяет неравенству 3. [М24[ Докажите, что .М.(1,и) = М(1, и) при всех и, 4. [М42) Справедливо ли неравенство,М(т, и) > [18("'~~")~ при всех т и и? б, [МЯд[ Докажите, что .М.(т, и) < .М'1(т, и+1). 6. [Мдд) Сформулированное выше доказательство теоремы К требует проверки на компьютере большого числа случаен.
Каким образом можно резко сократить число таких случаев7 7. [д![ Докажите неравенство (11). 8. [24 [ Докажите, что М(2, 8) < 6. Для этого придумайте такой алгоритм слияния двух элементов с восемью другими, который бы выполнял не более шести сравнений О. [87[ Докажите, что три элемента можно слить с шестью элементами нс более чем за семь шагов. В„(а, 1) = 1 + ш(п( плп глав(В (й — 1, Я), ,Ва в(з — й, Я)), зйвйз зп1в шах(н (з,1г — 1), зт -в(1,2 Ю)) з < в <з прн О < з < и, 0 < Я < и, в+Я > О. 13. [М42) (Р. Л.
Грэхем (Е. Ь. Ога1заш).) Покажите, что решение рскуррентного соот- ношения из упр. 12 можно выразить следующим образом. Определим функцию С(х) при 0 < х < оо такимй правилами: если 0<х< ~; если -<х<-; Б з 7 — в' если в<х<1; з 1, з + вы(8х — 5), -'С(2х — 1), О, О(х) = если 1 < х < оа. (Рнс. 38.) Поскольку В„(з,д') = В„(Я, з) и Л„(О,Я') = М(1,1), можно считать, что 1 < з < Я < и. Пусть р = [18 з!, д = [18 Я), г = [18 и) н пусть 1 = и — 2" + 1. Тогда Н„(з,д) = р+ 9+ Я„(з, 1) + Т (з',1), где функции Яь и Т принимают значения 0 илн 1: д < г или (1 — 2г > и и з' — 2' > и), р<гили(1> в2' сиз — 2'>а), Я (з, 1) = 1 тогда н только тогда, когда Т„(з,я') = 1 тогда н только тогда, когда где и = 2" 0(1/2е) и е = 2" ~зз(1/2" з).
10. [ЯЯ) Докажите, что пять элементов можно слить с девятью не более чем за двенадцать шагов. [Указание. Опыт введения соперника подсказывает, что начать нужно со сравнения Аз .'Вз, а затем, если Аз < Вз, попытаться сравнить Аз.'Вв.) 11. [М40[ (Ф, Хуан н Ш. Линь.) Пусть дзв = [2 — ), дзвв.з = [2 — [ при к > О, так что (дв,дпдз, .) = (1,1,2,3,4,6,9,13,19,27,38,54,77,...). Докажите, что для слияния двух элементов с дз элементами требуется в худзвем случае более чем 1 сравнений, однако слить два элемента с у — 1 можно не более чем за 1 шагов.
[Указанне. Покажите, что если и = дз или и = дз — 1 н если нам нужно слить (Аы Аз) с (Вм Вз,..., В ) за 1 сравнений, то наилучшее первое сравнение — это Аз; Вв,, [ 12. [М81[ Пусть В (йд) — — наименьшее число сравнений, необходимое для сортировки различных объектов (а,д,Хм,.,,Х„), если заданы соотношения а < В, Хг < Хз « Х, а < Х, з, д > Л„у. (Условие а < Хьы или )Я > Х „теряет смысл, если 1 > и илн .1 > и. Поэтому В„(и, и) = М(2, и).) Ясно, что й„(0, О) = О.
Докажите, что 1.0 атз 0.8 ад 0.5 ал 0.3 а.г ал Б.а 0.0 0.1 0.2 0.3 0.4 0.5 0.0 0.7 0.8 0.0 1.0 1.1 1.2 ),Б Рис. 38. Функции Грэхема (скс упр. 13). (Это, быть может, самое сложное рекуррентное соотношение из всех, которые, возможно, когда-либо будут решены!) 14. [41] (Ф, К Хуан.) Пусть йзь = Я 2" ] — 1, азию = Ьэь +3. 2ь з, Ьзь+э = [ —" 2" — 7] при )г > 3 и начальные значения подобраны так, что (Ье,)п,йлю ) = (1,1,2,2,3,4,5,7,9,11,14,18,23,29,38,48,б0,7б,...). Докажите, что М(3, Ь~) > 1 и М(З, М вЂ” 1) < 1 при всех 1, определяя таким образом точные значения М(3, п) для всех и.
15. [19] На шаге Н1 алгоритма бинарного слияния может потребоваться вычислить значение [)8(п?ш)] при п > т. Как можно легко вычислить это значение, не применяя операций деления и взятия логарифма? 16. [18] При каких гп и я, 1 < пг < и < 10, оптимален алгоритм бинарного слияния Хванга и Шень Линя? 17.
[М25] Докажите неравенство (21). [Указание. Это неравенство не очень жесткое.] 18. [М40] Исследуйте среднее число сравнений, выполняемых алгоритмам бинарного слияния. ь 19. [28] Докажите, что функция М удовлетворяет неравенству (22). 20. [80] Покажите, что если М(т, п+1) < М(ил+1, и) при всех ш < и, то М(т, и+1) < 1+ М(т, и) при всех гл < и. 21. [М47] Докажите или опровергните соотношения (23) и (24). 22. [М48] Исследуйтс минимальное среднее число сравнений, необходимых для слиянвя т элементов с и элементами.
23. [МЗЗ] (Э. Рейнгольд (Е. Не)вбо)д).) Пусть (Ам, А ) и (Вм..., В„) —.— множества, содержащие по и элементов. Рассмотрите алгоритм, который пытается проверить наличие роеенсглва между множествами исключительно путем сравнений равенства элементов этих множеств. Таким образом, в процессе выполнения алгоритма задаются вопросы наподобие "А, = В, 7ь при некоторых 1 и 7' и выбирается дальнейший путь вычислений в зависимостгг от того, был ли ответ положительным или отрицательным. Определив подходящего соперника, докажите, что любой такой алгоритл1 в наихудшем глучае будет вынужден выполнить не менее эп(п+ 1) сравнений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
