AOP_Tom3 (1021738), страница 6
Текст из файла (страница 6)
Стпратегия С(й,1) для т < й < т и 1 < 1 < /. Ответить, что А; < В з н потребовать, чтобы последующие операции осуществляли слияния (Ат,..., Аь) с (Вт,...,Вт т) и (Аы...,А~) с (Вт,...,Ва) при условии, что Вт т < Аг < Вт. (Эта стратегия аналогична стратегии В, но массивы А и В меняются ролями.) Стпратегия А'(й,1) для 1 < й < т и / < 1 < п. Ответить, что А, > В, и потребовать, чтобы последующие операции осуществляли слияния (Ат,..., Аь т) с (Вт,..., Вт) и (А»,...,А,„) с (Втет,.,.,В„).
(Эта стратегия аналогична стратегии А.) Стпратпегия В'(й,1) для 1 < й < т и т' < 1 < и. Ответить, что А; > В, и потребовать, чтобы последующие операции осуществляли слияния (Ат,..., Аь-т ) с (Вп...,Вт) и (А»,...,А ) с (Вт,...,В„) прн условии Аь т < Вт < Аь.
(Эта стратегия аналогична стратегии В.) Стпратегия С'(/с,1) для 1 < й < т и т' < 1 < п. Ответить, что А, > В, и потребовать, чтобы последутощие операции осуществляли слияния (Ат„..., Аг) с (Вт,,Вт) и (Аы...,Ага) с (Вт„.»,...,В ) при условии Вт < Аг < Вт.ьт. (Эта стратегия аналогична стратегии С.) В случаях, которые перечислены ниже, приведенные выше стратегии не могут применяться из-за налагаемых ограничений.
Не должна применяться, если Стратегия А(й,.1), В(й,1), С(1с,1) А'(1,1), В'(1,1), С'(1,1) А(т,1), В(т,1), С(т,1) А'(й, и), В'(й, и), С'(й, и) Л=/ Л=! р=/ Обозначим через ЛИр(т,и) максимальную нижнюю оценку, которую можно получить при помощи соперника из описанного вьппе класса. Если первое сравнение есть А;:В, то каждая стратегия, если она применима, дает неравенства, связывающие эти девять функций, а именно: /М.(т, и) = .М~(т, и) = ~ЛХ. (и,т) = .М/(и, т), позволяющими свести наши девять функций всего лишь к четырем: .М.(т, и), /ЛХ.
(т, и), /ЛХ~(т, и) и /М/(т, и). В табл. 1 приведены значения для всех т,и < 10. Наш соперник для слияний определен таким образом, что .М.(т,и) < М(т,и) при всех т,и > О. Дшпсое соотношение содержит в качестве частного случая теорему М, поскольку при ~т — сс~ < 1 наш соперник изберет простую стратегию этой теоремы. Рассмотрим теперь несколько простых соотношений„которым удовлетворяет функция М: ЛХ(т, и) = ЛХ(и, т); ЛХ(т,п) < М(т,и+1); Л1(й+т,и) < М(lс,и) + М(т,и); ЛХ(т,и) < шах(М(т,и — 1) + 1, М(т-1,и) + 1) при т > 1, п, > 1; М(сп, и) < снах(ЛХ(т,и — 2) + 1, М(т — 1,и) + 2) при сп > 1, и > 2, (9) (10) (11) (12) (13) Соотношение (12) следует из обычной процедуры слияния, если начать со сравнения элементов Ас .
Вс . Соотношение (13) выводится аналогично, только сначала сравниваются Ас. Вз: если Ас > Вт, то нужно еще ЛХ(т, и — 2) сравнений, если же .4с < Вс, то можно вставить Ас в соответствующее место и слить (Ав,..., А ) с (Вы.... В„). А(131): ЛМр(т,и) > 1+ ЛМ.(lс,( — 1) +.Мр(т-й,и+1 — !); В(131): ЛМр(ги, и) > 1 -~- ЛЛХЦй,1) + /Л1р(ги — Л, и+1 — 1); С(А,1): ЛМр(ти,и) > 1+ ЛМ/($с,1 — 1) + сМр(т+1 — Зс,и+1 — 1); А(13 1): ЛМр(га,и) > 1+ ЛЛХ (й — 1,1) + .Мр(т+1-Хс, и — 1); В(1, 1): ЛМр(т,и) > 1+ ЛМ~(Хс — 1,1) + /Мр(ос+1 — Л, и+1 — 1); С'(111). ЛМр(т, и) > 1+ ЛМ/(131) + ~,Мр(т+1 — К, и — 1).
Для фиксированных с и с соперник примет ту стратегию, которая максимизирует нижвюю оценку, задаваемую правыми частями неравенств, если Й и 1 лежат в пределах, определенных для с и у. Таким образом, ЛМр(т,и) есть минимум этих нижних оценок по всем 1 < с < си и 1 < у < и. Если т или и равно О, то и значение функции ЛЛХр(т, и) раино О. Пусть, например, т = 2 и и = 3, а наш соперник не ограничен. Если первым выполняется сравнение Ас:Вы то соперник может принять стратегию А'(1, 1), в результате чего потребуется еще ЛХ.(0,1) + .М.(2,2) = 3 сравнения. Если первым выполняется сравнение Ас .
Вэ, то он может выбрать стратегию В(1, 2) и тогда потребуется еще .М1(1,2) + /М.(1,2) = 4 сравнения. Независимо от того, какое сравнение А,:Вс было сделано первым, соперник гарантирует выполнение еще, по крайней мере, трех сравнений. Следовательно, .М. (2, 3) = 4. Не так просто выполнить эти вычисления вручную, но компьютер позволяет довольно быстро получить таблицу значений функций ЛМр.
Эти функции обладают некоторыми очевидными свойствами симметрии Таблица 1 НИЖНИЕ ОПЕНКИ Д2!Я СЛИЯНИЙ, ВЫПОЛНЕННЫХ ПРИ УЧАСТИИ СОПЕРНИКА .М. (т, и) /М.(иь и) 1 2 3 4 5 б 7 В 9 1О и 1 2 3 4 5 6 7 8 9 10 2 3 3 3 4 5 5 6 5 6 7 7 б 7 8 9 7 8 9 10 7 9 10 11 8 10 11 !2 В 1О 12 13 9 11 12 14 9 11 13 15 1 1 2 2 2 3 3 2 4 4 3 5 5 3 5 6 3 б 7 3 б В 4 6 9 4 7 10 4 7 3 3 3 4 5 5 6 7 7 7 В 9 8 9 10 В )О 11 9 10 12 9 )1 13 10 11 13 10 12 14 3 4 6 6 8 8 9 10 11 12 12 13 13 14 14 15 15 16 15 17 4 4 1 7 7 2 9 9 3 10 11 4 12 13 5 14 14 б 15 16 7 16 17 В 17 18 9 18 19 10 3 4 6 6 8 В 10 !О 11 12 12 13 13 )4 14 15 15 16 1б 17 4 4 7 7 9 9 11 11 12 13 14 15 15 16 16 17 !7 18 18 19 1 2 2 1 3 4 1 3 5 1 4 5 1 4 б 1 4 б 1 4 7 1 5 7 1 5 8 1 5 8 /57Цис и) 2 3 3 3 4 4 5 5 4 6 б 7 5 6 В В 5 7 8 10 5 7 9 10 5 8 10 11 6 В И 12 б 9 10 12 б 9 11 13 /М/(иь и) 1 1 1 4 4 4 5 б 6 7 7 8 7 9 9 8 9 11 9 1О 11 9 11 12 9 11 13 1О 12 14 1 -оо 2 — оо 3 — оо 4 — оо 5 б -со 7 -оо  — оо 9 -оо 10 -оо 3 4 б 6 В В 9 10 10 11 12 !3 12 14 13 15 14 16 15 16 1 1 4 5 7 7 9 9 10 11 11 12 13 14 14 15 15 16 15 17 1 1 ) 5 5 2 В В 3 9 10 4 11 )2 5 13 14 6 15 15 7 16 17 8 17 18 9 18 19 10 4 4 7 7 8 9 10 11 12 13 14 14 15 16 16 17 17 18 18 19 1 1 1 1 3 3 1 3 5 1 4 5 1 4 6 1 4 6 1 4 7 1 5 7 1 5 В 1 5 8 ) 2 3 4 5 6 7 8 9 10 и 1 2 3 4 5 б 7 8 9 10 Если перейти к более общему случаю, выполнив для этого сначала сравнение А1, Вы а затем испш!ьзовав двоичный поиск в случае А! < В1, увидим, что при и! > 1 и и > /с выполняется неравенство М(т,п) < шах(М(т,п — lс) +1, М(т — 1,п) + 1+ (181)).
(14) Оказывается, М(т. и) = .М.(т, и) при всех 7п,п < 10, так что в табл. 1 в действительности приведены оптилсальные значения для слияний. Это можно доказать, применяя соотношения (9) -(14), а также специальные построения для (т, и) = (2, 8), (3, б) и (ос, 9), которые приводятся в упр. 8-10. С другой стороны, такой соперник не всегда дает наилучшую возможную нижнюю оценку. Простейший пример; т = 3, и = 11, когда .М.(3, 11) = 9, а М(3, 11) = 10. Чтобы понять, где же в этом случае наш соперник "промахнулся", нужно изучить мотивы, на которых основаны его решения; при дальнейшем тщательном исследовании обнаруживается, что если (4, 7) ф (2., б), то соперник может отыскать стратегии, требующие 10 сравнений; если же (1, !) = (2, б), то ни одна стратегия не превосходит стратегию А(2,4), которая приводит к нижней оценке 1 +.М.(2,3) + .М.
(1, 8) = 9, Необходимо, но не достаточно, чтобы процесс заканчивался слиянием (А7, А ) с (В1, Вз, Вз) и (Аз) с (В4,..., В1! ); таким образом, нижняя оценка в этом случае оказывается неточной. Аналогично можно показать, что .М. (2, 38) = 10, в то время как М(2, 38) = 11, и т. д. Значит, наш соперник не достаточно искусен, чтобы справиться со случаем т = 2. Однако существует бесконечный класс значений, для которых он работает безупречно. Теорема К.
М(т, гп+2) = 2т + 1 М(т, т+3) = 2т + 2 М(т,т+4) = 2гп+ 3 при т > 2; прп т > 4; при т >6. Доказательство. На самом деле мы можем доказывать зти соотношения, заменив М на .Л!.; при малых т эти результаты были получены на компьютере, поэтому можно предполагать, что т достаточно велико. Можно также считать, что первое сравнение есть А;:В, где! < (т/2!. Если з < 1, то воспользуемся стратегией А (! 1); тогда получим .М.(т, т+й) > 1+.М (! — 1,!) +.М.(т+1 — г,т+й — !) = 2т+ И вЂ” 1, применив индукцию по И, И < 4.
Если у' > г, то воспользуемся стратегией А(1,1+1); применив индукцию по т, получим .М.(т,т+4) >1+.М.(1,г)+.М.(т — 1,т+0 — !) =2т+д — 1. 1 Первые два утверждения теоремы К получили Ф. Хванг и Ш. Линь в 1969 году. Спустя несколько лет Пол Стокмайер (Рап! 8!ос)ппеуег) и Фрэнсис Яо (Р. Р.
С. Уао) показали, что некоторые свойства этих формул можно распространить и на более общий случай. В частности, нижние оценки, выведенные стратегиями соперника, достаточно удовлетворительны для того, чтобы обеспечить значения ЛХ(т, т+Н) = 2т + с! — 1 при т > 2Ы вЂ” 2. ($!СОМР 9 (1980), 85 — 90.) Верхние оценки. Рассмотрим теперь верхние оценки функции М(т, и). Хорошие верхние оценки соответствуют эффективным алгоритмам слияния. При т = 1 задача слияния эквивалентна задаче вставки, когда имеется и+ 1 мест между элементами Вы,, ., В„, куда может попасть элемент Ам В этом случае нетрудно видеть, что любое распзиренное бинарное дерево с п+ 1 внешними узлами есть дерево для некоторого метода слияния (см. упр. 2)! Следовательно, можно выбрать оптимальное бинарное дерево, реализовав теоретико-информационную нижнюю оценку 1+ (!8п) = М(1,п) = (!8(и+1)).
(15) М(2,п) = !!8 —,",(п + 1)1 + !!8 гу(и+ 1)1. (16) Мы видели, что при т = и оптимальна обычная процедура слияния, а при т = 1 оптимальна довольно сильно отличающаяся от нее процедура бинарного поиска. Нам же нужен некоторый промежуточный метод, объединяющий в себе лучшие черты алгоритмов обычного слияния и бинарного поиска. Формула (14) наводит на мысль о следующем алгоритме (Р. К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
