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