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