AOP_Tom3 (1021738), страница 43
Текст из файла (страница 43)
12 ЕИТЗ НЕАВ+1-1МРОТ,4 )Ч Ч +- 10С(ИЕАП(гА)). 10 ЬОА 1МРОТ,1 М К «- К,. 14 ЗМР 4Р Х Переход на установку р. 10 ЗН СИРА 1ИРОТ,2(КЕЧ) В + )Ч вЂ” А 1б ЛЬЕ БР В + Х вЂ” А Переход на вставку, если К < Кр. 17 ЕМТЗ 0,2 В д«-р. 10 4Н ЬО2 1МРОТ,З(ЬТМК) В+ Ж р «- ь1МК(Ч). 10 12Р ЗВ В+ 1Ч Переход, если не конец списка. 20 бн ЯТ1 1М ОТ,З(ЬТМК) )Ч 11МК(д) — 1ОС(Я,). 21 ЯТ2 1МРОТ,1(Ь1МК) 1Ч «1ИК(10С(В«)) ~.— р. 22 ВН ОЕС1 1 Ж 20 11Р 2В )Ч )Ч>1 >1.
$ Эта программа написана для любого значения М, но лучше зафиксировать М, положив его равным некоторому приемлемому значению; можно, например, положить М = ВУТЕЯ12Е, тогда головные элементы списков можно очистить с помощью одной-единственной команды МОЧЕ, а последовательность команд 08 — 11, реализующих умножение, заменить единственной командой ЬОЗ 1ИРОТ,1(1:1). Наиболее заметное отличие программы М от программы Ь состоит в том, что в программе М нужно принимать во внимание и возможность образования пустого списка, когда не надо делать сравнений. Сколько же времени мы экономим, имея М списков вместо одного? Общее время выполнения программы М равно ?В+31% — ЗА+4М+2 машинных циклов, где М вЂ” число списков, Х вЂ” число сортируемых записей, А и В равны соответственно числу правосторонних максимумов и числу инверсий среди ключей, принадлежащих каждому списку.
(Анализируя этот алгоритм, в отличие от всех других в данном разделе, мы включаем н подсчет А и крайний справа элемент непустой перестановки, а не игнорируем его.) К4ы уже проанализировали величины А и В при М = 1, когда их средние значения оказались равными соответственно Нм и -' ( ) . Согласно предположению о распределении ключей вероятность того, что данный список в конце сортировки будет содержать ровно п элементов, есть "биномиальная" вероятность В„„=М~ ( )( — ) (1 — — ) ( )/2.
(16) Используя тождество которое представляет собой частный случай соотношения 1.2.6-(20), можно легко определить сумму в (16): В„.,=2 М(2). (17) В упр. 37 определено стандартное отклонение для В, но суммирование в (15) вы- полняется сложнее. По теореме 1.2.7А получим /У 1 ( )(М 1) Нл = (1 ) (Нм 1пМ) +с~ ь-я М 0<с= ~ ~— (1 — — ) < ь>н следовательно, Мт г 1 ~я+1 4ьть = М(НЛ вЂ” 1пМ)+5, 0 < б < (1 — — ) (18) Лт+1 ~ М/ (Эта формула практически бесполезна, еслп М вЂ” Х. Более подробно асимптотическое поведение величины Аыь при М = Л/о обсуждается в упр. 40.) Рассматривая совместно (17) и (18), можно получить общее время выполнения программы М при фиксированном М и Х -э ош ппп 31Лг+ М+ 2, аче 1.75Л7т/М+ 31Х вЂ” ЗМНн + ЗМ (и М+ 4М вЂ” 35 — 1.75Л'/М+ 2, шах 3.50Л'~ + 24.5Л'+ 4М + 2.
(19) Заметим, что если М не слишком велико, то среднее время выполнения сокращается в М раз. При М = 10 сортировка будет осуществляться примерно в 10 раз быстрее, чем при М = 1. Однако максимальное время выполнения гораздо болыпе среднего. Таким образом, подтверждается важность выполнения условия равномерности распределения ключей, так как наихудший случай имеет место, когда все ключи попадают в один список. Если положить М = Х, то среднее время выполнения будет составлять примерно 34.36% машинных циклов.
При М = 1Х оно несколько больше, приблизительно 34.52Л' машинных циклов, а при М = —,' Л вЂ” приблизительно 48.04Х. (Заметим, что 10Ж машинных циклов ИХХ при этом тратятся на одну лишь команду умножения!) Дополнительные затраты на сопровождающую программу из упр. 35, которая связывает воедино все М списков, увеличивают время выполнения приблизительно до 44.99%, 41.95% и 52.74Л' соответственно вариантам значения М. Таким образом, получен метод сортировки с временем работы порядка Х при условии, что ключи довольно равномерно распределены в области возможных значений.
Пути дальнейшего совершенствования метода вставок в несколько списков обсуждаются ниже, в разделе аг.2.5. УПРАЖНЕНИЯ 1. (10) Является ли алгоритм Б алгоритмом "устойчивой" сортировки? 2. [11) Будет ли алгоритм Б правильно сортировать числа, если на шаге БЗ отношение К > К, заменить отношением К > К,? 3. [50) Является ли программа Б салшй короткой программой сортировки для машины КХХ, или можно написать еще более короткую программу, которая давала бы тот же результат? 4.
[МЙО) Найдите минимальное н максимальное время выполнения программы Б как функцию от 1>>. ° 5. (Мй?) Найдите производящую функцию дл(г) = 2 л>орллг~ для общего времени выполнения программы Б, где рл.л — вероятность того, что на выполнение программы Б уйдет ровно Й машинных циклов при заданной исх>отпой случайной перестановке множества (1,2,...,К).
Вычислите также стандартное отклонение времени выполнения для данного значения )>'. 6. [20) Для метода двухпутевых вставок, праиллюстрированнаго в табл. 2, по-видимому, необходимо> помимо области ввода, содержащей )>' записей, иметь область вывода, в которой может храниться 2М+ 1 записей. Покажите. что можно выполнять двухпутевые вставки, имея в памяти как для ввода, так н для вывода пространство, достаточное для хранения всего 21Л> + 1 записей.
7. [М20[ Пусть о> аг... а„— случайная перестановка множества (1, 2,..., и). Каково среднее значение величины [а> — 1[+ (аг — 2(+ + [а — и[? (Оно равна произведению и и среднего чистого расстояния, на которое перемещается зались в процессе сортировки.) 8.
[10) Является ли алгоритм Р алгоритмам "устойчивой" сортировки? 9. (20] Какие значения А и В и какое общее время раГ>оты программы Р соответствуют табл. 3 и 4? Проаналп. > руйте достоинства метода Шелла по сравнению с методом простых вставок в этом случае. ь 10. (22) В случае, когда 1Г> > К, л, на шаге РЗ алгоритм Р предписывает выполнение множества ненужных действий. Покажите, как можно изменить программу Р, чтобы избежать этих избыточных вычислений, и проанализируйте преимущества такой модификации. 11. [М10) Какой путь на решетке (аналагичной представленной на рис. 11) соответствует перестановке 1 2 6 3 7 4 8 6 9 11 10 12? 12. (МОО) Докажите, что сумма вертикальных весов пути на решетке равна числу инверсий соответствующей 2-упорядоченной перестановки.
ь 13. [М16) Поясните, как нужно приписать веса на решетке горизонтальным отрезком вместо вертикальных, чтобы сумма горизонтальных весов пути на решетке равнялась числу инверсий в соответствующей 2-упорядаченной перестановке. 14. (МЯО) (а) Покажите, что для сумм, определяемых равенством (2), действительно Аг е> = 2А> . (Ъ) Если положить г = в, 1 = — 2, то обобщенное тождество в упр, 1.2.6 — 26 упрощается и приводится к виду (2?с+ в) л 1 (1 — >/à — 4г) Проанализировав сумму 2 „Аг„з", покажите, что Аг„= п 4" ь 15. [НМЭЭ[ Пусть д„(з), д„(з). И„(з) и И (з) равны 2 з~"'"" "' "' ", где сумма берется по всем путям длиной 2п на решетке от (0,0) до (и, и), где веса определяются, как на рнс.
11, а пути удовлетворяют некоторым ограничениям на верзпины, через которые эти пути проходят. Для Л (з) нет ограничений, но для д (х) пути не должны проходить через вершины (з,у), такие, что з > 3; И„(з) и д„(х) определяются аналогично, но не допускаются также и вершины (з, з) при 0 ( з < и. Таким образом, да(я) = 1, дз(з) = з, дз(з) = з + к; дз(я) = з, дг(з) = з; з г з Ие(з) = 1, Из(з) = з + 1, Иг(е) = з + з + Зз + 1; Лз(з) = х + 1, Йг(х) = зз + з. Найдите рекуррснтные соотношения, определяющие эти функции; и воспользуйтесь полу- ченными рекуррентными соотношениями для доказательства равенства (Отсюда легко можно найти точную формулу дисперсии числа инверсий в случайной 2-упорядоченной перестановке множества (1, 2,..., 2п);,она асимптотически приближается к (зо й)п ) 16.
[М24] Найдите формулу максимального числа инверсий в И-упорядоченной перестановке множества (1,2,...,и). Каково максимально возможное число перезаписей при выполнении алгоритма В, если значения смещений для сортировки удовлетворяют условию делимости (5)? 1?. [М2/[ Покажите, что если Х = 2' и Л, = 2' при г > з > О, то существует единственная перестановка множества (1, 2,..., и), максимизирующая число перемещений записей при выполнении алгоритма Р. Найдите простой способ описания этой перестановки. 18. [ЛМ24) При больших значениях /О сумму (б) можно считать равной у2 / — ? /з/3/гИз/г /Оз/г~ з/г — — + ~ + + 4 Из з 8 ~ Из г И Какояы действительные значения Лз и, Иа, минимизирующие это выражение, если И/ и г фиксированы, а Из = 1? ° 19.
[М25[ Каково среднее значение величины А в анализе времени работы программы В, если значения смещений при сортировке удовлетворяют условию делимости (5)? 20. [М22[ Покажите, что теорема К следует из леммы Е. 21. [М25) Пусть И и И вЂ” взаимно простые целые положительные числа. Будем говорить, что целое число — порог/сдаемое, если оно равно хИ+ уИ при некоторых неотрицательных целых кз и дз.
Покажите, что и является порождаемым тогда и только тогда, когда ИИ вЂ” И вЂ” И вЂ” и — не пораксдаемое. (Поскольку 0 — наименьшее порождаемое целое, наибольшее не порождаемое дшзжно, таким образом, быть равно ЛИ вЂ” Л вЂ” И. Отсюда следует, что в любом массиве, который является одновременно и И-, и И-упорядоченным, К, < Км если только 3 — з > (И вЂ” 1)(/з — 1).) 22. [МЭО[ Докажите, что любое целое число > 2'(2' — 1) можно представить в аиде ао(2 — 1) + аз(2'е' — 1) + лз(2'ьг — 1) + где а, — неотрицательные целые числа; но число 2'(2' — 1) — 1 нельзя представить в таком виде. Более того, существует ровно 2' '(2' + з — 3) цел»вх положительных чисел, которые нельзя представить в таком виде.
Найдите аналогичные формулы для случая, когда в этом представлении выражение 2 — 1 заменено выражением 2 + 1. » ь 23. [М22] Докажите, что если Л,»э и Л» ~ — взаимно простые числа, то количество перезаписей в ходе выполнения алгоритма П при просмотре со смешением Л, есть 0(5?Л,езЛ„+~/Л,). (Указание. См. упр. 21.) 24. [М42) Докажите, что теорема Р . — наилучшая яз возможных теорем в том смысле, что показатель 3/2 нельзя уменьшить. ь 25.
[М22] Сколько существует перестановок множества (1, 2,, Ж), являющихся одновременно 3- и 2-упорядоченными? Каково максимальное чисто инверсий в такой перестановке? Чему равно суммарное число инверсий во всех таких перестановках? 26. [МЯ5] Может лн 3-, 5- и 7-упорядоченный массив из )з' элементов содержать более )»? инверсий? Оцените максимальное количество инверсий при большом )з'. 27.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
