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