Несложная модификация этого доказательства дает аналогичную формулу

М{т,т+1) = 2т при m > 0. (6)

Определение нижних оценок. Теорема М показывает, что "теоретико-информационная" нижняя оценка (2) может сколь угодно далеко отстоять от истинной нижней границы; таким образом, метод доказательства теоремы М дает нам еще один способ нахождения нижних оценок. Такой метод доказательства часто рассматривается как порождение соперника, советы которого принуждают алгоритм работать как можно медленнее. Когда алгоритм слияния решает сравнить элементы Af.Bj, соперник так определяет судьбу сравнения, что вынуждает алгоритм избрать наиболее трудный путь. Если бы мы смогли придумать подходящего соперника, то смогли бы убедиться в том, что всякий правильный алгоритм слияния должен вьшолнить довольно мало сравнений.

Мы будем использовать соперников с ограниченными возможностями, воздействие которых лимитировано заранее заданными результатами некоторых сравнений. В методе слияния, находящемся под воздействием соперника с ограниченными возможностями, ограничения считаются неизвестными, и поэтому выполняются все необходимые сравнения даже в том случае, когда их результат предопределен. Например, в доказательстве теоремы М мы ограничили все результаты сравнений условием (5), тем не менее в алгоритме слияния нельзя воспользоваться этим обстоятельством, чтобы избежать хотя бы одного сравнения.

Ограничения, которые мы будем использовать в следующем ниже анализе, относятся к левому и правому концам массивов. Левые ограничения обозначаются следующими символами:

. (нет ограничения слева),

\ (результаты всех сравнений не должны противоречить условию Ai < Bi),

I (результаты всех сравнений не должны противоречить условию А\ > Bi). Аналогично правые ограничения обозначаются следующими символами:

. (нет ограничения справа),

\ (результаты всех сравнений не должны противоречить условию А < Вп),

I (результаты всех сравнений не должны противоречить условию Am > Вп)-

Существует девять типов соперников, обозначаемых символами ХМр, где Л - левое ограничение, ар - правое. Например, соперник \М\ должен говорить, что Ai < Bj и Ai < Вп\ соперник -М- не подчиняется никаким ограничениям. При некоторых малых значениях тип может не существовать соперников с ограниченными возможностями некоторых типов; при m = 1, очевидно, не может быть соперника \М/.

Займемся теперь построением весьма сложного, но чрезвычайно коварного соперника для слияний. Он не всегда порождает оптимальные результаты, но дает нижние оценки, которые охватывают множество интересных случаев. Предположим, заданы т и п, а также левые и правые ограничения Лир. Пусть соперника спрашивают, какой из двух элементов {Ai или Bj) больше. Соперник может, вообще говоря, применить б стратегий приведения задачи к случаю меньшего значения т + п-

Стратегия А{к, i) для i<k<m,ul<l<j. Ответить, что Ai < Bj,vl потребовать, чтобы последующие операции осуществляли слияния {Ai,Ак] с {Bi,...,Bj-i} и [Ak+i,..., Am] с {Bi,... ,Вп}. Тогда последующие сравнения Ap-.Bq дадут такие результаты: Ар < Bq, если р < к и q > I; Ар > Bq, если р > к и q < I; они будут управляться соперником {к,1-1,Х,.), если p<kuq<l, и соперником {т.-к, п+1-l, .,р), если р > к и q > I.

Стратегия В{к,1) для i<k<mul<l<j. Ответить, что Ai < Bj,u потребовать, чтобы последующие операции осуществляли слияния {Ai,..., Ак} с {Bi,..., Bi} и {Ак+1,. . ,Ат} с {Bi,Bn} при условии Ак < Bi < Ак+1- (Обратите внимание на то, что Bi присутствует в обоих списках, подлежащих слиянию. Условие Ак < Bi < Ак+1 обеспечивает такое положение, при котором слияние одной пары массивов не может дать никакой информации, которая бы помогла при слиянии другой пары.) Тогда последующие сравнения Ap-.Bq дадут такие результаты: Ар < Bq, если р <к w q > I; Ар > Bq, если р > к и q < I; они будут управляться соперником (А;,,Л, \), если p<kuq<l,u соперником (т.-к, п+1-l, /, р), если р > к и q > I.

Стратегия С{к,1) для i<k<mul<l<j. Ответить, что Ai < Bj, и потребовать, чтобы последующие операции осуществляли слияния {Ai,... ,Ак} с {Bi,..., и {Ак,...,Ат} с {Bi,...,Bn} при условии, что < Ак < Bi. (Эта стратегия

аналогична стратегии В, но массивы Aw. В меняются ролями.)

Стратегия А{к, I) для 1 < к < i и j < I < п. Ответить, что Ai > Bj, и потребовать, чтобы последующие операции осуществляли слияния {Ai,..., Ak-i} с {Bi,..., В/} и {Ак, -.., Am} с {Bi+i,..., Bn}. (Эта стратегия аналогична стратегии А.)

Стратегия В{к,1) для l<k<iuj<l<n. Ответить, что Ai > Bj, и потребовать, чтобы последующие операции осуществляли слияния {Ai,... ,Ak-i} с {Bi,...,Bi} и {Ак,...,Ат} с {Bi,...,Bn} при условии Ак-1 < Bi < Ак- (Эта стратегия аналогична стратегии В.)

Стратегия С{к, I) для l<k<iuj<l<n. Ответить, что Ai > Bj, и потребовать, чтобы последующие операции осуществляли слияния {Ai,...,Ak} с {Bi,..., Bi} и {Ак,...,Ат} с {Bi+i,...,Bn} при условии Bi < Ак < Вг+ь (Эта стратегия аналогична стратегии С.)

В случаях, которые перечислены ниже, приведенные выше стратегии не могут применяться из-за налагаемых ограничений.

Стратегия Не должна применяться, если

А{к,1),В{к,1), С{к,1) Л = /

А(1,/), В(1,/), С(1,/) А = \

А{т,1),В{т,1),С{т,1) р = /

А{к,п),В{к,п),С{к,п) р = \

Обозначим через ХМр{т,п) максимальную нижнюю оценку, которую можно получить при помощи соперника из описанного выше класса. Если первое сравнение есть Ai.Bj, то каждая стратегия, если она применима, дает неравенства, связывающие эти девять функций, а именно:

A{k,l): Шр{т,п) > 1 + XM.{k,l-l) + .Mp(m-k,n+l-iy,

B{k, I): \Mp(m, n) > 1 + \M\(k, I) + /Мр{т-к, n+l-/);

С{к,1): XMp{m,n) > 1 + XM/{k,l-l) + \Мр{т+1-к,п+1-1);

A{k,l): XMp{m,n) > 1 + XM.{k-l,l) + .Mp{m+l-k,n-l);

B{k,l): XMp{m,n) > 1 + XM\{k-l,l) + /Mp{m+l-k,n+l-l);

C{k, I): XMp(m,n) > 1 + AM/(ifc,/) + \Mp(m+l-k,n-l).

Для фиксированных г и j соперник примет ту стратегию, которая максимизирует нижнюю оценку, задаваемую правыми частями неравенств, если к и I лежат в пределах, определенных для г и j. Таким образом, ХМр{т,п) есть минимум этих нижних оценок по всем 1<г<ти1<7<п. Если т или п равно О, то и значение функции ХМр{т,п) равно 0.

Пусть, например, т = 2ип - 3, а. наш соперник не ограничен. Если первым выполняется сравнение AiiBi, то соперник может принять стратегию А(1,1), в результате чего потребуется еще .М.(0,1) + .М.(2,2) = 3 сравнения. Если первым выполняется сравнение AiiB, то он может выбрать стратегию В(1,2) и тогда потребуется еще .М\(1,2) + /М.(1,2) = 4 сравнения. Независимо от того, какое сравнение Ai-.Bj было сделано первым, соперник гарантирует выполнение еще, по крайней мере, трех сравнений. Следовательно, .М.(2,3) = 4.

Не так просто вьшолнить эти вычисления вручную, ио компьютер позволяет довольно быстро получить таблицу значений функций ХМр. Эти функции обладают некоторыми очевидными свойствами симметрии

/М.{т,п) = .М\{т,п) = \M.(n,m) = .М/{п,т), (7)

позволяющими свести наши девять функций всего лишь к четырем:

.М.{т,п), /М.{т,п), /М\{т,п) и /М/{т,п).

В табл. 1 приведены значения для всех т,п < 10. Наш соперник для слияний определен таким образом, что

.М.{т,п) < М{т,п) при всех т,п>0. (8)

Данное соотношение содержит в качестве частного случая теорему М, поскольку при \т - п\ <1 наш соперник изберет простую стратегию этой теоремы.

Рассмотрим теперь несколько простых соотношений, которым удовлетворяет функция М:

М{т,п) = М{п,т); (9)

М{т,п) < М{т,п+1); (10)

М{к+т,п) < М{к,п) +М{т,п); (11)

М(т, п) < max(M(m,n-l) + 1, M(m-l,n) + 1) при m > 1, n > 1; (12) M(m,n) < max(M(m,n-2) + 1, Л/(т-1,п)+ 2) при m > 1, n > 2. (13)

Соотношение (12) следует из обычной процедуры слияния, если начать со сравнения элементов Ai.Bi. Соотношение (13) выводится аналогично, только сначала сравниваются Ai .В2; если Ai > В2, то нужно еще М{т,п-2) сравнений, если же Ai < В2, то можно вставить Ai в соответствующее место и слить {Лг, -.., Am} с {Bi,..., В„}.