Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 82
Текст из файла (страница 82)
При- свойте картам номера от 0 до 5 — 1 в соответствии с тем, на каком по порядку сеансе была прочитана карта, и примените поразрядную МЦ-сортировку в системе счисления с основанием т. (См. Мшч)н Сагс)пег'з ббхгЬ Боо)г ог Магйетабса) Сашез (Зап Ггалс1эсо: %. Н. Ргеешап, 1971), 111 — 112.) 15. Пусть требуется 5 чтений и можно раскладывать карты в ш стопок. Порядок обра- щается при каждом просмотре: если необходимо 5 чтений в одном направлении, то в обратном направлении понадобится н+ 1 — 5 чтений. Минимальное число просмотров есть либо наименьшее четное число, большее илн равное !об„, Й, либо нзименьшее нечетное число, большее или равное )об (и + 1 — 5).
(Если отталкиваться от рассортированной перестановки, то нетрудно заметить, что после первого просмотра перестановка требует не более чем т чтений для убывающего порядка, после второго — не более чем т э чтений для возрастаощего порядка и т, д.) Нашу перестановку можно рассортировать в порндке возрастания за пнп(2, 5) = 2 просмотра, а в порядке убывания — за пнп(3, 4) = 3 просмотра, если раскладывать карты только в две стопки.
10. Обеспечим, чтобы каждая строка завершалась специальным символом пиИ, кото- рый меныве кода любой буквы в алфавите. Выполните поразрядную сортировку слева направо, причем перед этим нужно связать все строки в единый блок данных. Затем обработайте каждый блок (5 = 1, 2, ...), в котором содержится более одной отличной строки, разделив его на подблоки и приняв за основу Ь-ю букву каждой строки. При атом сохранится сортировка блоков, выполненная по начальным буквам (будем называть их пре4иксам). Когда в блоке останется только один злемевт и все их Ь-е символы будут равны пп(1 (т. е. все ключи будут одинаковыми), организуем работу так, чтобм избежать сто повторного анализа, (В, Ра18е, В.
Е. Тат)ап, ЯСОМР 18 (1987), 973-989, 82.) Этот процесс, по сути, есть построение дерева, как описано в разделе б.8. Более простой, но и немного менее аффективный алгоритм базируется на поразрядной сортировке справа налево и описывается в работе А)зо, Норсгойз Н!1пзап, ТЬе Вепйп апс) Ала)утбз оГ СотриЗег А!8ойсйтз (Аоо1зоп-'гзез)еу, 1974), 79-84. Метод Мак-йлроя, на который имеется ссмлка в тексте раздела, обеспечивает на практике еще более бмструю сортировку, РАЗДЕЛ $.3.1 1. (а) г ~, где А;; есть либо 1 . '2 , либо Аш Азз паз В,зз ВззЗ Вз 1 а В,.з ест Длина внешнего пути равна 112 (оптимальная).
(6) Здесь А,з = г ~, тле СЗи = ага Со зз Сззз Двина внешнего пути также равна 112 (оптимзльная). 17. Метод Мак-Ларена позволяет ускорить выполнение на втором уровне, но не мохсет использоватьсл на первом уровне, поскольку он не предусматривает вычисление значений Ф». 18. Во-первых докажем то, что рекомендовано в указании. Пусть рз = 1 „. /(х) Их-- (з+! з/оп вероятность того, что ключ попадет в стопку Ь, если имеется СХ стопок.
Время, необходимое для распределения записей, имеет порядок О(Х), а среднее число инверсий, остав- ~ К'='. ' (") ( — )' '(~) = Ю'м. ' (") 4 < —,'рзВ/С, поскольку рз < В/СЖ. Теперь рассмотрим два уровня распределения, причем на верхнем уровне число стопок — сЮ, и пусть Ьз = зпр(/(х) ) Ь/сХ < х < (Ь+ 1)/сХ). Тогда среднее суммарное время выполнения равно 0(Ж) плюс 2 зм,, Тз, где Ть — среднее время, затрачиваемое при выполнении сортировки Фз ключей, для которых функция плотности вероятностей имеет вид /з(х) = /((Ь+ в)/сХ)/сФрз в соответствии с алгоритмом Мак-Ларена.
Как следует пз приведенного выше анализа, Тз = Е 0(Ьз Кз/сАрь), поскольку /з (я) ограничена величиной Ьз/сХрз. Но Е Фз = Фрз, так что Тз = 0(Ьз/с). А при Х -+ оз по определению интегрируемосгн по Римаиу получим 2 ',"; Ьз -+ Ф/ /(х) Их = Х. 2, В обозначенивх упр. 5,2.4-14 В(н) — В(н) = ~~ ((е! + й — Ц2'" — (е! + 1)2'") + 2" ь — 2" ь=! = 2" — 2" — ~ ~(е! — ее+ 2 — й)2" ь 3 >2с! (2с!-!+ +2х!-!Е!+2ч) >О При атом равенство достигается тогда и только тогда, когда н = 2" — 2! при некоторых к > 2 > О.
[Если для слияния используется "нискодящав" версия, как в упр. 5.2.4-23, максимальное число сравнений будет равно В(п).[ 3. При и > О число исходов, в которых наименьший ключ встречается точно й раз, равно ("„)Рь-ы Таким образом, 2Р„= ) ь (ь)Р4 ь прил > Ои мы имеем 2Р(х) ж е'Р(х) +1, как следует из формулы 1.2.9- (10). Другое доказательство опирается на тот факт, что Р = ) г~е [")Ы, поскольку ["„) есть число способов разбиения множества из и злементов на й непустых подмножеств, а зтн подмножества можно переставить Ы способами. Таким образом, согласно формуле 1.2.9-(23) ~ „ье Р„х /и! = 2„г>е(е' — 1) = 1/(2 — е*). И все же остается еп!е ед!!о, пожалуй, наиболее интересное доказательство, Скомпонуем из всех элементов устойчивую последовательность, так что К; предшествует К! тогда и только тогда, когда К; < К илн (К, = К. и ! < /).
Среди всех возможных Р„исходов данное расположение К„,, К„„встретится ровно 2~ раз, где л — число восходянптх серий перестановки а!... а„; следовательно, Р„можно выразить через числа Эйлера: Р„= 2 „(,",)2". Искомый результат можно получить„используя формулу 5.1.3-(20), прн г = 2, Эту производящую функцию нашел А. Кейлей (А. Сау)еу) [РЬ!Т Мвб. 18 (1859), 374-378) применительно к перечислению одного нечетко определенного класса деревьев.
См. также Р. А. МасМаЬоп, Ргос. йол!)оп Маей. Яос. 22 (1891), 341-344„3. ТовсЬатб, Авп. Яос, Яс!1 Вл!хейев 53 (1933), 21 — 31; О. А, Сговв, АММ 69 (1962), 4-8. В последней работе получена интересная формула Р„= 2 „ь, л"/2!+г, н > 1. 4. Представление 1(' . !(х-!п2) ) 1 1 гз / 1 1 2Р(х) = — 1-!сос 21 2 / 2 с-)п2 ~1л-1п2-2я!к л-1п2+2к!к) ьй!' дает сходящийся ряд Р /и) = -'(1п2) " '+ 2 „>, 51((чь 2+ 2к!к) " '). 6. 5'(г!) > Я(п), поскольку все ключи могут быть различны; таким образом, остается показать, что Я'(и) < В(п).
Пусть дан алгоритм сортировки для различных ключей, требующий Б(в) шагов. Тогда можно построить алгоритм сортировки для общего случая, считая, что ветвь для отношения "=" идентична ветви для отношения "<", н удалить лишние сравнения. По достижении внешнего узла нам становятся известными все отношения равенства, поскольку К, < К „« . К,„и при всех 1 < 1 < в были выполнены явные сравнения К,:К,„,. М.
Патерсон (М. Рагешон) обратил внимание на то, что егля множество ключей есть (вв...,в ), то число сравнений может быть уменыпено до в1бв — 2 и; 18 в + О(л); см. $1СОМР Б (1976), 2. Этой нижней границы можно достичь без существенного увеличения объема дополнительной памяти, модифицирован метод пирамидальной сортировки применительно к случаю равных ключей, как предлахсено в работе Мщпо, Еашэл, гестасе №геэ ш Сошр.
5с1 619 (1991), 473-480. 7. См. рис. А-1. Среднее число сравнений равно (2+ 3+ 3+ 2+ 3+ 3+ 3+ 6+ 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) + 19(в — 2)) = 1 + 19(в — 1) + 19(л — 2) при в > 2. (Таким образом, наилучшая стратегия заключается в том, чтобы сравнивать каждый раз по возможности два неизвестных ключа.) Отсюда вытекает, что /(л) — д(в) = 1(/(в — 1) — д(в — 1)) при л > 2 и д(в) = з1(л+ 1(1 — (-1)")) при в > О. Следовательно, ответ есть 1зв+ ~~ — 6~( — -') — (-') прн л > 1.
(Эту точную формулу можно сравнить с теоретико-информационной оценкой нижней границы 1абэ(2л — 1) 0.6309л.) 11. То, что 5 (и) < В(т) + (л — т)(18(л1+ 1)) прн л > т, можно доказать, используя методику бинарных вставок. С другой стороны, 3 (л) > (162„,',",(ъ)Уе!), а предел правой части равен л 16 т + 0(((т — 1)/т)" ) (см. формулу 1.2 6-(63)). 12. (а) Если избыточные сравнения не выполняются, то равнмм ключам, когда они сравниваются впервые, можно приписать произвольное отношение порядка, поскольку это отношение порядка нельзя вмвести нз предыдущих сравнений, (Ь) Предположим, что дерево сильно сортирует любую последовательность нулей и единиц. Докажем, что оно сильно сортирует любую перестановку элементов (1, 2,...,в), Пусть это не так, т, е.
существует перестановка, которую оно якобы упорядочивает,как К„ < К , « К „, на в действителъности существует 1, при котором К„, > К„,,, Заменим нулями все элементы < К,, и единицами . — все элементы > К ,; по предположению наш метод рассортирует полученную перестановку, если выбрать путь, ведущий к К„ < К , « ..
К,„. Значит,мы получили противоречие, 13. Если в четно, то Г(л) — Р(л — 1) = 1+ г'((в/2) ) — Е((л/2) — 1) и нам нужно доказать, что юъ 1 < (л/2) < юъ; это очевидно, поскольку юэ 1 = (юъ/2). Если в нечетно, та Г(л) — Р(л — 1) = С((л/2)) — С((л/2) ) н нам нужно доказать, что гю в < (в/2) < гэ; зто очевидно, поскольку 1ъ 1 — — )'юъ/2). 14. Согласно упр. 1.2.4-42 эта сумма равна л(18 зл) — (ю~ + . +ю1), где ю1 < в < югъь Последняя сумма равна ю;+1 — ~/2) — 1. Следователъна, Г(п) можно записать в виде л(16 1л) — (21'кш<0/3) + Я 16(би)) (а также многими другими способами.) 15, Если (!8 4п) = !8(1п)+д, то Г(п) = и!8п — (3 — !83)я+п(8+1 — 2 ) + О(1обн).
Есэи (!8п) = !8п+8, то В(п) = н!8п — и+ ««(д+ 1 — 2 ) + О(!обп). (Обратите внимание на то, что !8п! = п18п — п((1п 2) + О(!обн); 1Д!п2) ж 1,443; 3 — !83 1.415.) 17. Число случаев, когда Ьь < ар < Ь«,.«.«, равно Гт — р+и — й) (р — 1+Ь) а число случаев, когда аз < Ь«< а«е««равно 18, Нет, поскольку мы рассматриваем всегда наименее эффективную ветвь под кюкдым узлом-сравнением. Одна из более эффективных ветвей могла бы оквзатьск более трудоемкой, 20. Пусть Х вЂ” максимальный номер уровня, на котором есть внешние узлы, а ! — такой минимальный номер. Если Х, > 1+ 2, то на уровне Х можно удалить два узла и поместить их под некоторым узлом на уровне 1; в рп«ультате длина внешнего пути сократится на ! + 2Х, — (Х, — 1+ 2(! + 1)) = Х вЂ” ! — 1 > 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
