Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 74
Текст из файла (страница 74)
Таким образом, как следует нз упр. 14„ среднее значение у(х, р) равно д гз/я/128 (2Х/й)г7~ + О(Х/дй). (Ь) См. С. Я. Ланаоп, 11. Е. Кпцг!ь Ялпдош Яегисгигег апд А1ш. 10 (1997), 125-142. Если й и д велики, имеем фй, у) = ь/яй/128 9+ О(д" ~ й ~ ) + О(дй '~~), 43. Если К < К~ пеле шага )рЗ, присвоить (Кн...,К,-ь,К,) +- (К,Кн...,Кз-л); в противном случае выполнять шаги 114 н П5 до тех пор, пока К > К;. Здесь ! = 1, если у = й + 1, а 1 е- 1+ 1 — й [1 = й[, если у увеличивается на 1.
[См, Н. %'. ТйппЫеЬу, яогеиъге Ргасбсе дг Ехрег. 19 (1989), 303-307.[ Другая идея повышения скорости выполнения программы состоит в том, чтобы прн й > 1 выполнять сортировку только частично, не пытаясь продвинуть К, влево далее позиции у — й [см. Ър. 77оЬог!ек4<г, 1пб Ргоц Ьешегг 11 (1980), 5-5[, но, кажется, этот подход требует больше смещений. 44. (а) Да. Это очевидно в случае, когда я' оказъшается на один шаг гвышег 1г; в упр.
5.1.1-29 показано, что при таких условиях существует путь от т к любой перестановке над ней, Этот путь образован операциями транспоннрования соседних мементов. (Ь) Да. Аналогично, если к расположена "выше" х', то х" расположена "ниже" х'". (с) Нет; 213 не будет нн "выше"[ ни "нижеР 312, но 213 < 312, [Частичное упорядочение х < я' было впервые проанализировано Ч. Эресманом в контексте алгебраической топологии (С. Ейгелшапп. Аппа1г оГ Маей. (2) 35 (1934), 39б-443, 320). Многие математики называют его теперь порядком Врюа перестановок.) РАЗДЕЛ $.2.2 1.
Нет, в ней на 2гл+ 1 инверсий меньше, где гп > Π— число элементов аг, таким, что 1 < й < !' и аг > аь > а . (Следовательно, любая обменная сортировка, в юнце концов, пряводит к упорядоченной перестановке.) 2. (а) б. (Ь) [А. Сау!еу, Рй!1ог, Мад. 34 (1849), 527-529,] Рассмотрим циклическое представление перестановки к, Если поменять местами элементы одного и того хсе цикла, то число циклов регличипггл на 1, если поменять местами элементы разных циклов, то число циклов рменьшипгсл на 1. (Это, по существу, содержание упр.
2.2.4-3,) Полностью рассортированная перестановка характеризуется тем, что она имеет и циклов. Следовательно, хсЬ(я) равно и минус число циклов перестановки х. [Алгоритм 5.2.3Я выполняет ровно хсй(я) операций обмена записей; см. упр, 5.2.3-4.) 3. Да; относительное расположение равных элементов никогда не меняется. 4. Это вероятность того, что в таблице инверсий будет Ь| > шах(6г,...,6„). Вероятность равна с Е н~'-'-'),/.= рс!к р( -'~= ° гбь<р 5. Можно считать, что г > О. Пусть 6'; = (Ь; — г + 1) [Ь, > г[ — таблица инверсий после г — 1 проходов. Если Ь', > О, то элементу ! предшествует Ь'; больших элементов, наибольший из которых всплывает, по крайней мере, до позиции Ь', +1 (так как имеется ! элементов < 1).
Кроме того, если элемент 1 — крайний справа среди всех элементов, которые предстоит обменять, то Ь' > 0 н после т-го прохода ИООИО м Ь,'+1 — 1. 6. Решение 1. Элемент, наиболее удаленный вправо от своего конечного положения, перемешается им один шаг влево при каждом просмотре, кроме последнего. Решение 2 (более высокого уровня), Из упр. 5.1.1-8, ответ (1), а', — т = Ь; — ст при 1 < т < и, гле ст сз ..с — двойственная таблица инверсий. Если Ьу ы шах(Ьт,..., Ь„), то ст = О.
~(+эо+т() — тс э-т~) — гатт"=Лг!2>+опт 8. При т < й+ 2 имеется 1+ й — т+ 1 способов выбора Ь,; при й+ 2 < т < и -1+ 2 имеется 1 — 1 /'-1 способов; при т ~ и — 1+ 2 имеется и — т + 1 способов. 10. (а) Если т = 2й-1, то нз (й — 1, а, — й) в (й, ат — й).
Если т = 21т, то из (а~ -й, й — 1) в (ат — 1т, й). (Ь) Шаг атд-~ выше диагонали с=э й < аэд т - й ч=д азд т > 2й аы-т > аы а=э ам < 2й-1 а=э аы — й < й — 1 с=э шаг азд выше диагонали. Если поменять этн элементы местами, то поменяются местами горизонтальный и вертикальный шаги. (с) Шаг атаев будет, по крайней мере, на т» единиц ниже диагонали а=э й+т» — 1 > ать+в — (й+ пт) + т» ч=д азд.~.~ < 2й+ т» стнэ атд > 2й+ т» емхт атд — й > й+ пт ет=ь шаг аы, (Если ам+в < 2й + т» и атд < 2й + т», то имеется не менее (й + т») + й элементов, меныпих, чем 2й + пт, а зто невозможно.
Если ать+в > 2й + пт и аэд > 2й+ пт, то один из знаков ">' должен быть знаком "> "; но невозможно поместить все элементы < 2й+ ш в менее чем (й+ т») + й позиций, Следовательно, ать+э,„~ < аэд тогда и только тогда, когда ам+та-т < 2й + пт, т е. когда 2й + т» < аэд. Довольно неожиданный результат!) 11.
1б 10 13 5 14 б 9 2 15 8 11 3 12 4 7 1 (81 обмен). Ответ получается в результате анализа решеточной диаграммы. Ситуация усложняется, если Х велико; э общем случае множество (Кт, Кы... ) должно быть таким: (1, 2,..., М вЂ” 1, М, М + 2, Ы+ 4... 2 (57/21 — М); и его перестановка должна максимизировать число обменов для 1/зт/2) элементов. Здесь М = ) 2~/3), где й максимнзирует й1Х/21 — дт((Зй — 2)2д-' + ( — 1)д). Суммарное максимальное число операций обмена записей равно произведению 1 — 2 (8 18 1э/ )8 Х+ С(1/ (об»т) и числа сравнений (Е. Вес)бекбсй, ЯСОМР 7 (1978), 239-272), 12.
Б следующей программе, написанной В. Панин (%. Раппу), команда ЬИО не исполь- зуется — для этого шаг М4 выполняется при т = г+ 2йр+ в„й > 0 и 0 < в < р. Здесь ТТ ш 2, р ш гП, т ээ г12, т ш г13, т+ 8 — 1зт ш г14 и р — 1 — в ш г15. полагается, что )1т > 2. т-т 01 ВТЬНТ ЕИТ1 ТТ 1 М1. н ат я .рт-2'"~. 09 28 ЕИТ2 ТТ Т М2. О и элиз т т). И ЗТ2 Я(1: 21 Т 9 д- 2' ', 04 ЕИТ2 0 .Т ге-б. 05 ЕИТ4 0,1 Т т14 д- ай 05 ЗН ЕИТЗ 0,2 мз. д~ 07 1ИС4 "И,З А г14+-т+т)-Ж, 08 НН ЕИТ5 "1,1 )9+ Е в+-О. ОУ 4Н 194 1ИРОТ+1,3 С М С аннели обмен К .
10 СЕРЬ 1ИРОТ+Н+1,4 С 11 118 э+4 С Переход, если К,+т < Кт+в+т. 19 102 1ИРОТ+И+1,4 В 13 871 1НРОТ+1.3 В Вз+ Кт+ + . 14 ЗТЬ 1ИРОТ+И+1,4 В 15 352 7Р С Переход, если в = р — 1. 1б ОЕСЗ 1 С вЂ” 17 вт-в+1. 17 1ИСЗ 1 С вЂ” В т+- т+1. 1В 1ИС4 1 С вЂ” 17 а -4/2. г14 е- д.. Перейти к шагу МЗ, если и 14 О Щф, Цикб по в, а П 2"(и — Ь) = 2"+'-п-2, ~~~ 2~( ) = 24ы — ( ) — 1, е=е аз е приводят к результату с(Ф) = Х(- ( ) + 2е1 — 1) — 2" (е~ — Ц вЂ” 1 +~ 2'~ ~е1+ ° +е, ~ — у(е1 — Ц+ - ( ' т)).
19 Уйн 4В С вЂ” Р Повторить цикл, если )+и < Х. 80 ЛНР ЬР ;Е Иначе перейтн к МЬ. тн тиоз 1,1 Р 1+-1+ и+ 1. 38 1ИО4 1,1 Р 8« Уйн 4В Р Повторить цикл, если 1+ и < Х. 84 бн китг о,1 А ))(3,Дйкдднд. г е- р. Вб О КИТ4 е А г14 е- О. вб китЬ 0,4 А 87 ЗИВ 1 А 38 зт4 О(1:2) А 89 0804 о,1 А «б 14Р ЗВ А «1 бн кита о,1 т «3 ЗВВ Т «« втй в+1(1:г) Т Кнтт е Т и Е- (р/2(. «б 11ит гв Т Перейти к шагу М2, если и Ф О. $ Время выполнении зависит от шести параметров, из которых лишь один зависит от исходных данных (остальные пять являются функциями только от Ф): Т = с, числа "внешних циклов"; А = е(Ф + Ц/2, числа просмотров, нли "внутренних циклов"; В = числу обменов (переменному); С = числу сравнений; Р = числу блоков последовательных сравнений; Е = числу неполных блоков.
Если Х = 2', то можно показать, что Р = (1 — 2)Ф+т+ 2 и Е = О. Для данных нз табл. 1 Т = 4, А = 10, В = 3+0+1+4+0+0+8+0+4+5 = 25, С = 63, Р = 38, Е = О, так что общее время выполнения равно 11А+бВ+10С+ 2Е+ 12Т+1 = 939в. Панин показал, что вобщем случае Р = е1(Ф+ Ц вЂ” 2(2" — Ц, Е = (" '")+(е1+еа+ + ) ( Ц(, Ц // гы+ +ге 13. Нет, так же, как и алгоритмы С) и К. 14. (а) Есля р = 1, то при последнем слиянии выполняем (2' ' — О) + (2' ' — Ц+ (2' ~— 2)+(2'-'-4)+" +(2' '-2' ') = (Г-Ц2' '+1сравнений;(Ь) ва =ха-1+1(Г-Ц+2 ' = "=хе+2 ос<(-'8+2 ~ ') = «( )+1 — 2 '.
Следовательно, с(2 ) = 2' '(с'-1+4)-1. 13. (а) ржсмотрнте число сравнений, таких, что 1+ б = Ф; затем примените индукцию пот. (Ь) Если Ь(п) =с(п+Ц, тоимеем Ь(2п) =о(Ц+ +о(2п) = а(0)+а(Ц+а(Ц+".+ о(п — Ц + а(п) + я(Ц + я(2) + + я(2п) = 2Ь(п) + р(гп) — е(п); аналогично Ь(2п+ Ц ю 2Ь(п) + И(го+ Ц. (с) См. упр. 1.2.4-42. (д) Весьма трудоемкие вычисления выражения (х(Ф) + гг((Х/2)) + ° . ) — о(/т') с использованием таких формул, как 16. рассмотрим ( „") путей на решетке нз (О, 0) в (п, п), как на рис. 11 и 18, и присвоим серии от (1„у) до (1+ 1,/) вес /(1 —,у), если 1 > у, и /(у — 1 — Ц + 1, если з < «; здесь /(Ь) — число изменений разрядов Ь, ф Ь,е1 в двоичном представлении й ж (,, ЬтЬ,Ье)т, Если 1О = гп, то общее число обменов в окончательном слиянии равно 2 1 ..«„(2/Ц) + 1)(,.' /)( „',, г, ).
Р. Седгевик показал, что в общем случае / эта сумма упрощается и пРиводитсм к видУ г (~") + 22 „, („г" ) ~ есг „ /(2); затем он использовал метод гамма- функции и получил асимптотическое выражейие ) ~-~!3п+ ~!3 + — + — +Ю(п)) и+О(з/й!обп)), 1)~ 2п 1 /1 / Г(1/4) 1 7+ 2 )~4 ~ 2 4 412 гд» 3(п) — периодическая функция !3 п с ограниченной амплитудой.0005. Следовательно, в среднем около 1/4 сравнений приведет к обмену при и -+ оо.
(ЯСОМР 7 (1973), 239-272; см. также Р!а)о!еэ., Об!узко, ЯАМ Х Ебэсгеге Май. 3 (1990), 233-239,) 17. Значение Кл+1 проверяется при сортировке подмассива, для которого г = Е и К~— иаиболыпий ключ. Кэ проверяется на шаге ь)9, когда минимум слева направо погружается до позипии В~. 13. На шагах ЯЗ и (44 до перехода к ЯЬ выполняется едикственная замена 1 иа /; процесс разделении подмассива Щ... В„закэлчивается при / = ((!+ г)/2~! иа шаге Я7, т, е, подмассив разделяется по возможности точно пополам.
(Количественно это выражается в том, что формулы (17) замеишотся формулами А м 1, В = ((Ж-1)/2), С = !У+ ()У шоб 2); это, по существу, наилучший случай для алгоритма (см. также упр. 27, приведенное ниже), за исключением того, что В ш -'С. Если на шагах ь)З и Я4 заменить знаки "<" знаками "'<", то алгоритм вообще ие будет сортировать данные. Даже если предполагать, что в (13) стоят знаки "<"( все равно иаш алгоритм поменяет местами Ие с Вм затем в третьей фазе разделения переместит исходную запись Ве в позицию Лг и т.
д. Настоящая катастрофа! 19, Да, полмэссивы можно обрабатывать в любом порядке. Но в очереди будет 1)(!з/ //!об Ф) элемеитов, если каждая очередная итерация будет разбивать массив ровно вополам, в то время как стек гарантированно остается меньшим по объему (см. следующее упражнение). 20. п1ах(О, (!3()У+2)/(М+2)!). (Самый плохой случай — это когда )У = 2 (М+ 2) — 1 и все подмассивы разделяются точно пополам.) 21.
На шаге (46 точно г записей перемещается в область В +1... Вл, поскольку В = б Когда фаза разбиения завершается, то,у = г. Следовательно, С вЂ” С' = Ф+ 1 — в есть количество вычитаиий 1 из /. На шахе ь)7 мы должны получить 1 = г+ 1, если ключи различны, поскольку 1 = / влечет за собой К = К. Таким образом, С' = э. 22. Указанное соотношение для Ал(г) легко вывести, поскольку .4, ~(г)Ая-,(г) — производящая функция лля величины А после ипшвисимой сортировки случайных последовательиостей длииой г — 1 и Х вЂ” э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
