AOP_Tom3 (1021738), страница 191
Текст из файла (страница 191)
01 О! 'ь', значит, для такой последовательности головок в наихудшем случае требуется не менее гп — (1ояг тп) — 1 проходов. Эта последовательность головок особенно интересна, поскольку она была использована как основа весьма остроумного сортирующего устройства, изобретенного Ф. Н. Армстронгом (Р. Х. Агшэсгопб) (см. С, Я.
Рагеш 3399333 (1965)). Пратт предполагает, что эти исходные последовательности представляют наихудший случай из возможных.) 64. При быстрой сортировке каждый ключ Кг,..., Кк сравнивается с К1; пусть А = (! ) кь < кь), В = (~ ) к, > кь». Далее метод быстрой сортировки независимо применяется к А и В. Все сравнения К,. Кг для 1' в Л и 1 в Н запрещаются как при быстрой сортировке, так и в алгоритме ограниченной однородной сортировки, но никакие другие сравнения не запрещаются в алгоритме неограниченной однородной сортировки.
В этом случае мы могли бы еще больше ограничить алгоритм, опуская случаи 1 н 2 так, что к С добавляются дуги, только если явно выполняются сравнения, и рассматривая при проверке избыточности лишь пути длиной 2. Другой способ решения этой задачи заключается в том, чтобы рассмотреть эквивалентный алгоритм вставки в дерево (раздел 5.2.2) ! который выполняет те же сравнения, что н однородный алгоритм, и в том же порядке.
65. Вероятность того, что К, сравнивается с Кал — это вероятность того, что с, других заданных ключей не лежат между К, и Кь,; это, в свою очередь, есть вероятность того, что два числа, случайно выбранные из (1, 2,, с!+2), окажутся последовательными, а именно (с, +1)/ ( ' ). (Ъ) Первые и — 1 значений сь равны нулю; затем плут (и — 2) единиц, (и-3) двоек и т. дб среднее значение, следовательно, равно 2 2 ",(и — Ь)/((с+1) =- 2 2 ь" 1((11+1)11(йч-1) — 1) = 2(н+ 1)(Н„эь — 1) — 2п.
(с) Раздвоенность, характерная для слияния, приводит к тому, что алгоритм ограниченной однородной сортировки совпадает с алгоритмом однородной сортировки для этой последовательности. Пары, содержащие вершину гь', имеют значения с, равные соответственна О, 1,...,1ь! — 2; поэтому среднее чисто сравнений точно такое же, как и при быстрой сортировке. 66. Нет. Когда гьь = 5, никакая последовательность пар, оканчивающаяся на (1,5)(1,2) (2, З)(З, 4)(4, 5), не будет требовать 10 сравнений. (Интересная проблема для исследования: найти для любого конечного А1 однородный метод сортировки, наилучший из возможных в наихудшем случае.] 67. Гил Калаи (Сь! Кв1а!) неофициально сообщил о найденном доказательстве минимальности для ограниченного случая. Он использовал метод, изложешьый в его же статье в Сгарйэ ш!11 СопьбьпасоНсэ 1 (1935), 65-79; однако само доказательство не опубликовано.
68. За каждый проход элемент может потерять не более одной инверсии, поэтому минимальное число проходов не может быть меньше максимального числа инверсий любого элемента исходной переставовки. При стратегии метода пузырька эта граница достигается, так как каждый проход уменьшает на единицу число инверсий каждого элемента, обладающего инверсиями (см. упр.
5.2.2 — 1). 5(ог бы потребоваться допочнительный проход, чтобы определить, закончена ли сортировка, но формулировка этого упражнения позволяет нам пе учитывать соображения такого рода. Возможно, наше несчастье в том, что первая теорема в изучении вычислительной сложности автоматов установила "оптимальностьд метода сортировки, который так плох с точки зрения его программной реализации! Положение аналогично истории с датчиками глучайных чисел, когда было сделано несколько шагов назад, как только датчики, "оптимальные" с одной частной точки зрения, были рекомендованы для общего использования.
(См. комментарии к выражению 3.3.3-(39).) Отсюда мораль: рассуждения об оптимальности зачастую сильно зависят от принятого уровня абстракции модели; всякие результаты, даже очень интересные, требуют осмотрительности при их практическом применении. (Демут далее рассмотрел более общую машину с г регистрами (это ускоряет работу в г раз) и устройство, аналогичное машине Тьюринга, в котором направление движения может по желанию переключаться. Он обнаружил, что этот вид мал~ив способен выполнять простые вставки и шейкер-сортировку; но любая такая машина с одним регистром должна в среднем совершить не менее 4 (97 — /57) н7агов, так как каждый шаг уменьшает общее -г число инверсий не более чем на единицк Наконец, он рассмотрел г-регистровые машины с произвольным доступом и вопрос сортировки с минимальным чиглом сравнений.
Эта часть его тезисов была опубликована в 1ЕЕЕ Тгавзасбопа С-34 (19В5), 296 — 310.) РАЗДЕЛ 5.4 1. Можно обойтигь без фазы внутренней сортировки, но при этом работа значительно замедлится, так как возрастет число считываний каждой части данных из внешней памяти и записи в нее. 2. Серии распределяются как в (1), затем на ленту 3 записываются А~ ..
Вгеэоеоо; Яэоооао~ , В4аооеое; Рыаоаоа~ ... Еэоаоооо. После перемотки всех лент в результате выполнения "однопутевого" слияния на ленты Т~ и Тз будет помещено соответственно содержимое ТЗ и Т4 в (2). Затем Ть и Тэ сливаются на Тэ, информация копируется и сливается еще раз; в итоге имеем пять проходов. В общем случае эта процедура аналогична четырехленточному сбалансированному слиянию, но выполняетгя копирование между любыми двумя слияниями, что приводит, таким образом, к удвоенному числу проходов минус один.
3. (а) (!обе л~!. (Ь) !оВв 5, где В =,/Р(Т вЂ” Р) †. так называемая "эффективная мощность слияния". При Т = 2Р эффективная мощность равна Р, при Т = 2Р— 1 она равна ~/Р~Р— 1) = Р— 5 — эР ' + О(Р '), что несколько меньше, чем -'Т. 4. -,'Т. Если Т нечетно, а Р должно быть целым, то как (Т/2), так и (Т/2) дают одинаковое максимальное значение. В соответствии с упр.
3 лучше иметь Р > Т вЂ” Р, поэтому для сбалансированного слияния мы выбираем Р = )Т/2(. РАЗДЕЛ 5.4.1 503 ( 503 " 1. 087 154 170 426 '( 426 Г 426 653 оо ( 612 оо 2. Путь (061) †-(512/ — Я87 --В54) — С061) был заменен путем 612 612 512 154 087 . (По существу, мы выполняем сортировку методом пузырька от нижней части к вершине дерева вдоль этого пути.) 3. апй Хоагвсоте опт вязав увага/ або Ьгоибйс 2асйегв Хотсп ов сйьа/ а совсвткей соасйпевс йп ТЬЬегеу пае1оа век спе со/ апй йей1сасей кев рторов1ььоп спас/ аП аге стеаьей ейка1.
4. (Эта задача несколько двусмысленна; здесь мы не очищаем внутреннюю память, пока дополнительный буфер не будет близок к переполнению.) авй тавгвсаге ов оаг вечеа сьйв уеагв/ аеа ьтовеьс сапс1певт тасьегв Тогсь ла ЬЬЬегсу вав1ав вея са/ а авй савсе1чей йеййсатей вев ргоров111ав спас тпе/ а11 аге сгеасей ечаа1. б. Неверно: полное двоичное дерево с Р узлами определено для всех Р > 1. 6.
Вставить 'егли Т = 10С(Х[0)), то переход к шагу К2; в противном случае" в начало шага Кб и исключить аналогичную фразу из шага К7. 7. Алгоритм ничего не выдает, ОМАХ остается равным О. 8. Если бы любой из первых Р реальных ключей оказался равным оа, то запись пропала бы. Чтобы избежать этого, мы можем ввести переключатель, установив его так, чтобы на шаге К4 сравнение с ЬАБТКЕТ первоначально не выполнялось. Затем, когда впервые окажется КО ф О па шаге КЗ, переключатель изменяет свое состояние таким образом, что далее не выполняются шаг К1 и анализ КЦ на шаге КЗ й. Предположим, например, что текущая серия — восходящая, тогда как следующая должна быть нисходящей. В этом»лучае алгоритм К будет работать правильно при однол» изменении: на шаге Кб, если ЕИ(Т) = КО > КС, следует изменить на противоположный знак сравпапия КЕТ(1.0БЕК(Т)) с КЕТ(0).
Когда КС меняется, проверки ключей на шагах К4 и Кб должны изменяться соответствующим образом. 10. Пусть 0 = — 10С (Х [))) . Алгоритм К обеспечивает выполнение следующих условий при достижении шага КЗ, если заранее установлено 1.0БЕК( О)» — 0 и КИ( 0)» — КО. Значения 1.0БейбО), ..., 1.ОБЕЕ( (Р— 1)) представляют собой перестановку множества ( О, .1, ..., (Р— 1)); су»цествует перестановка указателей (10БЕК(0) [ КИ( /) = О), которая соответствует текущей турнирной сетке Другими словами, если КИ(/) равно нулю, величина КЕТ(ЬОБЕКО/)) не имеет зна»ения, :можно переставить "проигравших" друг с другом.
После Р шагов все КИ( )) будут отличны от нуля. Таким образом, дерево будет сформировано полностью. (Ответ на указание — "да'.) Любители строгости формулировок могут возразить, что алгоритм сравнивает значения КЕТ, которые е»це не иницию»изированы Если вас это тоже смущает, можете избежать такой ситуации, установив на шаге К) все КЕТ равными О. 11. Верно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
