Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 80
Текст из файла (страница 80)
3. М2'. Если К < К', перейти к шагу МЗ'; если К, = К,', перейти к шагу М7': если К, > К';, перейти к шагу М5'. МТ'. Усзановить Кэ' <- К,', й е- й + 1, 1 +- 1+ 1, ! е — 7' + 1. Если 1 > 51, пеРейти к шагу М4'; в противном случал, если у > 51, перейти к шагу Мб'; иначе— вернуться к шагу М2'. 5 (Соответствующим образом изменяются и другие шаги алгоритма М. И опять исчезнет необходимость анализировать особые случаи, если в конец обоих массивов добавить искусственные ключи Кмь, — — К,'... = оо в конце Файла.) 4.
Последовательность элементов, появляющихся с течением времени в" фиксированном внутреннем узле дерева выбора, получается путем слияния последовательностей элементом, появляющихся в узлах — потомках этого узла. (В разделе 5.2.3 рассматривается выбор иаи6ольшсго элемента, но его анализ с тем же успехом можно было провести и для обратного отношения порядка.) Таким образом, операции, которые осуществляются при выборе из дерева, по существу, те же самые, что и при слиянии, ио выполняются оии в другом порядке и с использованием других структур данных.
Другие общие черты слияния и выбора из дерева рассмотрены в упр. 1. Заметим, что г7-путевое слияние одноэлементных массивов -- это сортировка посредством выбора; сравните также четырехпутевое слияние (А, В, С, В) с двухпутевым слиянием (А,В), (С, В), а затем с (АВ, СВ), 5. На шаге Хб всегда К, < К; ~ < К~; на шахе Х10 всегда К < К ~~ < К,. 6. 26410814121615111379351. После первого просмотра имеем 1256781314161512 1110943 (две из предполагаемых четырех ступенек вниз исчезли).
Эту возможность заметил Д. А. Белл (П. А. Ве!!) [см. Сошр. Х 1 (1958), 74]. Из-за наличия не совсем предсказуемых ситуаций наподобие этой попытки точно проанализировать алгоритм Н почти безнадежны. 7. [)857], если г7 > 1. (Залумайтесь над тем, сколько раз нужно удвоить значение р, прежде чем оно станет > Х.) 8. Если Х не кратно 2р, то при таком просмотре встретится одна более короткая серия и она всегда будет находиться где-то в середине. Пусть ее длина равна 1, 0 < ! < р, На шаге 812 обрабатывается ситуация, когда короткая серия должна быть "слита" с пустой серией, т. е.
1= 0; в противном случае мы, по существу, получим х, < хз « . хг ! у, » йь Если хр < рм то левая серия будет обработана первой и от шага 86 после пересылки хр мы перейдем к шагу 813. С другой стороны, если х > рм то по отношению к правому подмассиву будет искусственно имитировано завершение обработки, но Кз = х„никогда не будет < К, иа шаге 83! Таким образом, во всех случаях из шага 86 мы, в конце концов, попадем на шаг 813.
10. Например, в элгоритые М можно сливать элементы х,ш...х1+ с х,е +~... хэе и помещать результат в позиции х~...х е массива, не создавая при этом никаких конфликтных ситуаций, если только 1 > и. Приложив некоторые усилия, зту идею можно развить настолько, что для всей сортировки потребуется Х + 2!'ел! ' ячеек. Но по сравнению с алгоритмом 8 такая программа кажется довольно сложной. [См.
Сошр. Х. 1 (1958), 75; см. также Л. С. Лозинский, Кибернетика 1., 3 (1965), 58-62.] 11. Да. Это можно показать, например, рассмотрев родство с методом выбора из дерева, упомянутое в упр. 4. Но алгоритмы Х и 8, очевидно, неустойчивы. 12. Установить Ьо ь- 1, 1 ь- К+ 1; затем при р = 1,2,, Х вЂ” 1 выполнить следующие действия. Если К„ < Крец установить Ь„ +- р + 1; в противном случае установить 1„ +- -(р + 1), 1+- р. И наконец, установить Бс +- О, Ья +- О, Ьл+~ +- )Ья+~ ). (Устойчивость сохраняется.
Число просмотров ражю (ф г), где г — число восходящих серий в начальном массиве. Точное распределение величины г проанализировано в разделе 5.1.3. Можно сделать вывод о том, что при использовании связного распределения памяти естественное" слияние предпочтительнее "простого", хотя при последовательном распределении наблюдалась обратная ситуация.) 13. При К > 3 время выполнения программы равно (11А+бВ+ЗВ'+9С+2Ся+4Р+5Ж+ 9) и, где А — число просмотров, В = В' + В" — число вмполненных операций слияния подмассивов, В' — число таких слияний, в которых р-подмасскв был обработан первым, С = С'+ С" — число выполненных сравнений, С' — число сравнений с результатом К„< Кю Р = Р' + Р" — число элементов, остававшихся в подмассивах, после того как один подмасснв был исчерпан, Р' — число таких элементов, принадлежащих д-цодмассиву.
Для табл. 3 имеем А = 4, В' = 6, В" = 9, С' = 22, С" = 22, Р' = 10„Р" ж 10; суммарное время = 76!и. (Конкурирующая программа о.2.11. требует только 433к, ести внести изменения, описанные в упр. 5.2.1-33, В результате приходим к выводу, что слияние не особенно эффективно при малых Ю.) Алгоритм Ь выполняет рид операций слияния подмассивов, размеры которых (гл, и) можно определить следующим образом. Пусть в дюичной системе счисления К вЂ” 1 = (Ьь...Ь|Ьо)г. Выполняется (Ьь...Ьаы)з "обычных" слияний, таких, что (гп,п) = (2~,2~) прн 0 < У < Е Имеются также "особые" слияния, такие, что (ш, и) = (2', 1+ (Ьз-в... Ьо)з), если только Ь~ = 1, при 0 < У < Е Например, прн Х = 14 выполняется шесть обычных слияний (1, 1), три обычных слияния (2, 2), одю обычное слияние (4, 4); особме слияния выполняются с подмассивами размером (1, 1), (4, 2), (8, 6). Иультимножество Мя размеров слияний (гл, н) можно также описать рекуррентным соотношением М1 = 9; Мз*„г = ((2, г)) Ю Мы Ш М, при 0 < г < 2 .
Отсюда заключаем, что независимо от распределения„характеризующего исходный массив, А = (18 51)а В = )У вЂ” 1 С + Р = 2,=о Ьз 2 (1 + фУ) С ' + Р' = 4"," о Ь (1+ 2 ( з У + Ьз. ~ + . + Ьь)). Следовательно, только параметры В', С, Р нуждаются в дальнейших исследованиях. Если исходный массив случаен„то вэлслая операция слияния удовлетворяет условиям упр, 2 и не зависит от выполнения другах аналогичных операций слияния, так что распределения параметров В, С, Р' являются "'свертками" их распределений для каждого отдельного слияния подмассивов.
Средние значения для такой операции равны В = н/(го+ и), С' = шп/(н+ 1), Р' = и/(т+ 1). Чтобы получить точные средние значении, достаточно просуммировать эти величины по всевозможным подходящим парам (т, и). Если Ф = 2", то имеет место простейшая ситуация: В,' = -'В, С„'„, = -'С ., С+ Р = ЙХ и Р,, = 2 .,(2ь 12~/(2~ ' + 1)) = о К+О(1), где значение 1 1 т 1 2" + 1 2 4" — 1 а>о >! = 1.
26449 97803 48444 20919 13197 47255 49848 25577- можно вычислить с высокой точностью, как в упр. 5.2.3-27. Этот частный случай проанализировали Э. Глисон (А. О!еззов) [неопубликовано, 1956] и 32 Нэглер (Н. Май)ег) (САСМ 3 (1960), 618 — 620). 14. Чтобы получить максимальное значение параметра С, достаточно в упр.
ЬЗ положить Р ж В. (Детальный анализ алгоритма Ь выполнен в работе %. Раппу, Н. Ргоб!пбег, А(йонгйписа 14 (1995), 340-354,) 15. Прсдублируйте команды реализации шагов ЬЗ, Ь4 и 1.6 для случаев, когда известно, что Ь, равно р или 9. (Алгоритм можно еще белее усовершенствовать, удалив нз внутреннего цикла присвоение з +- р (нли з +- д), просто переименовав регистры! Замените, например, строки 20 и 21 строкой 1Л)3 1ИР07,1(Ь) и продолжайте далее, считая, что р находится в 213, з — в гП, а значение переменной Ь„Ь, заведомо равно р. Имея двенадцать копий внутреннего цикле„соответствующих различным перестановкам (р, 9, г) относительно регистров (гП, г12, г13) и различной информации о Ь„можно сократить среднее время работы до 8А'!8 М+ О()1).1 16. Полученный алгоритм будет работать чуть быстрее зл1 оритма Ь (гль упр. 5.2.3-28), 17.
Рассматривайте новую запись как подмассив длиной 1. Повторяйте слияние двух панменьших подмагснвов, имеющих одинаковую длину. (Полученный алгоритм сортировки, по существу, такой же, как алгоритм Ь, только слияния подмассивов выполняются в другом порядке.) 18. Да, но это, по-видимому„очень сложно. В простейшем известном методе используется следующее искусное построение (ДАН СССР 186 (1969), 1256-1258).
Пусть н яз зги. Разделим массив на гл+ 2 "зон" Я1... Ям Я .Ь1 Я тз, гДЕ Зона Я ьз СОДЕРжит А' шод н записей, а остальные эоны содержат ровно по н записей. Поменяем местами записи зоны Я„,е1 с зоной, в которой содержится Км; теперь массив имеет внл Я1... Я А, где каждая из ЭОН Я1... Ям СадЕржнт РОВНО Н уПОрядОЧЕННЫХ ЗаПИСЕй, а А - — ВСПОМОГатЕЛЬНая Обпаетъ, содержащая з записей, где з — некоторое число из диапазона н < з < 2п. Найдем зону с нанменылим лидирующим элементом и поменяем ее местами г Я1 . Если более одной эоны имеет наименьший лидирующий элемент, выберите ту нз них, замыкающий элемент которой будет наименьшим.
(Для этого потребуется О(ш + и) операций.) Затем найдем зону со следующим по порядку лидирующим элементом и поменяем ее местами г Яз и т. д, В конце концов, за 0(гл(гл+ и)) = 0(21') операций мы перекомпонуем эти гл зон таким образом, чтобы их лидирующие элементы были упорядочены. Кроме того, в соответствии с исходным предположением о характере массива каждый из ключей в зонах Я1... Я теперь имеет не более чем н инверсий, Для слияния Я1 с Яз можно воспользоватьгл следующим трюком: поменять местами Я1 с первыми н злемеятами А' области А, а затем свить Яз с А', как обычно, но при выводе поменять местами элементы с элементами области Я1 Яз. Например, если и = 3 и х1 < у1 < хз < уз < хз < уз, то имеем следующее.
Зона 1 Начальное содержиьюе: Обмен с Я1: Обмен с х1; Обмен с у*.; Обмен с хз. Обмен с уз: Обмен с хз: Х1 ХЗ ХЗ а1 аз аз Х1 аз аз у1 аз Х1 У1 Хз Х1 У1 Х2 Х1 У1 Х2 У1 У2 Уз У1 Уз Уз У1 У2 Уз а2 у2 уз аз уз уз у2 а2 уз у2 хз уз Вспомогательная область а1 аз аз Х1 Х2 ХЗ а1 хз хз а1 хз хз а1 аз хз а1 аз хз а1 аз аз (Слияние всегда заверншется в тот момент, когда происходит обмен и-го элемента вспомогательной области.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
