Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 37
Текст из файла (страница 37)
[М81] Пусть с(уг') — число сравнений ключей при сортировке Х элементов методом Бэтчера; оно равно количеству выполнений шага М4. а) Покажите, что с(2') = 2с(2' ~)+(1 — 1)2' ~+1 при 1 > 1. Ь) Найдите простое выражение для с(2') как функцию от и Уко«акое. Рассмотрите последовательность х~ с(2')/2'. 18. [МУ8] Назначеняе этого упражнения — проанализировать функцию с(Х) из упр. 14 и вывести формулу для с(Ж), если К = 2" +2'«+ ° +2'", е~ > е«> > е, > О. а) Пусть а(Ф) = с(Я+ 1) — с(й). Докажите, что а(2п) = а(п) + [18(2п)] и а(2п+ 1) = а(п) + 1; отсюда а(йг) = ~ ~ — г(еь — 1)+(е~+с«+ .
+е„). /с~+1~ 2 Ь) Пусть к(п) = а(п) — а( и/2]), так что е(п) ы х(п)+ х([п/2]) +х([п/4]) + . Пусть р(п) = х(1) + х(2) + ° + я(п) н «(2п) = у(2п) — а(п), «(2п+ 1) = И(2н+ 1). Докажите, что с()У+ Ц = «(Ф) + 2«([%~2]) + 4«([Ф/4]) + ) Дока~иге, что р(Ж) = уг" + ([М/2] + 1)(еэ — 1) — 2" + 2. 4) Теперь соберите все вместе и найдите выражение с(Ф) через показатели еу при фиксированном значении г.
16. [ВМ42] Найдите значение асимптотического выражения для среднего числа операций обмена, когда алгоритм Бэтчера применяется к случайной перестановке л1 различных элементов, полагая, что Ю есть степень двойки. ь 17. [90] Где в алгоритме () используется тат факт, что К» н Кмт» имеют значения, постулированные неравенствами (13)7 ь 18. [20] Объясните, как работает алгоритм Я в случае, когда все ключи в исходном массиве равны. Что произойдет, если на шагах (»3 и Я5 заменить знаки "<" знаками "<'7 19. [15] Будет ли алгоритм () по-прежнему работать правильно, если вместо стека (погледним пришел — первым вышел) воспользоваться очередью (первым пришел — первым вышел)? 20. [МЯ0] Выразите наибольшее число аэементов, которые могут одновременно оказаться в стеке во время работы алгоритма (), в виде функции от М и Ю, 21, [30] Объясните, почему для фазы разделения в алгоритме Я требуется именно столько сравнений и пересылок, сколько определено в (17).
22. [Мйб] Пусть рьм — веронтиасть того, что величина А в (16) будет равна я, если алгоритм Ц применяется к случайной перестановке множества (1, 2,..., Х], и пусть Ам(э) = 2 „рамль — соответствующая пронзводшцая функция. Докажите„чта Ам(г) = 1 прн М < М, а Ам(г) = эД,«,мА,-~(э)Ам-,(э))/Ж прн К > М. Найдите аналогичные рекуррентные соотношейия, определяющие другие распределения вероятностей Вм (э), См(э), Вм(э), Ем(э), Ям(г).
23. [М83] Пусть Ам, Вм, Вм, Ем, Ям — средние значения соответствующих величин в (16) при сортировке случайной перестановки множества (1, 2,..., )г'). Найдите для этих величин рекуррентиые соотношения, шгалогичные (18), затем найдите решения этих соотношений и получите формулы (25). 24. [МЯ1] Очевидно, в алгоритме Я выполняется несколько больше сравнений, чем необходимо, потому что на шаге ОЗ мажет получитьсяэ = у, а на шаге Я5 — даже 1 > 11 Сколько сравнений См выполнялось бы в среднем, есди бы исключались все сравнения при 1 > 17 25.
[МЗО] Чему равны точные значения величин А, В, С, В, Е н Я для программы О, когда исходные ключи представляют собой упорядочмэиый набор чисел 12 ... Х в предположении, что Ф > М. ° 26. [М24] Постройте исходную последовательность, при которой программа Я работала бы еще медленнее, чем в упр. 25. (Попытайтесь найти по-настоящему отвратительный случай.) 27. [М28] (Р. Седгевик (Н.
3Ыйен!сЪ),) Рассмотрите наилучший случай для алгоритма О, Найдите перестановку множества (1, 2,..., 23), которая требует меньше всего времени для сортировки при Х = 23 и М = 3, 28. [МЗб] Найдите рекурреитнае соотношение, аналогичное (20), которому удовлетворяет среднее число сравнений в алгоритме Ц, модифицированном Синглтоном (т. е. когда в качестве э выбирается не о = Км а медиана из (КмК11м,лы»1, Км)), Не обращайте внимания на сравнения, которые необходимы при вычисления медианы о. 29.
[ВМ40] Найдите значение асямптатического выражения для числа сравнений в алгоритме Сннглтона "медиана из трех" (это упражнение является продолжением упр. 28). ь 30. [25] (П. Шеклтон (Р. ЯЬасИ»1»п).) При сортировке ключей длиной несколько машакнмк слое работа многих алгоритмов все более замедляется по мере упорядочения массива, поскольку для определения правильного лексикографяческого порядка равных илн почти равных ключей необходимо сравнить несколько пар слов (см. упр, 5-5).
В массивах, которые встречаются на практике, часто содержатся почти равные ключи, и это явление может заметно отразиться на времени сортировки. Объясните, как можно усовершенствовать алгоритм (З, чтобы избежать этого затруднения. В подмассиве, о котором известно, что старшие й слов во всех ключах содержат постоянные значения, следует проверять лишь (й + Ц-е слова ключей. ь 31. [30] (Ч. Э.
Р. Хоар (С. А. Н. Номе).) Предположим, что необходимо не рассортировать массив, а лишь определить т-й наименьший по величяне элемент из заданного множества и элементов. Покажите, что алгоритм быстрой сортировки можно приспособить для этой цели, сократив значительную часть вычислений, которые используются для полной сортировки. ЗЗ, [М40] Найдпте простое выражение в замкнутом виде для С, — среднего числа сравнений ключей, необходимых для поиска т-го наименьшего из и элементов по метцлу быстрого поиска (см.
упр. ЗЦ. (Для простоты можете положить М = 1; т. е, предполагается не использовать специальную методику обработки коротких подмассивов.) Каково асимптотическое поведение параметра С~з и — среднего числа сравнений, необходимых для нахождения медианы из Зш — 1 элементов методом Хоарау ь 33. [15] Разработайте алгоритм переразмещения чисел в некоторой заданной таблице пь ким образом, чтобы все ашрнцапмльнне значения предшествовали положительным. Элементы полностью сортировать не нужно: достаточно просто отделить отрицательные числа от положительных.
Алгоритм должен быть построен таким образом, чтобы мннимязировалось количество операций обмена записей в памяти. 34. [80] Как можно ускорить циклы проверки разрядов при обменной поразршпюй сортировке (шаги от ВЗ до Нб)2 Зб. [МЗЗ] Проанализируйте статистические характеристики А, В, С, С, К, Д Н, л и Х, которые получаются при обменной поразрядной сортировке исходных данных наподобие (1). 36.
[МЗ7] Для любой данной последовательности чисел (а„) = аэ,аназ,... определите ее бннамнальное преобразование (а„) = ае, амат,... с помощью правила а =~ ( )( — Цаз. а) Докахсите, что (а„) = (а„). Ь) Найдите биномиальные преобразования зюследовательностей (Ц, (и) и ((")) при фиксированном т, (а") — при фиксированном а, ((") а") — при фиксированных а и ш.
с) Прелположим, что последовательность (х„) удовлетворяет соотношению хк = а + 2 ~ ( ) хь при и > 2; хе = х~ ж ае = аз — — О, ь>з Докажите, что решением этого рекуррентного соотношения будет ь>з ь>з ЗТ. [МЯ8] Определите все такие последовательности (а ), что (а ) = (а„) в смысле упр. Зб. ь 33.
[МУ0] Найдите Ал, Вл, Сн, Сн, Кл, Ел, Кл и Хн — средняе значения величин в (29) в случае, когда поразрядной сортировке подвергаются исходные данные наподобие (З). Выразите ответы через Ю и функции ~"" (к) 2" 1 — 1 ь>г [Указание. См. упр, Зб.] 39. [30] Результаты (ЗО) показывают, что поразрядная обменная сортировка, примененная к случайным входным данным, требует около 1.44Х итераций. Докажите, что для быстрой сортировки никогда не требуется более Х итераций, и объясните, почему при обменной поразрядной сортировке часто необходимо более Х итераций. 49. [3!] Объясните, как нужно изменить алгоритм В, чтобы он работал достаточно аффективно и в том случае, когда в сортируемых массивах содержится много равных ключей. »' 41.
[ЯО] Разработайте такой способ обмена записей Н»... Н, который обеспечивает их разбиение на три блока: (!) К» < К при 1 < )г < 1; (и) К» = К для 1 < й < 1; ((ц) К» > К для ! < й < г. Схематически окончательная компоновка должна иметь следующий внд: <К ! 1 ! г 42. [НМ33] Докажите, что для любого действительного числа с > О вероятность того, что алгоритм (С потребует менее (с + Ц(Ф + ЦНл сравнений при сортировке данных, меньше е ' . (Верхняя грань представляет особый интерес, если запать условие, скажем, с ы Н'.) 43.
[НМО!] Докажите, что !е р '(е "— Цлу+ [, К е "»(р = -у. [Умзакпе. Рассмотрите!!ша ~О+ у ] 44. [НМО!] Выведите формулу (37), как предложено в тексте настоящего раздела. 43. [НМЮО] Объясните, почему прн х > О справедливо равенство (43). 46. [НМОО] Каково значение выражения (1/2х!) !;"~ Г(х)п' *»(з/(2' * — Ц прн условиях, что з — целое положительное число и О < а < зт 42. [НМО!] Докажите, что т >, (и/2!) е '!~ — ограниченная функция от и.
43. [НМЯ1] Найдите асимптотическое значение величины У, апре!к»ленной в уцр, 38, при помощи методов, аналогичных тем, которые в тексте настоящего раздела использовалксь для анализа величины (!», н получите члены до О(Ц. 49, [НИХ!] Продолжите асимптотвческую формулу (47) для К, до членов порядка О(п '). ЬО. [НМ24] Найдите асимптотическое значение функции кп»=~(~)( ц »32 гдето — произвольное фиксированное число, большее 1. (Эта функция при целом тл, большем 2,потребуется для исследования общего случая обменной поразрядной сортировки, а также для анализа алгоритмов поиска в "памяти луча" в разделе б.З.) ° 31.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
