AOP_Tom3 (1021738), страница 181
Текст из файла (страница 181)
На самом деле это типичное применение принципа "наименьший из включенных первым исключается" и приоритетной очереди. з(ажно хранить ключи в пирамиде и вообще не использовать са. Дальнейшее обсуждение приводится в разделе 5.4.1. 2. Пусть С числа сравнений; тогда С = гл+ и — 8, где а — количество элементов, передаваемых на шаге М4 или Мб. Как легко видеть, вероятность тога, чта 8 > э, равна при 1 ~ о < т + и; Ь = 0 при о > гп + и. Следовательно, математическое ожидание величины Я есть р „= 9~+до+ = т/(и+1)+п/(т+1) (ср. с упр 3.4.2 — 5, 6), а дисперсия равна а~„„= (д~+Здз+ 5дз+ ) — р~„„= т(2т+ и)/(и+ 1)(а+ 2) +(т+ 2п)п/(т+ 1)(т+ 2) — р~ „.
Таким образом, С = (ш1п шш(т,п), аее т->и — р „, шах т+и — 1, беки „). Для случая, когда гп = и, среднее значение первым нашел Х, Нэглер (Н ~аб(ег) (САСМ 3 (1960), 618-620); асимптотическое выражение для него имеет вид 2п — 2 -~- О(п '), а выражение для стандартного отклонения — чг2 + О(п ').
Таким образом, С недалеко отклоняется от сноего максимального значения. 3. М2'. Если К; < К„перейти к шагу МЗ': если К, = К,', перейти к шагу М7'; если К, > К,', перейти к шагу М5'. М7'.Установить Кь" ( — К,', й Е- Й + 1, 1 +- 1 + 1, 1 е- 1 + 1. Если г > ЛХ, пеРейти к шагу М4'; в противном случае, если 1 > Х, перейти к шагу Мб': иначе— вернуться к шагу М2'. (Соответствующим образом изменяются и другие шаги алгоритма М. И опять исчезнет необходимость анализировать особые случаи, если в конец обоих массивов добавить искус— ственные ключи Км, = К~ч, = оо в конце файла.) 4.
Последовательность элементов, появляющихся с течением времени в'фиксированном внутреннем узле дерева выбора, получается путем слияния последовательностей элементов, появляющихся в узлах -- потомках этого узла. (В разделе 5.2.3 рассматривается выбор наибольшего элемента, на его анализ с тем же успехом можно было провести и для обратного отношения порядка.) Таким образам, операции, которые осуществляются при выборе из дерева, по существу, те же самые, что и при слиянии, но выполняются онн в другом порядке и с использованием других структур данных.
Другие общие черты слияния и выбора из дерева рассмотрены в упр 1 Заметим, что Х-путевое слияние одноэлементных массивов это сортировка посредством выбора; сравните также четырехпутевое слияние (А, В, С, Р) с двухпутевым слиянием (А, В), (С, Р), а затем с (.4В, СР). 5. На шаге Хб всегда К, < К, ~ < К,; на шаге г410 всегда К, < Кз.ь~ < К,. 6. 2641081412 1615 11 1379351.
После первого просмотра имеем 1256781314161512 1110943 (две из предполагаемых четырех ступенек вниз исчезли). Эту возможность заметил Д. А. Белл (1). А. Бей) (см. Сагир. Х 1 (1958), 74). Из-за наличия не совсем предсказуемых ситуаций наподобие этой попытки точно проанализировать алгоритм Х почти безнадежны. 7. (18%), если )У > 1. (Задумайтесь над тем, сколько раз нужно удвоить значение р, прежде чем оно станет > )У.) 8. Если Х не кратно 2р, то при такам просмотре встретится одна более короткая серия и она всегда будет находиться где-то в середние.
Пусть ее длина равна 1, 0 < 1 < р. На шаге 812 обрабатывается ситуация, когда короткая серия должна быть "слита" с пустой серией, т. е, 1 = 0; в противном случае мы, па существу, получим х: < хз « хр (9, » . 9ь Если г < уь та левая серия будет обработана первой и от шага 86 после пересылки хр мы перейдем к шагу 813 С другой стороны, если хг > йь то по отношению к правому подмассиву будет искусственно имитировано завершение обработки, но К, = хр никогда не будет < К; на шаге 83! Таким образом, во всех случаях из шага 86 мы, в конце концов, попадем на шаг 813. 10. Например, в алгоритме М можно сливать элементы х,; ~ .. х,+„, с хгь,„.ы ., хгь„„.„ и помещать результат в позиции хш ..
х ь„массива, не создавая при этом никаких конфликтных ситуаций, если только 2 > и. Приложив некоторые усилия, зту идею можно развить настолько, что для всей сортировки потребуется Х + 20кл' ' ячеек. Но па сравнению с алгоритмом 8 такая программа кажется довазьно сложной. (См. Сашр. Х 1 (1958), 75; см. также Л.
С. Лозинский, Кибернетика 1,3 (1965), 58-62.) 11. Да, Это можно показать, например, рассмотрев родство с методом выбора из дерева, упомянутое в упр. 4. Но алгоритмы Х и Б, очевидно, неустойчивы. 12. Установять Ро е- 1, 1 1- »У + 1; затем при р = 1, 2....., 1»' — 1 выполнить следующие действия.
Если Кр < Кр+1, установить Рр 1- р + 1; в противном случае установить б» +- †(р + 1), 1» — р. И наконец, установить |1 1- О, бя 1- О, Ли+1 +- !Ел+1~. (Устойчивость сохраняется. Число просмотров равно (18 г), где г — числа восходящих серий в начальном массиве. Точное распределение величины г проанализировано в разделе 5.1.3. Ыожно сделать вывод о том, что при использовании связного распределения памяти "естественное" слияние предпочтительнее »простого", хотя при последовательном распределении наблюдалась обратная ситуация,) 13.
При Ю > 3 время выполнения программы равно (11А+бВ+ЗВ'+9С+2Сп+4Р+51»'+ 9) и, где А — число просмотров, В = В' + В" — число выполненных операций слияния подмассивав, В' — число таких слияний, в которых р-подмассив был обработан первым, С = С + С» —. число выполненных сравнений, С вЂ” число сравнений с результатом Кр < и К», Р = Р + Р— число элементов, остававшихся в подмассивах, после того как олин подмассив был исчерпан, Р' — — число таких элементов, принадлежащих 9-подмасснву.
Для табл. 3 ил»еем А = 4, В' = 6, В" = 9, С' = 22, С" = 22, Р' = 10, Р" = 10; суммарное время = 761и. (Конкурирующая программа 5.2.!Е требует только 433в, если внести изменения, описанные в упр. 5.2.1-33. В результате приходим к выводу, что слияние не особенно эффективно при малых М.) Алгоритм Ь выпщшяет ряд операций слияния падмассивов, размеры которых (т, и) можно определить следующим образом. Пусть в двоичной системе счисления Х вЂ” 1 = (Ь» .
51Ьа)1. Выполняется (Ь»... Ь, 1)1 "обычных" слинний, таких, что (т, и) = (21, 21) при 0 < / < Ь. Имеются также "особые" слияния, такие, что (гл и) = (2', 1+ (Ь, 1... Ьо)г), если только Ь1 = 1, при 0 < / < Ь. Например, при Ж = 14 выполняется шесть обычных слияний (1, 1), три обычных слияния (2,2), одно обычное слияние (4,4); особые слияния выполняются с подмассивами размере»1 (1, 1), (4, 2), (8, 6). Мультимножество ЛХм размеров слияний (т, и) можно также описать рекуррентным соотношением ЛХ1 = 9; М,»э, = ((2",г)) Ю Мр» Ы ЛР при О < г < 2". Отсюда заключаем, что независимо от распределения, характеризующего исходный массив, А = (18»У), В = 1»' — 1. С'+ Р" = 2» еЬ 21(1+ 1/), С" + Р' = ~ » Ь (1+ 2~(11+ Ь,+1 + + Ь»)).
Следовательно, только параме»ры В~, С~, Р нуждаются в дальнейших исследованиях. Если исходный массив случаен, то каждая операция слияния удовлетворяет условиям упр. 2 и нг зависит от выполнения других аналогичных операций слияния, так что распределении параметров В~, С~, Р' являются "свертками" их распределений для каждого отдельного слияния подмассивов. Средние значения для такой операции равны В' = и/(гл + п), С' = тп/(и -> 1), Р' = и/(гп + 1), Чтобы получить точные средние значения, достаточно просуммировать эти величины по всевозможным подходящим парам (т, и). Если Х = 2, то имеет место простейшая ситуация: Вп~ = —,В, С„„, = 2С, „С+ Р = » 1 ! 1 Й»У и Р, = 2' п»(2» 121/(21 ' + 1)) = о/1»'+ 0(1), где значение 1 1 ~- 1 о = = 11+ — — 27 с» 2п.»1 2 с г4» >а п>1 = 1.26449 97803 48444 20919 13197 47255 49848 25577- можно вычислить с высокой точностью, как в упр.
5.2.3-27. Этот частный случай проанализировали Э. Глисои (А. О(еазоп) [неопублнкаваиа, 1956) и 5Ь Нэглер (Н. Ха81ег) (САСМ 3 (1960), 618 †6). 14. Чтобы получить максимальное значениепараметра С, достаточна в упр. 13 положить !гз = В, (Детальный анализ алгоритма 1. выполнен в рабате Ч~. Раппу, Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
