AOP_Tom3 (1021738), страница 174
Текст из файла (страница 174)
30. Число точек с целыми координатами в треугольной области (х!п2+И)пЗ С )п)л', х > О, И > 0) Равно -'()абл))1)()аЕ Х)+0(1оЕЬ'). Ва время Ь-сортнровки массив уже 2Ь- н ЗЬ-упорядочен (см. теорему К); следовательно, можно использовать результат упр. 25. 31. 01 ЯТАНТ ЕИТЗ Т 1 ОЯ 1Н 504 Н,З Т 00 ЕИИ2 -ТИРОТ-И,4 Т (Ц БТ2 БГ(0:2) Т 05 БТ2 7Г(0:2) Т Об БТ2 4Г(0:2) Т 07 ЕИТ2 0,4 Т ОЯ .ТМР 9Г Т 00 2Н 10А ТИРОТ+И,1 )л7Т вЂ” Я вЂ” В + А 10 4Н СИРА ХИРОТ+И-Н,1 ЖТ вЂ” Я вЂ” В + А 11 10Е 8Г )ГТ вЂ” Я вЂ” В + А 1Я 6Н ЬОХ ХИРОТ+И-Н,1 В 12 БТХ ХИРОТ+8,1 В Ц 7Н ЯТА 1ИРОТ+И-Н, 1 В 15 1ИС1 0,4 В 10 ЯН ХИС1 0,4 11Т вЂ” В+ А 17 11ИР 28 )9Т вЂ” В+ А 18 ОЕС2 1 Я !О 9Н ЕИТ1 -И,2 Т.~- Я ЯО 12Р 80 Т+Я Я1 ОЕСЗ 1 Т ЯЯ )ЗР 18 Т $ Здесь А — число правосторонних максимумов, как А в программе  — число левостш ранних минимумов; обе величины статистически ведут себя одинаково.
В результате упрощения внутреннего цикла время выполнения сократилось да 7ЬлТ+ 7.4 — 25+ 1 + 15Т машинных циклов н, как ни странно, оно не зависит от В! При Х = 8 смещениями будут 6, 4, 3, 2, 1, и имеем Аа е = 3.892. В т = 6,762; суммарное время работы в среднем составляет 276.24и (ср. с табл, 5). Обе величины— А и  — достигают максимума на перестановке 7 3 8 4 5 1 6 2. При Ж = 1000 имеется последовательность из 40 смещений: 972,864, 768,729,...,8,6,4, 3, '1, 1; змпирические тесты, подобные тем, которые приведены в табл, 6, дают А 875,  — 4250 и общее время выполнения — около 268000и (примерно вдвое больше, чем для программы В с последовательностью смещений из упр. 28).
Вместо того чтобы хранить значения смещений во вспомогательной таблице, удобно генерировать их на двоичной машине следующим образом. Р1. Присвоить т +- 20х ~) ', наибольшая степень двойки, меньшая Ж. Р2. Присвоить )л+- гп. РЗ. Использовать Ь в качестве смещения на очередном проходе сортировки. Р4. Если Ь четное, присвоить Ь г- Ь+ Ь/2; затем, если Ь С Х, вернуться к РЗ.
Р5. Присвоить т < — (т/2) и, если т > 1, возвратиться к Р2. Хотя смещения для сортировки генерируются не в порядке убывания, сформированная последовательность значений обеспечивает правильную работу алгарятма. 32. 4 12 11 13 2 О 8 5 10 14 1 6 3 9 16 7 15. 33. Улучшить программу можно двумя разными способами. Во-первых, полагая, что искусственный ключ Ка равен ~ю, можно опустить цраверку ушювия р > О. (Эта идея применялась, например, в алгоритме 2.2.4А.) Вшвторых, можно использовать стандартный прием оптимизации; продублировать внутренний цикл, поменяв местами присвоенные регистрам значения р и 4; в результате удастся избежать присвоения Ч +- Р. (Эта идея использовалась в упр.
1.1- 3 ) Таким образом, предполагается, чро в пале (О:3) по адресу 1МРОТ содержится наибольшее возможное значение и нужно заменить в программе Ь строки, начиная с 07, следующими. 07 ВН ЬОЗ !КРОТ,2(ЬТМК) В' Р+- Ьд. (Здесь Р = г13, Ч сн г12.) 00 СИРА 1МРОТ,З(КЕТ) В' 00 1С 4Г В' Перейти к шагу Ь4 с Ч р+ р, если К > Кг. 10 7Н БТ1 1МРОТ,2(Ь1МК) 1Ч' 7р +- 1. 11 БТЗ 1МРОТ.1(ЬТМК) !Ч' Ь, +- р. 18 ЗНР ВГ Ан Переход на уменьшение 1'. 1Я 4Н ЬО2 ТМРОТ,З(ЬТМК) В" р+- Ьр. (Здесь р се г12, Ч Щ г13.) 14 СЕРА ТМР1)Т,2(КЕТ) В" 15 ЛС 88 В" Перейти к шагу Ь4 с 9 р+ р, если К > Кр. 10 БН ЯТ1 1МРОТ,З(Ь1МК) АР Ьр Р- 1. 17 ЯТ2 1МРОТ,1(Ь1МК) дУн Ь, р- р.
18 6Н ОЕС1 1 !Ч 1+-1 — 1. !О ЕМТЗ О АР Ч+- О. 80 ЬОА 1МРОТ,1 !Ч К р- К,. 81 11Р 48 !Ч Ч>1>1. 3 Здесь В'+В" = В+!Ч вЂ” 1, !Ч'+!Ч" = )Ч вЂ” 1, так что суммарное время выполнении сортировки равно 5В + 14рл7 + !Ч' — 3 машинных циклов. Поскольку )Ч' равно числу злелрентов, справа от которых имеется нечетное число меньших элементов, величина 1Ч' имеет следующие статистические характеристики: 1 1 1 (ш)п О, аде -!Ч+ — Н(ид6 — -Нщ рвах !Ч вЂ” 1). 2 4 ' 2 Трюк с присвоением значершя со дает аналогичное ускорение и программы Б. Приведенный ниже текст программы предложен Дж. Х.
Гальпериным (д. Н. На!Регйл), который использовал эту идею и команду НОТЕ для сокращения времени выполнения до (6В+ 11Ар— 10)и, полагая, что по адресу 1МРОТ+В+1 уже находится наибольшее возможное однословное число. 01 БТАВТ 08 28 ОЯ 04 05 4Н Об ЗН 07 ОЯ БН 00 10 ЕНТ2 М-1 ЬОА 1МРОТ,2 ЕМТ1 1МРОТ,2 1НР ЗГ МОЧЕ 1,1(1) СНРА 1.1 1С 4В БТА 0,1 ОЕС2 1 12Р 28 1 1Ч вЂ” 1 !Ч вЂ” 1 !Ч вЂ” 1 В В+ !Ч вЂ” 1 В+ рУ вЂ” 1 Ж вЂ” 1 Аг — 1 !Ч вЂ” 1 Дублирование внутреннего цикла сохранит дополнительно В/2 или около того машинных циклов. 34. Существует (~~) последовательностей из Х выборов, в которых данный список выбирается и раз; вероятность появления каждой такой последовательности равна (1/М)'(1— 1/М)~ ", так как каждый список выбирается с вероятностью 1/М.
35. Я4 ЕИТ1 0 1 Яд ЕИТ1 0,3 1д Яб ЕИТ2 1-Н 1 Яд Ы)3 1ИРОТ,1(ПИН) Н/ Яб 7Н 503 НЕАВ+Н,2 М 31 ЛЗР «-2 Х Я7 332 ВР М ЯЯ ВН 1ИС2 1 М ЯВ ЗТЗ 1ИРВТ,1(11ИК) М вЂ” Е ЯЯ 22ИР 78 М Замечание. Если программа М была модифицирована таким образом, чтобы отслеживать текущий конец каждого списка, то, поместив команду "БТ1 ЕИ0,4" между строками 19 и 20, можно сберечь время путем объединения списков так же, как и в алгоритме 5.2,5Н. 36. Программа 1л А = 3, В = 41, Ж = 16, время = 496и. Программа М: А = 2 + 1+ 1+3 = 7, В = 2+0+3+3 = 8, Ж = 16, время = 549и. (К приведенному значению времени выполнения программы М нужно добавить время 94и, необходимое для выполнения дополнительной программы нз упр.
35. Это позволит осуществить корректное сравнение. Операции умножения всегда замедляют выполнение программы! Обратите внимание на то, что время выполнения программы Е, усовершенствованной в упр. 33, составляет только 358и. 37. Сформулированное тождество эквивалентно тождеству дкм(з) = М г ~ ~ ~ ) д>1(в) ° д м(в) -Ю / НО щ.~.-м в>~ =и которое доказывается, как в упр. 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 ам(-, ) = М(~.д.( )=„, ) ~д'.( )=„, . >е >а Следовательно, л к г 2 (1) =М вЂ” ~ — ) = 1о! 4 / 4 я>е Аналогично из формулы д„"(1) = з (") + ~ (") следует, что 54 к х (1) М(М 1)е(лг-Юч ~ и + М 1и-Пч ( 4 з) л>а Приравнивание козффициентов прин~ч даетд'„(1) = —,'(л~)М ' Щ (ц — (3('")+1(я))х хМ, и оказывается, что дисперсия равна (-'(~) + 'м ' (~)) М-"-, 38 2 ' ( )Рт (1 — рт) ( ) = (з) Я рз; положив рз ж Е(1/М) — Щу — 1)/М) и Г (х) = /(х), зту сумма можно привести к произведению ( )/М и Д /(х) д!х, если только функция Г подобрана достаточна харашо.
[Однако Д' /(х)з т!х мажет оказаться слишком велико. Тонкости выбора, подходящего для всех ограниченных интегрируемых плотностей, приводятся в теореме 5.2.5Т. (Здесь имеется в визу интегрируемость по Рнману. — Прим. ред.).! 39. Чтобы минимизировать величину АС/М + ВМ, нужно положить ЛХ = „/АС/В, так что М вЂ” одно из целых, ближайшее (сверху илн снизу) к этому значению.
(В случае программы М можно было бы выбрать Л1 пропортндональным )з1) 40. Асимптотические ряды для ~ п '(1 — а/Ю" =-Ат '+~ (А'+АГ'(1 — а/!У)' >л й>а можно получить, ограничившись значениями 6 до О(Ат'~'), представив (1 — а/тз/) как произведение е йтн и (1 — йа~/2тт~ + ) и использовав формулу суммирования Эйлера; таперь выражение начинаетсв с членов е Ет(а)(1 -ь а~/2!У) — (1 + а)/2Ат+ 0()тт ). Следовательно, асимптотическое значение (15) есть !йт(!па+о+ Ей(а))/а+ (1 — е (1+ а))/2а+ 0(!йт ').
[Коэффициент при !у равен — 0.7966, 0.6596, 0.2880 соответственно для и = 1, 2, 10.! Обратите внимание на то что, как показано в упр. 5.2.2-43, 1и о+ 7+ Ет (а) = (1 — е ')»' да 41. Имеем ай = О(р ), поскольку из теоремы о простых числах следует, что количество простых чисел между р" и рйе' равно рйд.й/(6 + 1) — рй/6 + 0(рй/!дз). Это значение положительно для всех достаточно больших !д. Такии образом, суима тшрвых (й) элементов в соотношении (10) Равна Ят<д«6(а„е,) = 2 т<д«, О(Ртет). Отсюда полУчим з( й 1)( й-д (Ь) Если (й ') < 1об„дт < (й), имеем (!д — 1) < 2!об Х, поскачьку рзй = О(ехрсьт)пдт).
Обратите внимание на то, что, поскольку р д 1, бзазовая погледовательность ет, из.. становится равной последователыюсти простых чисел и в теореме 1 граница снижается до О(!У(1обЛ)4(! К!обА)-'). 42. (а) [А. С. Тао, Х А!догй!зпм 1 (1980), 14-50.! Можно показать, что каждая из (й) пар списков потРебУет зд д з6 ~~~Ат~~~ + 0(АГ/96) инвеРсий на каждый подмассив (К„К<+д, К ттд,...
), 1 < е < д. Например, предположим, что 6 = 12, д = 5, а = 1, и проанализируем инверсии, когда списки Кз < Кы < Кзт < н Кт < Кш < Кзт < пересекают подмассив (Кз,Кд,Кп,...) После первого прохода (Кз,Кт Ктз,Ктд,Кзт Кзт, ) получается случайная 2-упорядоченная перестановка. Элементы К„которые нас особо заботят, имеют /— : 1 (по модулю 5) и 1 = 3 или 7 (по модулю 12); следовательно, / = 51 или 31 (по модулю 60), а нам нужно вычислить среднее значение д(51, 31), где д(х, у) = )' ([Кйз-дй! > Кдйдйй! + [Кд+дйт > Азади !) + г(х у) т<й г(х, у) = ~~' [К дтд,д!едй! > К ° тй,дтд.дйт] < !т/96.
Если ]р] < д и [д[ < д, то получим [Ку /дй-дй > Кй+дйедй! < [К, > К ] < [К!еде дт > Кй+тй-д~ ]. Значит, [К*+зги > Кд+дьь] + [Кд+дьд > К*+дш] < [к +дьедьсбе«> к)+бьч.ддсб — «] + [кдч-дь+дьсдд«> к*ддьддлсд- «!. Отсюда следует, что д(х,д) < д(х + р6,у + 96) -1- 8Х/96. Аналогично яайделс д(х,д) > д(х+ р6, у + 96) — 86)/96.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
