2) -/tmn- Teikhm образом, с = (min m.in(m, n), ave m + n - pmn, maxm + n -1, devamn)-Для случая, когда тп = n, среднее значение первым нашел X. Нэглер (Н. Nagler) [САСМ 3 (1960), 618-620]; асимптотическое выражение для него имеет вид 2л - 2 + 0(п"), а выражение для стандартного отклонения - \/2 + 0(п"). Таким образом, С недалеко отклоняется от своего максимального значения.

3. М2. Если Ki < Kj, перейти к шагу МЗ; если Ki = Kj, перейти к шагу М7; если

Ki > Kj, перейти к шагу М5.

М7. Установить К <- Kj, k<r-k + l, ii + l, j<r-j + l. Если i > М, перейти к шагу М4; в противном случае, если j > N, перейти к шагу Мб; иначе - вернуться к шагу М2.

(Соответствующим образом изменяются и другие шаги алгоритма М. И опять исчезнет необходимость анализировать особые случаи, если в конец обоих массивов добавить искусственные ключи Км+\ = Knx = оо в конце файла.)

4. Последовательность элементов, появляющихся с течением времени вфиксированном внутреннем узле дерева выбора, получается путем слияния последовательностей элементов, появляющихся в узлах - потомках этого узла. (В разделе 5.2.3 рассматривается выбор наибольшего элемента, но его анализ с тем же успехом можно было провести и для обратного отношения порядка.) Талсим образом, операции, которые осуществляются при выборе из дерева, по существу, те же самые, что и при слиянии, но выполняются они в другом порядке и с использованием других структур данных.

Другие общие черты слияния и выбора из дерева рассмотрены в упр. 1. Заметим, что iV-путевое слияние одноэлементных массивов - это сортировка посредством выбора; сравните также четырехпутевое слияние {A,B,C,D) с двухпутевым слиянием {А, В), (С, D), а затем с [АВ, CD).

5. На шаге N6 всегда К, < Ki-i < Kj; на шаге N10 всегда Kj < Kj+i < Ki.

6. 2 6 410 8 14 12 16 15 11 13 7 9 3 5 1. После первого просмотра имеем 1 2 5 6 7 8 13 14 16 15 12 11 10 943 (две из предполагаемых четырех ступенек вниз исчезли). Эту возможность заметил Д. А. Белл (D. А. Bell) [см. Сотр. J. 1 (1958), 74]. Из-за наличия не совсем предсказуемых ситуаций наподобие этой попытки точно проанализировать алгоритм N почти безнадежны.

7. [IgiV], если N > 1. (Задумайтесь над тем, сколько раз нужно удвоить значение р, прежде чем оно станет > N.)

8. Если N не кратно 2р, то при таком просмотре встретится одна более короткая серия и она всегда будет находиться где-то в середине. Пусть ее длина равна t, О < t < р. На шаге S12 обрабатывается ситуация, когда короткая серия должна быть "слита" с пустой серией, т. е. t = 0; в противном случае мы, по существу, получим Xi < Х2 < < Хр \ yt > > yi. Если Хр < yt, то левая серия будет обработана первой и от шага S6 после пересылки Хр мы перейдем к шагу S13. С другой стороны, если Хр > yt, то по отношению к правому подмассиву будет искусственно имитировано завершение обработки, но Kj - Хр никогда не будет < Ki на шаге S3! Таким образом, во всех случаях из шага S6 мы, в конце концов, попадем на шаг S13.

10. Например, в алгоритме М можно сливать элементы Xj + l . . . Xj+rn с Xj+rn+l • • Хj+m+n и помещать результат в позиции xi .. .Хт+п массива, не создавая при этом никаких конфликтных ситуаций, если только j > п. Приложив некоторые усилия, эту идею можно развить настолько, что для всей сортировки потребуется N + 2 ячеек. Но по сравнению с алгоритмом S такая программа кажется довольно сложной. [См. Сотр. J. 1 (1958), 75; см. также Л. С. Лозинский, Кибернетика 1,3 (1965), 58-62.]

11. Да. Это можно показать, например, рассмотрев родство с методом выбора из дерева, упомянутое в упр. 4. Но алгоритмы N и S, очевидно, неустойчивы.

12. Установить Lo <- 1, t <- ЛГ + 1; затем при р = 1, 2,..., ЛГ - 1 выполнить следующие действия.

Если Кр < Кр+1, установить Lp «-р+1; в противном случае установить Lt <--(р + 1),

t -(-р.

И наконец, установить Lt <- О, Ljv <- О, Ln+i <- LAf+i.

(Устойчивость сохраняется. Число просмотров равно fig г], где г - число восходящих серий в начальном массиве. Точное распределение величины г проанализировано в разделе 5.1.3. Можно сделать вывод о том, что при использовании связного распределения памяти "естественное" слияние предпочтительнее "простого" хотя при последовательном распределении наблюдалась обратная ситуация.)

13. При ЛГ > 3 время выполнения программы равно (ПА+ЬВ + ЗВ + 9С+2С"+ iD+5N+ 9)и, где А - число просмотров, В = В + В" - число выполненных операций слияния подмассивов. В - число таких слияний, в которых р-подмассив был обработан первым, С - С + С" - число выполненных сравнений, С - число сравнений с результатом Кр < Kg, D = D + D" - число элементов, остававшихся в подмассивах, после того как один подмассив был исчерпан, D - число таких элементов, принадлежащих д-подмассиву. Для табл. 3 имеем Л = 4, В = 6, В" = 9, С = 22, С" - 22, D = 10, D" - 10; суммарное время = 761и. (Конкурирующая программа 5.2.1L требует только 433и, если внести изменения, описанные в упр. 5.2.1-33. В результате приходим к выводу, что слияние не особенно эффективно при малых ЛГ.)

Алгоритм L выполняет ряд операций слияния подмассивов, размеры которых (т, п) можно определить следующим образом. Пусть в двоичной системе счисления Л - 1 = (bfc ... 6160)2. Выполняется (6 ... 6 ,+i)2 "обычных" слияний, таких, что (m,n) = (2-, 2-) при О < j < fc. Имеются также "особые" слияния, такие, что (т, п) = {2\ 1 + (6j i ... 60)2), если только bj = 1, при О < j < fc. Например, при N = 1А выполняется шесть обычных слияний (1,1), три обычных слияния (2,2), одно обычное слияние (4,4); особые слияния выполняются с подмассивами размером (1,1), (4, 2), (8, 6). Мультимножество Mn размеров слияний (т, п) можно также описать рекуррентным соотношением

Mi=0; М2»,+,. = {(2*,г)} ЫМг», ttlMr при0<г<2*.

Отсюда заключаем, что независимо от распределения, характеризующего исходный массив, А = figiVl, В = iV- 1, С + D" = -=0bjV{l + С" + D= =0bji + 2(j + 6j+i + • • • + 6*)). Следовательно, только параметры В, С, D нуждаются в дальнейших исследованиях.

Если исходный массив случаен, то каждая операция слияния удовлетворяет условиям упр. 2 и не зависит от выполнения других аналогичных операций слияния, так что распределения параметров В, С, D являются "свертками" их распределений для каждого отдельного слияния подмассивов. Средние значения для такой операции равны В = п/{т + п), С = тп/{п + 1), D = п/{т + 1). Чтобы получить точные средние значения, достаточно просуммировать эти величины по всевозможным подходящим парам (m,n).

Если ЛГ = 2*, то имеет место простейшая ситуация: Bave = 5, Give = Cave, с + D = fcЛГ и Dave = Е)=1 (2*"27(2-- + 1)) = аЛГ + 0(1), где значение

п>0 п>1

= 1.26449 97803 48444 20919 13197 47255 49848 25577-

можно вычислить с высокой точностью, как в упр. 5.2.3-27. Этот частный случай проанализировали Э. Глисон (А. Gleason) [неопубликовано, 1956] и X. Нэглер (Н. Nagler) [САСМ 3 (1960), 618-620].

14. Чтобы получить максимальное значение параметра С, достаточно в упр. 13 положить D = В. [Детальный анализ алгоритма L выполнен в работе W. Раппу, Н. Prodinger, Alg-orithmica 14 (1995), 340-354.]

15. Продублируйте команды реализации шагов L3, L4 и L6 для случаев, когда известно, что Ls равно р или q. [Алгоритм можно еще более усовершенствовать, удалив из внутреннего цикла присвоение s <- р (или s д), просто переименовав регистры! Замените, например, строки 20 и 21 строкой LD3 INPUT, 1(L) и продолжайте далее, считая, что р находится в г13, s - в гИ, а значение переменной Ls, L, заведомо равно р. Имея двенадцать копий внутреннего цикла, соответствующих различным перестановкам (р, q, г) относительно регистров (гП, г12, г13) и различной информации о La, можно сократить среднее время работы до 8iVIg iV -Ь 0(N).]

16. Полученный алгоритм будет работать чуть быстрее алгоритма L (см. упр. 5.2.3-28).

17. Рассматривайте новую запись как подмассив длиной 1. Повторяйте слияние двух наименьших подмассивов, имеющих одинаковую длину. (Полученный алгоритм сортировки, по существу, такой же, как алгоритм L, только слияния подмассивов выполняются в другом порядке.)

18. Да, но это, по-видимому, очень сложно. В простейшем известном методе используется следующее искусное построение [ДАН СССР 186 (1969), 1256-1258]. Пусть п к у/М. Разделим массив на m -Ь 2 "зон" Zi ... Zm Zm+i Zm+2, где зона Zm+2 содержит N mod п записей, а остальные зоны содержат ровно по п записей. Поменяем местами записи зоны Zm+i с зоной, в которой содержится Rm; теперь массив имеет вид Z\ ... Zm А, где каждая из зон Zl ... Zm содержит ровно п упорядоченных записей, а А - вспомогательная область, содержащая s записей, где s - некоторое число из диапазона п < s < 2п.

Найдем зону с наименьшим лидирующим элементом и поменяем ее местами с Zi. Если более одной зоны имеет наименьший лидирующий элемент, выберите ту из них, замыкающий элемент которой будет наименьшим. (Для этого потребуется 0{т + п) операций.) Затем найдем зону со следующим по порядку лидирующим элементом и поменяем ее местами с .2 и т. д. В конце концов, за 0{т(т + п)) = 0[N) операций мы перекомпонуем эти т зон таким образом, чтобы их лидирующие элементы были упорядочены. Кроме того, в соответствии с исходным предположением о характере массива каждый из ключей в зонах Zl ... Zm теперь имеет не более чем п инверсий.

Для слияния Zl с Z2 можно воспользоваться следующим трюком: поменять местами Zl с первыми п элементами А области А, а затем слить Z2 с А, как обычно, но при выводе поменять местами элементы с элементами области ZiZ2. Например, если п = 3 и Xl < yi < Х2 < У2 < Хз < уз, то имеем следующее.

Зона 1 Зона 2 Вспомогательная