AOP_Tom3 (1021738), страница 183
Текст из файла (страница 183)
12. После обмена Вь с Л(р) на шаге М4 (упр. 5.2-12) можно сравнить Кь с К» ь Если Кь меныае, то сравниваем его с Кь м Кь э, ..., пока не встретим Кь > Км Тогда устанавливаем (Нуэ,,..., Нь „Еь) < — (Кы Н,+м..., Кь,), не меняя полей 5188. Удобно принудительно поместить с левого конца массива искусственный ключ Ке, который < всех других ключей. 14. Если исходная перестановка карт требует )г чтений в смысле упр. 5,1.3 — 20 и если при каждом просмотре карты раскладываются в т стопок, то придется выполнить не менее Роб гг) просмотров. (Рассмотрите обратный переход — от упорядоченной колоды к исходной; при каждом просмотре число чтений увеличивается не более чем в пэ раз.) Данная перестановка требует четырех чтений для возрастающего порядка и десяти чтений для убывающего порядка. Поэтому сортировка в порядке убывания требует четырех просмотров при двух стопках и трех просмотров при трех стопках.
И обратно, этого оптимального чисва просмотров достаточна для сортировки. Присвойте картам номера от 0 до )г — 1 в соответствии с тем, на каком по порядку сеансе была прочитана карта, и примените поразрядную МЦ-сортировку в системе счисления с основанием пь [Сьь МагНп Сшс)пег'э 55хсй Воо)г оГ МагЬетаНса1 Сатее (Зап Ргапс)все: ЪЧ. Н. Ггеешап, 1971), 111-112.) 15. Пусть требуется 5 чтений н можно раскладывать карты в гп стопок. Порядок обращается при каждом просмотре: если необходимо Й чтений в одном направлении, то в обратном направлении понадобится п + 1 — х чтений.
Минимальное числа просмотров есть либо наименьшее четное число, боль~весили равное 1ой к,либо наименьшее нечетное число, большее или равное 1об (и + 1 — 5) (Если отталкиваться от рассортированной перестановки, то нетрудно заметить, что после первого просмотра перестановка требует г не более чем т чтений для убывающего порядка, после второго — не более чем т чтений для возрастающего порядка и т. д.) Нашу перестановку можно рассортировать в порядке возрастания за ш!п(2, 5) = 2 просмотра, а в порядке убывания — за ппц(3, 4) = 3 просмотра, если раскладывать карты только в две стопки. 18.
Обеспечим, чтобы каждая строка завершалась специальным символом пиИ, который меныпе кода любой буквы в алфавите. Выполните поразрядную сортировку слева направо, причем перед этим нужно связать все строки в единый блок данных. Затем обработайте каждый блок (5 = 1, 2, ... ), в котором содержится более одной отличной строки, разделив его на подблоки и приняв за основу Ь-ю букву каждой строки.
При этом сохранится сортировка блоков, выполненная по начальным буквам (будем называть их префиксом). Когда в блоке останется только один элемент и все их й-е символы будут равны пвй (т. е. все ключи будут одинаковыми), организуем работу так, чтобы избежать его повторного анализа. [Е. Разбе, 11. Е. Тагзав, 51СОМР 16 (1987), 973-989, 12.) Этот процесс, по сути, есть построение дерева„как описано в разделе 6.3. Более простой„но и немного менее эффективный алгоритм базируется на поразрядной сортировке справа налево и описывается в работе АЬо, Норсго(з, П1шав, ТЬе Реззбв апз1 Ала1уз1з о/ Сошрисег А18оп0тзз (Аббшоп-%ез!еу, 1974), 79-84.
Метод Ыак-Илрая, на который имеется ссылка в тексте раздела> обеспечивает на практике еще более быструю сортировку. 17. Метод Мак-Ларена позволяет ускорить выполнение на втором уровне, но не может использоваться на первом уровне, поскольку он не предусматривает вычисление значений Хы 18. Во-первых докажем то, что рекомендоаано в указании. Пусть рз = )ь . Дх) Нх— (ь+ Ю/ск вероятность того, что ключ попадет в стопку Ь, если имеется СХ стопок.
Время, необходимое для распределения записей, имеет порядок О(Х), а среднее число инверсий, оставшихся после распределения, составляет -'2 з (Я)рзз(1 — рз)' з() = з ~"„„' (' )рз < — раВ/С поскольку рз < В/СХ. Теперь рассмотрим два уровня распределения, причем на верхнем уровне число стопок — сХ, и пусть Ьь = звр(/(х) ~ Й/сХ < х < (/с+ 1)/сХ). Тогда среднее суммарное ел-Т время выполнения равно О(Х) плюс ) ь е Ть, где Тз — среднее время, затрачиваемое при выполнении сортировки Хз ключей, для которых функция плотности вероятностей имеет вид /ь(х) = /(()с -> х)/сХ)/сХрь в соответствии с алгоритмом Мак-Ларена.
Как следует из приведенного выше анализа Тз = ЕО(ЬзХь/сХрь), поскольку /ь(х) ограничена величиной Ьь/сХрь. Но ЕХь = Хры так что Ть = О(Ьз/с) А при Х вЂ” з со по определению ннтегРиРУемости по РиманУ полУчим 2.' ' Ьь — > Х/з /(х) бх = Х. РАЗДЕЛ 5.3.1 1.
(а) г ~, где 4н есть либо 1.2 либо В Аы Ам Воз Вз; Взз Вз, а В, ь ест Длина внешнего пути равна 112 (оптимальная). (Ь) Здесь Ао = г ~, где С*,н = 3:4 Со аз Со зз Длина внешнего пути также равна 112 (оптимальная). 2. В обозначениях упр. 5.2.4 — 14 Цп) — В(п) = ~ ~((еь + й — 1)2"1 — (е1 + 1)2'" ) + 2" — 2" 1=1 = 2" — 2" — ~ (е1 — еэ+2 — й)2'1 э=э >2" — (2" + +2" ~~~+2") >О. При этом равенство достигается тогда и только тогда, когда и = 2" — 21 при некоторых )с > ! > О. [Если для слияния используется "нисходящая"' версия, как в упр. 5.2.4-23, максимальное число сравнений будет равно В(п).) 3. При и > 0 число исходов, в которых наименьший ключ встречается точно и раз, равно (")Р ы Таким образом, 2Р = 2 „(1)Р 1 прин > О и мы имеем 2Р(э) = с*Р(э) + 1, как следует из формулы 1.2.9 — (10).
ДРУгое доказательство опиРаетса на тот факт, что Р„= 2 „>е (")й), посколькУ ('„') есть число способов разбиения множества из и элементов на й непустых 1юдмножеств, а эти подмножества можно переставить Ы способами. Таким образом, согласна формуле 1.2.9 — (23) 2 ~>аР э /11 =2 ь>е(е 1) =1/(2 е ). И все же остается еп!е одно, пожалуй, наиболее интересное доказательство. Скомпонуем из всех элементов устойчивую пот 1едовательность, так что К, предшествует К, тогда и только тогда, .когда К; < К1 или (К, = К и 1 < /).
Среди всех возможных Р„исходов данное расположение К„... К,„встретится ровно 21 раз, где й число восходящих серий перестановки а1... а„; следовательно, Р„можно выразить через числа Эйлера. Р„= 2,'э (1) 2~. Искомый результат можно получить, используя формулу 5.1.3-(20), при э = 2. Эту производящую функцию нашел А. Кейлей (А. Сау!еу) (РЬ1!. Май. 18 (1859), 374 — 378] применительно к перечислению одного нечетко определенного класса деревьев. См. также Р.
А. МасМаЬоп, Ргос 5олг1оо МагЛ Яос. 22 (1891), 341 — 344; .!. ТоисЬагс1, Аоп. Яос. Боб Вгихейеэ 53 (1933), 21-31: 0 А. Сгоэе, АММ 69 (19б2), 4-8. В последней работе получена интересная формула Р„= 2 ь>, й"/21+~, и > 1. 4. Представление 2Р(э) = — ~! — 1со! / — ~~ т + 1/ . 1(г — !п2)~ 1 1 т / 1 1 21 2 / 2 э — !п2 ~~э — !п2 — 2я1')г э — !п2+2я11) 121' дает сходящийся ряд Р„/и. '= „-'(!и 2) " ' -ь 2„1>1 32(((( 2+ 2я1к) " '). 6.
Я'(и) > 5(п), поскольку все ключи могут быть различны; таким образам, остается показать, что В'(и) < Я(п). Пусть дан алгоритм сортировки для различных ключей, требующий о(п) шагов Тогда можно построить алгоритм сортиранки для общего случая, считая, что ветвь для отношения "=" идентична ветви для отношения "<", и удалить лниь ние сравнения. По достижении внешнего узла нам становятся известпымн все отношения равенства, поскольку Л, < К э « . Ка„и при всех 1 < ! < и были выполнены явные ср не ия К.,:К..„ М. Патерсон (М.
Ра1егяоп) обратил внимание на то, что если множество ключей есть (и,,..., п,„), то число сравнений может быть уменьшено до и!бп — 2 и, !6п + О(п); см. ИСОИР б (1976), 2. Этой нижней границы можно достичь без существенного увеличения объема дополнительной памяти, модифицирован метод пирамидальной сортировки применительна к случаю равных ключей, как предложено в работе Мвпга, Вагпап, Лес!иге Мосек ш Сотр. Бс!. 519 (199!), 473-480. 7. См.
рис. А-1. Среднее число сравнений равно (2 + 3+ 3+ 2+ 3+ 3+ 3+ б+ 3+ 3+ 3+ 2+3+ 3+ 2)/16 2з 8. См. рис, А-2. Среднее число сравнений равно 3 э,. 9. Если все ключи равны, то для того, чтобы обнаружить это, необходимо выполнить, па крайней мере, и — 1 сравнений Обратно, и — 1 сравнений всегда достаточна, потому что окончательное упорядочение можно получить, сравнив Л ~ со всеми остальными ключами. 10. Пусть /(и) — искомая функция, а д(п) — минимальное среднее число сравнений, необходимое для сортировки и + й элементов, где Й > О, и ровно к элементов имеют известные значения (О или 1). Тогда /(О) = /(1) = д(0) = О, д(1) = 1; /(и) = 1 + -/(ив 1) + зд(п — 2), д(п) = 1+ ш!п(д(п — 1), гд(п — 1) + —,д(п — 2)) = 1+ зд(п — 1) + зд(п — 2) при и > 2. (Таким образом, наилучшая стратегия заключается в там, изобы сравнивать каждый рвз па возможности два неизвестных ключа.) Отсюда вытекает, что /(и) — д(п) = з(/(и — 1) — д(п — 1)) при и > 2 и д(п) = ~~(п+ -'(1 — ( — —,')")) при и > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
