Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 73
Текст из файла (страница 73)
28). Вместо того чтобы хранить значения смещений во вспомогательной таблице, удобно генернрова".гь их на двоичной машине сведующим образом. Р1. Присвоить го+- 20ел" ', наибольшая степень двойки, меньшая ЬГ. Р2. Приаюить Ь +- гл. РЗ. Использовать Ь в качестве смещения на очередном проходе сортировки. Р4. Если Ь четное, присвоить Ь +- Ь+ Ь12; затем, если Ь с Р1, вернутьгл к РЗ.
Рб. Присвоить гп е- (гп/21 и, если пг > 1, возвратиться к Р2. $ Хотя смещения для сортировки генерируются не в порядке убывания, сформированная последовательность значений обеспечивает правильную работу алгоритма. 32. 4 12 11 13 2 0 8 5 10 14 1 6 3 9 16 7 15. 33. Улучп«ить программу можно двумя разными способами. Во-первых, полагая, что искусственный ключ Ко равен оа, можно опустить проверку условия р > О, (Эта идея применялась, например, в алгоритме 2,2.4А.) Во-вторых, мох«но использовать стандарх- ный прием оптимизации: продублировать внутренний шякл, поменяв местами присвоенные регистрам значения р и 4; в результате удастся избежать присвоения д «- р.
(Эта идея использовалась в упр. 1.1.-3.) Таким образом, предполагается, что в поле (О:3) по адресу 1ИРУТ содержится наи- большее возможное значение и нужно заменить в программе Ь строки, начиная с 07, следующими. 07 ВН 103 ХИРУТ.2(ПИК) В' р+- Ь«. (Здесь р ш г13, 4 ш г12.) 08 СНР4 ХЕРСТ „З(КЕТ) В' 09 1С 4Р В' Перейти к шагу 14 с 4 еь р, если К > Кг.
1О 7Н 371 ХИРУТ,2(ХХНК) «т «ч +-1, 11 ЗТЗ 1ИРУТ, 1(ьХИК) «У Ь1 +- Р. 18 Л«Р 6Р «У Переход на уменьшение,), 18 4Н 502 ХИРУТ,З(11ИК) В" р+- Ь«. (Здесь р щ г12, 4 ш г13.) Ц СНР4 ХИРУТ,2(КЕТ) В" 15 1С ВВ В" Перейти к шагу 1,4 с д еь р, если К > К„. 16 ВН 371 1ИРУТ,З()ХИК) «ч Хч «-1. 17 ЗТ2 ХИРУТ,1(51ИК) Ко Ку +- р. 18 6Н РЕС1 1 ТУ 1 «- 1 — 1. 10 ЕИТЗ 0 «"т' 4 +- О. 80 104 1ИРУТ, 1 Ж К«-К,.
81 11Р 4В )У А'>1>1. ! Здесь В'+В" = В+Аг — 1, 17'+)У" = А'-1, так что суммарное время выполнения сортировки равно 5В+ 14М+ )т' — 3 ма«аниных циклов. Поскольку рр равно числу злементов, справа от которых имеется нечетное число меныпих элементов, величина М' имеет следующие статистические характеристики: 1 1 1 (пнп О, ате -А«+ -Н(я1з) — -Вш шах Аг — 1) 2 4 2 Трюк с ариев>снись«значения оо дает аналогичное ускорение и программы Я. Приведенный ниже текст при раммы преддожен Дж. Х.
Гальпериных«(Л. Н. Нв)рог(п), который использовал зту идею и команду НОТЕ для сокращения времени выполнения до (6В+ 111««'— 10) в, павшая, что по адресу ХЕРСТ+И+1 уже находится наибольшее возможное однословное число. 01 ЗТККТ 08 2Н 08 04 05 4Н 06 ЗН 07 08 ВН 00 10 ЕИТ2 И-1 501 1ИРУТ,2 ЕИТ1 1ИРУТ,2 1НР ЗР НОЧИ 1,1(1) СНРЗ 1.1 1С 4В 374 0,1 РЕС2 1 12Р 2В 1 10 — 1 ХУ вЂ” 1 )У вЂ” 1 В В+Я вЂ” 1 В+ А« — 1 17 — 1 )У вЂ” 1 Ж вЂ” 1 $ Дублирование внутреннего цикла сохранит дополнительно В/2 или около того машинных циклов.
34. Существует (~) последовательностей из Х выборов, в которых данный список выби- рается и раз; вероятность появления каждой такой последовательности равна (1/М) (1— 1/М)л ", так как каждый список выбирается с вероятностью 1/М. 35 84 ЕИТ1 О 1 Яд ЕИТ1 О,З Ж 85 ЕИТ2 1-И 1 Яо 103 ПП%7,1(1ТИН) )Ь" Йд 7н 103 неар+и,2 М Я1 ЗЗр ° -2 Л' 87 ЛЗ2 Зд М ЯЕ 8Н ХИ02 1 М 88 ЗТЗ ТИРОТ, 1(11ИК) М вЂ” Е ЯЯ ЗЗИР 78 М $ Замечание. Если программа М была модифицирована таким образом, чтобы отслежи- вать текущий конец каждого списка, то, поместив комацлу "ЗТ1 ЕИ0,4«между строками 19 и 20, можно сберечь время путем обьединения списков так же, как и в алгоритме 5.2.5Н. 36.
Программа Тх А = 3, В = 41, А' = 16, время = 496и, Программа М: Л м 2+ 1+ 1+ 3 ы 7, В = 2+ О+ 3+ 3 = 8, Ф = 16, врема = 549и. (К приведенному значению времени выполнения программы М нужно добавить время 94и, необходимое для выполнения дополнительной программы из упр. 35. Это позволит осуществить корректное сравнение. Операции умножения всегда замедляют выполнение программы! Обратите внимание на то, что время выполнения программы 1«усовершенствованной в упр.
33, составляет только 358и, 37. Сформулированное тождество эквивалентно тождеству ,„м(,) , ~- / . ~ , (,) , (,) -и Ач. ~ц+- +«м «к которое доказывается, как в упр, 34. Интересно, по-видимому, будет привести таблицу некоторых из этих производящих функций, чтобы выявить тенденцию, которая иаблюдаетгя при возрастании М: ум(х) = (216+ 648х+ 1080хх+ 1296хз+ 1080х~+ 648хз+ 216хе)/5184, Уы(,) = (945+1917.+1485х'+ 594хз+ 135хх+ 81,з+ 27хе)/5184, дхз(х) = (1704+2264х+ 840хз+ 304хз+ 40х~+ 24х + 8х~)/5184. Если См (ш, х) — сформулированная двойная производящая функция, то дифференциро- вание по х дает ~м-1 « ю« См(ю,х) = М~ ~д„(х) —,) ~ д„(х) —,.
««йэ «>э Следовательно, Ми и /,х Е (ц ю М (м-3)«и' «~ х мш )д( 4 Аналогично из формулы д„"(Ц = Зз(") + Зз (") следует, что л я 2 дмлЯ вЂ” =М(М вЂ” 1)е ~ — е ~ +Ме ~-зх +-ш ~е . М (м х)«хх «<и Н /3 з 5 аз Х1 ~,4 '12 3,/ н>э Приравиивание коэффициентов призон дает длм(1) = -'( )М ',дччм(1) = (З(х)+ з (з)) х хМ х, и оказывается, что дисперсия равна (-'(' ) + х='( )) М з.
36 ~ 4 „('„")рэ(1-рз)" п(з) = (к) ~„ур,'; положиврб = Е(//М) — Г((/ — 1)/М) и Е'(я) = /(Я), зтУ сУмма можно пРивести к пРоизведекию ( з ) /М и [о /(к)з 4Я, если только фУнкцив Г подобрана достаточно хорошо. [Однако ) /(х)з 4к может оказаться слишком велико. 'лонкости выбора, подходищего для всех ограниченных интегрируемых плотностей, приводится в теореме 5.2.5Т. (Здесь имеется в виду интегрируемость по Риману. — Прзлм. рд)[ ЗВ.
Чтобы минимизировать величину АС/М + ВМ, нужно положить М = /АС/В, так что М вЂ” одно из целых, ближайшее (сверху или снизу) к этому значению. (В случае программы М можно было бы выбрать М прсшорциональным Х.) 40. Асимптотические ряды для -'(1- /ж)п-к м-А-'+~(А'+5) '(1-о/А)' п>К л>о можно получить, ограничившись значениями к до О(Х'+'), представив (1 — а/Х)" как произведение е "ш~ и (1 — кпз/2Кз + ) и использовав формулу суммирования Эйлера; теперь выражение начинается с членов е" Ез(оК1 + о~/214) — (1+ а)/2А'+ О(Х ). Следовательно, асимптотическое значение (15) есть Х(1по+ т+ Ез(а))/о+ (1 — е "(1+ а))/2а+О(Ю ').
[Коэффициент при 1т' равен 0.7966, 0.6596, 0.2830 соответственно для а = 1, 2, 10 ) Обратите внимание на то, что, кэк показано в упр. 5 2 2 — 43, !по+ у+ Ез (а) = У (1 -4)4-46 41. Имеем ал = О(р ), поскольку из теоремм о простых числах следует, что количество л простых чисел мек4ду рл и р"+' равно рл+'/(к+ 1) — р"/й+ О(рл/к~). это значение положительно дэи всех достаточно больших к.
Таким образом, сумма первых (") элементов в соотношении (10) равна [,«, .„5(а„а ) = 2 <4 <„О(р4+"), Отсюда получим 4+, г'(р" — 1)(рл ' — 1) (р' — 1К вЂ” 1) (Ь) Если (л ~) < 1ой Ю < (л), имеем (й — 1)з < 2!ой Х, поскольку рзл = О(ехрсл/[пХ). Обратите внимание на то, что, поскольку р -4 1, базовая последовательность ом оз, становится равной последовательности простых чисел и в теореме 1 граница снижается до О(л7()о6 к4)4()ой1об м)-з) 42.
(а) [А. С. Уао, Х А16ог1зйшз 1 (1930), 14-50.[ Можно показать, что каждая из (") пар списков потребует фй ~Ь ю~Хш~ + О(Ю/95) инверсий на казкдый подмассив (Кп, Кп+з, К«+зз,...), 1 < а < р. Например, предшиожкм, чтой = 12,9 = 5, о ш 1, и проаиалязируем инверсии, когда списки Кз < Кы < Кзт < и Кз < Кш < Кзз < пересекают подмассив (К1„Ке, Кн,. ), После первого прохода (Кз, Кц Кы, Кш, Кем йю„., ) паэучается случайная 2-упорядоченная перестановка. Элементы Кз, которые нас особо заботят, имеют у' ш 1 (по модулю 5) и / ш 3 или 7 (по модулю 12); следовательно,,~' ш 51 или 31 (по модулю 60), а нам нужно вычислить среднее значение 9(51,31), где 9(к~ У) = ~ ([Кпчтлз > Кз+злл[+ [Кт+яы > Кп+злл[) + г(я Р) 4'(я Р) ~~~ [Кпяп4п,т)+злу > К и пьз)+злу[ < 4 Чуй Если [р[ < д и [9[ < р, то получим [К +эл-зл > Кл+чл+зл) < [Ку > Кл[ < [Кз+элчкл > Кл+зл-ял[, Значит, !К ргго > Кр+гьь[+ [Кр+рго > К грьь! < [к ррлррьб+м > крегььгл!г-1!) + [Ар+ел+гьб+м > к +рь+гь!г-ц[.
Отсюда следует, что у(х,р) < д(х+ рй,р+ дй) + ЗХ/уй. Аналогично найдем у(х,р) > у(х+ рйу+ уй) — ЗА!/дй. Но сумма у(яр) по всем дг парам (х р), таким, что х шаг)й = Ь и р шог! й = с для любого данного Ь ф с, и есть общее количество инверсий в случайной 2-упорядоченной перестановке 2Ю/й ьтеьгентов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
